# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
53878 |
2018-07-01T13:35:09 Z |
milisav |
Pinball (JOI14_pinball) |
C++14 |
|
529 ms |
36964 KB |
#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;
vector<pair<int,int> > v;
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]);
v.push_back(make_pair(a[i],i));
v.push_back(make_pair(b[i],i+m));
v.push_back(make_pair(c[i],i+2*m));
}
v.push_back(make_pair(1,-1));
v.push_back(make_pair(n,-1));
sort(v.begin(),v.end());
int l=1;
if(v[0].second!=-1) {
if(v[0].second<m) a[v[0].second]=l;
else {
if(v[0].second<2*m) b[v[0].second-m]=l;
else c[v[0].second-2*m]=l;
}
}
for(int i=1;i<v.size();i++) {
if(v[i].first>v[i-1].first) l++;
if(v[i].second!=-1) {
if(v[i].second<m) a[v[i].second]=l;
else {
if(v[i].second<2*m) b[v[i].second-m]=l;
else c[v[i].second-2*m]=l;
}
}
}
n=l;
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:64:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=1;i<v.size();i++) {
~^~~~~~~~~
pinball.cpp:46: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:48: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]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
356 KB |
Output is correct |
3 |
Correct |
3 ms |
560 KB |
Output is correct |
4 |
Correct |
2 ms |
560 KB |
Output is correct |
5 |
Correct |
2 ms |
660 KB |
Output is correct |
6 |
Correct |
3 ms |
660 KB |
Output is correct |
7 |
Correct |
3 ms |
660 KB |
Output is correct |
8 |
Correct |
3 ms |
660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
356 KB |
Output is correct |
3 |
Correct |
3 ms |
560 KB |
Output is correct |
4 |
Correct |
2 ms |
560 KB |
Output is correct |
5 |
Correct |
2 ms |
660 KB |
Output is correct |
6 |
Correct |
3 ms |
660 KB |
Output is correct |
7 |
Correct |
3 ms |
660 KB |
Output is correct |
8 |
Correct |
3 ms |
660 KB |
Output is correct |
9 |
Correct |
3 ms |
660 KB |
Output is correct |
10 |
Correct |
3 ms |
744 KB |
Output is correct |
11 |
Correct |
2 ms |
744 KB |
Output is correct |
12 |
Correct |
2 ms |
744 KB |
Output is correct |
13 |
Correct |
2 ms |
744 KB |
Output is correct |
14 |
Correct |
2 ms |
744 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
356 KB |
Output is correct |
3 |
Correct |
3 ms |
560 KB |
Output is correct |
4 |
Correct |
2 ms |
560 KB |
Output is correct |
5 |
Correct |
2 ms |
660 KB |
Output is correct |
6 |
Correct |
3 ms |
660 KB |
Output is correct |
7 |
Correct |
3 ms |
660 KB |
Output is correct |
8 |
Correct |
3 ms |
660 KB |
Output is correct |
9 |
Correct |
3 ms |
660 KB |
Output is correct |
10 |
Correct |
3 ms |
744 KB |
Output is correct |
11 |
Correct |
2 ms |
744 KB |
Output is correct |
12 |
Correct |
2 ms |
744 KB |
Output is correct |
13 |
Correct |
2 ms |
744 KB |
Output is correct |
14 |
Correct |
2 ms |
744 KB |
Output is correct |
15 |
Correct |
2 ms |
744 KB |
Output is correct |
16 |
Correct |
3 ms |
744 KB |
Output is correct |
17 |
Correct |
4 ms |
760 KB |
Output is correct |
18 |
Correct |
4 ms |
760 KB |
Output is correct |
19 |
Correct |
5 ms |
888 KB |
Output is correct |
20 |
Correct |
4 ms |
888 KB |
Output is correct |
21 |
Correct |
3 ms |
888 KB |
Output is correct |
22 |
Correct |
5 ms |
1016 KB |
Output is correct |
23 |
Correct |
4 ms |
1016 KB |
Output is correct |
24 |
Correct |
5 ms |
1016 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
248 KB |
Output is correct |
2 |
Correct |
2 ms |
356 KB |
Output is correct |
3 |
Correct |
3 ms |
560 KB |
Output is correct |
4 |
Correct |
2 ms |
560 KB |
Output is correct |
5 |
Correct |
2 ms |
660 KB |
Output is correct |
6 |
Correct |
3 ms |
660 KB |
Output is correct |
7 |
Correct |
3 ms |
660 KB |
Output is correct |
8 |
Correct |
3 ms |
660 KB |
Output is correct |
9 |
Correct |
3 ms |
660 KB |
Output is correct |
10 |
Correct |
3 ms |
744 KB |
Output is correct |
11 |
Correct |
2 ms |
744 KB |
Output is correct |
12 |
Correct |
2 ms |
744 KB |
Output is correct |
13 |
Correct |
2 ms |
744 KB |
Output is correct |
14 |
Correct |
2 ms |
744 KB |
Output is correct |
15 |
Correct |
2 ms |
744 KB |
Output is correct |
16 |
Correct |
3 ms |
744 KB |
Output is correct |
17 |
Correct |
4 ms |
760 KB |
Output is correct |
18 |
Correct |
4 ms |
760 KB |
Output is correct |
19 |
Correct |
5 ms |
888 KB |
Output is correct |
20 |
Correct |
4 ms |
888 KB |
Output is correct |
21 |
Correct |
3 ms |
888 KB |
Output is correct |
22 |
Correct |
5 ms |
1016 KB |
Output is correct |
23 |
Correct |
4 ms |
1016 KB |
Output is correct |
24 |
Correct |
5 ms |
1016 KB |
Output is correct |
25 |
Correct |
23 ms |
2932 KB |
Output is correct |
26 |
Correct |
66 ms |
7660 KB |
Output is correct |
27 |
Correct |
209 ms |
14952 KB |
Output is correct |
28 |
Correct |
163 ms |
14952 KB |
Output is correct |
29 |
Correct |
138 ms |
14952 KB |
Output is correct |
30 |
Correct |
200 ms |
14952 KB |
Output is correct |
31 |
Correct |
337 ms |
23316 KB |
Output is correct |
32 |
Correct |
327 ms |
23316 KB |
Output is correct |
33 |
Correct |
40 ms |
23316 KB |
Output is correct |
34 |
Correct |
160 ms |
23316 KB |
Output is correct |
35 |
Correct |
204 ms |
36708 KB |
Output is correct |
36 |
Correct |
529 ms |
36828 KB |
Output is correct |
37 |
Correct |
352 ms |
36964 KB |
Output is correct |
38 |
Correct |
448 ms |
36964 KB |
Output is correct |