#include<bits/stdc++.h>
using namespace std;
long long int inf=1e18 + 1;
struct node
{
long long int t;
node* l;
node* r;
node(long long int c) {
t=c;
l=nullptr;
r=nullptr;
}
};
void insert(long long int f,int c,int x,int y,node* &t)
{
if(t==nullptr) t=new node(f);
t->t=min(t->t,f);
if(x==y) return;
int m=(x+y)>>1;
if(c<=m) insert(f,c,x,m,t->l);
else insert(f,c,m+1,y,t->r);
}
long long int query(int l,int r,int x,int y,node* &t)
{
if(t==nullptr) t=new node(inf);
if(x==y) return t->t;
if(l<=x && y<=r) return t->t;
int m=(x+y)>>1;
if(r<=m) return query(l,r,x,m,t->l);
if(l>m) return query(l,r,m+1,y,t->r);
return min(query(l,r,x,m,t->l),query(l,r,m+1,y,t->r));
}
node* g;
node* h;
int m,n;
int a[150000];
int b[150000];
int c[150000];
int d[150000];
long long int p[150000];
long long int t,r;
int main()
{
scanf("%d %d",&m,&n);
for(int i=0;i<m;i++) {
scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);
}
g=nullptr;
insert(0,1,1,n,g);
for(int i=0;i<m;i++) {
p[i]=d[i]+query(a[i],b[i],1,n,g);
insert(p[i],c[i],1,n,g);
}
h=nullptr;
r=inf;
insert(0,n,1,n,h);
for(int i=0;i<m;i++) {
t=d[i]+query(a[i],b[i],1,n,h);
insert(t,c[i],1,n,h);
r=min(r,t+p[i]-d[i]);
}
if(r>=inf) printf("-1");
else printf("%lld",r);
return 0;
}
Compilation message
pinball.cpp: In function 'int main()':
pinball.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&m,&n);
~~~~~^~~~~~~~~~~~~~~
pinball.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d",&a[i],&b[i],&c[i],&d[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
448 KB |
Output is correct |
| 3 |
Correct |
2 ms |
448 KB |
Output is correct |
| 4 |
Correct |
2 ms |
456 KB |
Output is correct |
| 5 |
Correct |
2 ms |
532 KB |
Output is correct |
| 6 |
Correct |
2 ms |
532 KB |
Output is correct |
| 7 |
Correct |
2 ms |
564 KB |
Output is correct |
| 8 |
Correct |
2 ms |
736 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
448 KB |
Output is correct |
| 3 |
Correct |
2 ms |
448 KB |
Output is correct |
| 4 |
Correct |
2 ms |
456 KB |
Output is correct |
| 5 |
Correct |
2 ms |
532 KB |
Output is correct |
| 6 |
Correct |
2 ms |
532 KB |
Output is correct |
| 7 |
Correct |
2 ms |
564 KB |
Output is correct |
| 8 |
Correct |
2 ms |
736 KB |
Output is correct |
| 9 |
Correct |
2 ms |
736 KB |
Output is correct |
| 10 |
Correct |
3 ms |
740 KB |
Output is correct |
| 11 |
Correct |
3 ms |
868 KB |
Output is correct |
| 12 |
Correct |
4 ms |
1392 KB |
Output is correct |
| 13 |
Correct |
4 ms |
1524 KB |
Output is correct |
| 14 |
Correct |
4 ms |
1524 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
448 KB |
Output is correct |
| 3 |
Correct |
2 ms |
448 KB |
Output is correct |
| 4 |
Correct |
2 ms |
456 KB |
Output is correct |
| 5 |
Correct |
2 ms |
532 KB |
Output is correct |
| 6 |
Correct |
2 ms |
532 KB |
Output is correct |
| 7 |
Correct |
2 ms |
564 KB |
Output is correct |
| 8 |
Correct |
2 ms |
736 KB |
Output is correct |
| 9 |
Correct |
2 ms |
736 KB |
Output is correct |
| 10 |
Correct |
3 ms |
740 KB |
Output is correct |
| 11 |
Correct |
3 ms |
868 KB |
Output is correct |
| 12 |
Correct |
4 ms |
1392 KB |
Output is correct |
| 13 |
Correct |
4 ms |
1524 KB |
Output is correct |
| 14 |
Correct |
4 ms |
1524 KB |
Output is correct |
| 15 |
Correct |
2 ms |
1524 KB |
Output is correct |
| 16 |
Correct |
3 ms |
1524 KB |
Output is correct |
| 17 |
Correct |
7 ms |
2404 KB |
Output is correct |
| 18 |
Correct |
3 ms |
2404 KB |
Output is correct |
| 19 |
Correct |
11 ms |
4452 KB |
Output is correct |
| 20 |
Correct |
7 ms |
4452 KB |
Output is correct |
| 21 |
Correct |
4 ms |
4452 KB |
Output is correct |
| 22 |
Correct |
10 ms |
4452 KB |
Output is correct |
| 23 |
Correct |
11 ms |
4836 KB |
Output is correct |
| 24 |
Correct |
11 ms |
4980 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
2 ms |
448 KB |
Output is correct |
| 3 |
Correct |
2 ms |
448 KB |
Output is correct |
| 4 |
Correct |
2 ms |
456 KB |
Output is correct |
| 5 |
Correct |
2 ms |
532 KB |
Output is correct |
| 6 |
Correct |
2 ms |
532 KB |
Output is correct |
| 7 |
Correct |
2 ms |
564 KB |
Output is correct |
| 8 |
Correct |
2 ms |
736 KB |
Output is correct |
| 9 |
Correct |
2 ms |
736 KB |
Output is correct |
| 10 |
Correct |
3 ms |
740 KB |
Output is correct |
| 11 |
Correct |
3 ms |
868 KB |
Output is correct |
| 12 |
Correct |
4 ms |
1392 KB |
Output is correct |
| 13 |
Correct |
4 ms |
1524 KB |
Output is correct |
| 14 |
Correct |
4 ms |
1524 KB |
Output is correct |
| 15 |
Correct |
2 ms |
1524 KB |
Output is correct |
| 16 |
Correct |
3 ms |
1524 KB |
Output is correct |
| 17 |
Correct |
7 ms |
2404 KB |
Output is correct |
| 18 |
Correct |
3 ms |
2404 KB |
Output is correct |
| 19 |
Correct |
11 ms |
4452 KB |
Output is correct |
| 20 |
Correct |
7 ms |
4452 KB |
Output is correct |
| 21 |
Correct |
4 ms |
4452 KB |
Output is correct |
| 22 |
Correct |
10 ms |
4452 KB |
Output is correct |
| 23 |
Correct |
11 ms |
4836 KB |
Output is correct |
| 24 |
Correct |
11 ms |
4980 KB |
Output is correct |
| 25 |
Correct |
34 ms |
8292 KB |
Output is correct |
| 26 |
Correct |
167 ms |
40452 KB |
Output is correct |
| 27 |
Correct |
516 ms |
74404 KB |
Output is correct |
| 28 |
Correct |
248 ms |
74404 KB |
Output is correct |
| 29 |
Correct |
421 ms |
84836 KB |
Output is correct |
| 30 |
Correct |
455 ms |
84836 KB |
Output is correct |
| 31 |
Execution timed out |
1057 ms |
155108 KB |
Time limit exceeded |
| 32 |
Halted |
0 ms |
0 KB |
- |
