제출 #13697

#제출 시각아이디문제언어결과실행 시간메모리
13697dohyun0324Pinball (JOI14_pinball)C++98
18 / 100
170 ms10848 KiB
#include<stdio.h> #include<algorithm> #define M 2147483647000000000LL using namespace std; int cnt,t,w,m,n,c[100010],pos[200010],a[100010],b[100010]; long long dap=M,d[100010],l[300010],r[300010]; struct data2 { int x,y; bool operator<(const data2&r)const { return x<r.x; } }arr[300010]; void updatel(int p,long long x) { p+=(t-1); l[p]=min(l[p],x); p/=2; while(p) { l[p]=min(l[p*2],l[p*2+1]); p/=2; } } void updater(int p,long long x) { p+=(t-1); r[p]=min(r[p],x); p/=2; while(p) { r[p]=min(r[p*2],r[p*2+1]); p/=2; } } long long queryl(int x,int y,int k,int s,int e) { if(x>e || y<s) return M; if(s<=x && y<=e) return l[k]; return min(queryl(x,(x+y)/2,k*2,s,e),queryl((x+y)/2+1,y,k*2+1,s,e)); } long long queryr(int x,int y,int k,int s,int e) { if(x>e || y<s) return M; if(s<=x && y<=e) return r[k]; return min(queryr(x,(x+y)/2,k*2,s,e),queryr((x+y)/2+1,y,k*2+1,s,e)); } int main() { int i; long long k1,k2; scanf("%d %d",&m,&n); for(i=1;i<=m;i++) { scanf("%d %d %d %lld",&a[i],&b[i],&c[i],&d[i]); arr[++w].x=a[i]; arr[w].y=i*3-2; arr[++w].x=b[i]; arr[w].y=i*3-1; arr[++w].x=c[i]; arr[w].y=i*3; } sort(arr+1,arr+w+1); for(i=1;i<=w;i++) { if(arr[i].x!=arr[i-1].x) cnt++; if(arr[i].y%3==1) a[arr[i].y/3+1]=cnt; else if(arr[i].y%3==2) b[arr[i].y/3+1]=cnt; else c[arr[i].y/3]=cnt; } for(t=1;t<=cnt;t*=2); for(i=1;i<=t*2;i++) l[i]=r[i]=M; updatel(1,0); updater(cnt,0); for(i=1;i<=m;i++) { k1=queryl(1,t,1,a[i],b[i])+d[i]; k2=queryr(1,t,1,a[i],b[i])+d[i]; if(dap>k1+k2-d[i]) dap=k1+k2-d[i]; updatel(c[i],k1); updater(c[i],k2); } if(dap>21474836470000LL) printf("-1"); else printf("%lld",dap); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...