| 记录编号 |
598010 |
评测结果 |
AAAAAAAAAA |
| 题目名称 |
寻宝（弱化版） |
最终得分 |
100 |
| 用户昵称 |
 flyfree |
是否通过 |
通过 |
| 代码语言 |
C++ |
运行时间 |
5.635 s |
| 提交时间 |
2024-12-25 21:43:33 |
内存使用 |
101.65 MiB |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long
#define MAXN 200010
#define N (ll)1e16
#define debug cout<<"flyfree\n";
// By flyfreemrn
inline ll read(){
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
inline void write(ll x){
if(x>9)write(x/10);
putchar(x%10+'0');
}
struct node_line{
ll k,b,id;
ll find(ll x){
return k*x+b;
}
};
struct node_LCsagment{
set <ll> pnt[MAXN*4];
node_line ln[MAXN*4];
ll minz[MAXN*4],l[MAXN*4],r[MAXN*4];
void push_up(ll now){//修改
if(!pnt[now].size()){
minz[now]=N;
return;
}
ll lz=*(pnt[now].begin()),rz=*(--pnt[now].end());
// cout<<"push_up: "<<l[now]<<" "<<r[now]<<" "<<lz<<" "<<rz<<endl;
minz[now]=min(min(ln[now].find(lz),ln[now].find(rz)),min(minz[now*2],minz[now*2+1]));
}
void insert(ll lz,ll rz,ll now,node_line val){//加边
if(!pnt[now].size()){
minz[now]=N;
return;
}
ll mid=(l[now]+r[now])/2;
if(l[now]>=lz&&r[now]<=rz){
ll _l=*(pnt[now].begin()),_r=*(--pnt[now].end());
if(val.find(mid)<ln[now].find(mid))swap(ln[now],val);
if(l[now]==r[now]){
minz[now]=ln[now].find(l[now]);
// cout<<"insert: "<<l[now]<<" "<<r[now]<<" "<<minz[now]<<endl;
return;
}
if(pnt[now*2].size()&&val.find(_l)<ln[now].find(_l))insert(lz,rz,now*2,val);
if(pnt[now*2+1].size()&&val.find(_r)<ln[now].find(_r))insert(lz,rz,now*2+1,val);
push_up(now);
return;
}
if(lz<=mid)insert(lz,rz,now*2,val);
if(rz>mid)insert(lz,rz,now*2+1,val);
push_up(now);
// cout<<"insert: "<<l[now]<<" "<<r[now]<<" "<<minz[now]<<endl;
}
void push_down(ll now){
if(pnt[now*2].size()>0&&(ln[now*2].k!=ln[now].k||ln[now*2].b!=ln[now].b)){
insert(l[now*2],r[now*2],now*2,ln[now]);
}
if(pnt[now*2+1].size()>0&&(ln[now*2+1].k!=ln[now].k||ln[now*2+1].b!=ln[now].b)){
insert(l[now*2+1],r[now*2+1],now*2+1,ln[now]);
}
}
void build(ll lz,ll rz,ll now){//建树
l[now]=lz,r[now]=rz,minz[now]=N;
for(int i=lz;i<=rz;i++)pnt[now].insert(i);
ln[now]=(node_line){0,N};
if(lz==rz)return;
ll mid=(lz+rz)/2;
build(lz,mid,now*2);
build(mid+1,rz,now*2+1);
}
void del(ll pos,ll now){//删点
pnt[now].erase(pos);
if(l[now]==r[now]){
minz[now]=N;
return;
}
// push_down(now);
ll mid=(l[now]+r[now])/2;
if(pos<=mid)del(pos,now*2);
else del(pos,now*2+1);
push_up(now);
}
ll find(ll now){//找最低点
if(l[now]==r[now]){
return l[now];
}
push_down(now);
push_up(now);
// cout<<"find: "<<l[now]<<" "<<r[now]<<" "<<minz[now*2]<<" "<<minz[now*2+1]<<endl;
if(pnt[now*2].size()&&minz[now*2]<=minz[now*2+1])return find(now*2);
else return find(now*2+1);
}
ll re(ll pos,ll now,ll &frm){//询问指定位置最低点
// auto it=pnt[now].find(pos);
// if(it==pnt[now].end())return N;
ll mid=(l[now]+r[now])/2,ans=ln[now].find(pos);
if(l[now]==r[now]){
frm=ln[now].id;
return ans;
}
// push_down(now);
if(pos<=mid)ans=min(ans,re(pos,now*2,frm));
else ans=min(ans,re(pos,now*2+1,frm));
// push_up(now);
return ans;
}
}LCsgt;
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > > q;
ll used[MAXN],tag;
struct node_qs{
ll hd[MAXN*30],nxt[MAXN*30],ed[MAXN*30];
ll l[MAXN],r[MAXN],w[MAXN],dis[MAXN],frm[MAXN],cur[MAXN];
ll idx,cnt;
void build(ll x,ll y){//建边
nxt[++idx]=hd[x];
ed[idx]=y;
cur[x]=hd[x]=idx;
// w[idx]=z;
}
void insert(ll lz,ll rz,ll wz){//新建区间
l[++cnt]=lz,r[cnt]=rz,w[cnt]=wz;
dis[cnt]=N;
// return cnt;
}
void mk(ll id){//访问区间
node_line now;
now.k=0,now.b=dis[id]+w[id],now.id=frm[id];
// cout<<"mk: "<<l[id]<<" "<<r[id]<<" "<<now.b<<endl;
LCsgt.insert(l[id],r[id],1,now);
}
void acc(ll id,ll val,ll p){//访问点
for(int i=cur[id];i;i=cur[id]=nxt[i]){
// cur[id]=i;
ll y=ed[i];
if(dis[y]>val){
dis[y]=val;
q.push(make_pair(dis[y],y));
frm[y]=p;
}
}
}
}mp;
struct node_sagment{
ll l[MAXN*4],r[MAXN*4];
void build(ll lz,ll rz,ll now){//建树
l[now]=lz,r[now]=rz;
if(lz==rz)return;
ll mid=(lz+rz)/2;
build(lz,mid,now*2);
build(mid+1,rz,now*2+1);
return;
}
void add(ll lz,ll rz,ll now,ll val){//区间建边
if(l[now]>=lz&&r[now]<=rz){
mp.build(now,val);
return;
}
ll mid=(l[now]+r[now])/2;
if(lz<=mid)add(lz,rz,now*2,val);
if(rz>mid)add(lz,rz,now*2+1,val);
return;
}
void acc(ll pos,ll now,ll val){//访问出边
mp.acc(now,val,pos);
if(l[now]==r[now])return;
ll mid=(l[now]+r[now])/2;
if(pos<=mid)acc(pos,now*2,val);
else acc(pos,now*2+1,val);
}
}sgt;
vector <ll> vec;
ll n,m,v[MAXN],frm[MAXN];
int main(){
freopen("Treasure.in","r",stdin);
freopen("Treasure.out","w",stdout);
n=read(),m=read();
sgt.build(1,n,1);
LCsgt.build(1,n,1);
// mp.cnt=n;
for(int i=1;i<=n;i++){
v[i]=read();
}
for(int i=1;i<=m;i++){
ll sl=read(),sr=read(),tl=read(),tr=read(),w=read();
// mp.insert(sl,sr,w);
// mp.insert(tl,tr,w);
// sgt.add(tl,tr,1,i*2-1);
// sgt.add(sl,sr,1,i*2);
mp.insert(tl,tr,w);
sgt.add(sl,sr,1,i);
}
LCsgt.insert(1,1,1,(node_line){0,0});
// debug;
for(int i=1;i<=n+m;i++){
ll pos=LCsgt.find(1);
// ll val;
ll val=LCsgt.re(pos,1,frm[pos]);
// cout<<pos<<" "<<val<<endl;
ll valq=N;
while(!q.empty()){
if(used[q.top().second])q.pop();
else break;
}
if(!q.empty())valq=q.top().first;
if(val==valq&&val==N){
cout<<"-1\n";
return 0;
}
// cout<<pos<<" "<<val<<" "<<valq<<endl;
if(val<=valq){
// cout<<pos<<" "<<val<<" "<<frm[pos]<<endl;
if(pos==n){
tag++;
write(val);
printf("\n");
break;
}
LCsgt.del(pos,1);
sgt.acc(pos,1,val);
if(v[pos]>0){
node_line now;
// if(pos<n){
now.k=v[pos],now.b=val-v[pos]*pos,now.id=pos;
LCsgt.insert(pos,n,1,now);
// }
// if(pos>1){
now.k=-v[pos],now.b=val+v[pos]*pos,now.id=pos;
LCsgt.insert(1,pos,1,now);
// }
}
}else{
used[q.top().second]=1;
mp.mk(q.top().second);
q.pop();
}
}
// if(!tag){
// cout<<"-1\n";
// return 0;
// }
// ll now=n;
// while(now){
// vec.push_back(now);
// now=frm[now];
// }
// write(vec.size());
// printf("\n");
// for(int i=vec.size()-1;i>=0;i--){
// write(vec[i]);
// printf(" ");
// }
return 0;
}