| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 975572 |
2024-05-05T13:34:29 Z |
PM1 |
Pinball (JOI14_pinball) |
C++17 |
|
4 ms |
6492 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mxn=1e5+5,sz=(1<<20);
ll n,m,g[mxn][4];
vector<int>v;
struct segment{
ll mn[sz];
void up(int id,int L,int R,int l,ll x,bool w){
if(L+1==R){
if(w==1 || mn[id]>x){
mn[id]=x;
}
return;
}
int mid=(L+R)/2;
if(l<mid)
up(id*2,L,mid,l,x,w);
else
up(id*2+1,mid,R,l,x,w);
if(mn[id*2]<mn[id*2+1])
mn[id]=mn[id*2];
else
mn[id]=mn[id*2+1];
}
ll get(int id,int L,int R,int l,int r){
if(L==l && R==r){
return mn[id];
}
ll x1=1e16,x2=1e16;
int mid=(L+R)/2;
if(l<mid)
x1=get(id*2,L,mid,l,min(r,mid));
if(r>mid)
x2=get(id*2+1,mid,R,max(l,mid),r);
return min(x1,x2);
}
}seg[3];
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>m>>n;
for(int i=1;i<=m;i++){
for(int j=0;j<3;j++){
cin>>g[i][j];
v.push_back(g[i][j]);
}
cin>>g[i][3];
}
sort(v.begin(),v.end());
v.resize(unique(v.begin(),v.end())-v.begin());
for(int i=1;i<=m;i++){
for(int j=0;j<3;j++){
int x=lower_bound(v.begin(),v.end(),g[i][j])-v.begin();
g[i][j]=x;
}
}
if(v.back()!=n){
cout<<-1;
return 0;
}
n=v.size()-1;
for(int i=0;i<=n;i++){
for(int j=0;j<3;j++){
seg[j].up(1,0,n+1,i,1e16,1);
}
}
seg[0].up(1,0,n+1,0,0,1);
seg[1].up(1,0,n+1,n,0,1);
for(int i=1;i<=m;i++){
ll x=seg[0].get(1,0,n+1,g[i][0],g[i][1]+1);
ll y=seg[1].get(1,0,n+1,g[i][0],g[i][1]+1);
//cout<<x<<" "<<y<<'\n';
seg[2].up(1,0,n+1,g[i][2],x+y+g[i][3],0);
seg[0].up(1,0,n+1,g[i][2],x+g[i][3],0);
seg[1].up(1,0,n+1,g[i][2],y+g[i][3],0);
}
ll ans=seg[2].get(1,0,n+1,0,n+1);
if(ans==1e16)
ans=-1;
cout<<ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6488 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 5 |
Correct |
3 ms |
6492 KB |
Output is correct |
| 6 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 7 |
Incorrect |
4 ms |
6492 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6488 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 5 |
Correct |
3 ms |
6492 KB |
Output is correct |
| 6 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 7 |
Incorrect |
4 ms |
6492 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6488 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 5 |
Correct |
3 ms |
6492 KB |
Output is correct |
| 6 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 7 |
Incorrect |
4 ms |
6492 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6488 KB |
Output is correct |
| 2 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 3 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 4 |
Correct |
1 ms |
6492 KB |
Output is correct |
| 5 |
Correct |
3 ms |
6492 KB |
Output is correct |
| 6 |
Correct |
2 ms |
6492 KB |
Output is correct |
| 7 |
Incorrect |
4 ms |
6492 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
