#include <iostream>
#include <vector>
#include <map>
#include <assert.h>
#include <algorithm>
using namespace std;
typedef long long ll;
#define mid (start+end)/2
const int M = 50;
const int N = M*3;
const ll inf=1e15;
ll dp[2][M];
int A[M][3];
int act[M*3];
ll D[M];
map<int,int> mp;
ll TREE[2][N*4];
void build(int idx, int start, int end) {
TREE[0][idx]=TREE[1][idx]=inf;
if(start!=end) {
build(idx*2, start, mid);
build(idx*2+1, mid+1, end);
}
}
void update(int g, int idx, int start, int end, int x, ll v) {
if(start==end) {
TREE[g][idx]=min(TREE[g][idx],v);
// if(g==0 ) cout<<"HOLA UP: "<<start<<" "<<x<<endl;
return;
}
else if(x<=mid) {
update(g, idx*2, start, mid, x, v);
}
else {
update(g, idx*2+1, mid+1, end, x, v);
}
// TREE[g][idx]=min(TREE[g][idx],v);
TREE[g][idx]=min(TREE[g][idx*2],TREE[g][idx*2+1]);
}
ll query(int g, int idx, int start, int end , int a, int b) {
if(start>=a && end<=b) return TREE[g][idx];
else if(start>b || end<a) return inf;
else return min(query(g,idx*2,start,mid,a,b),query(g,idx*2+1,mid+1,end,a,b));
}
int main() {
vector<pair<int, pair<int, int>>> vt;
int m,n,x;scanf("%d %d",&m,&n);
for (int i=1; i<=m; i++) {
scanf("%d",&x);
vt.push_back({x,{i,0}});
scanf("%d",&x);
vt.push_back({x,{i,1}});
scanf("%d",&x);
vt.push_back({x,{i,2}});
scanf("%lld",D+i);
}
vt.push_back({1,{0,3}});
vt.push_back({n,{0,3}});
sort(vt.begin(),vt.end());
int i=0,h,g=0;
while (i<vt.size()) {
h=vt[i].first;
g++;
act[g]=h;
mp[h]=g;
while (i<vt.size() && h==vt[i].first) {
if(vt[i].second.second>=3) {
i++; continue;
}
A[vt[i].second.first][vt[i].second.second]=g;
i++;
}
}
n=mp[n];
// for (int i=1; i<=m; i++) {
// cout<<i<<" : "<<A[i][0]<<" "<<A[i][1]<<" "<<A[i][2]<<endl;
// }
build(1, 1, g);
ll ans=inf;
for (int i=1; i<=m; i++) {
if(A[i][0]==1) {
dp[0][i]=D[i];
}
else {
dp[0][i]=D[i]+query(0,1,1,g,A[i][0],A[i][1]);
// cout<<i<<" : "<<query(0,1,1,g,A[i][0],A[i][1])<<endl;
// cout<<"queried : "<<A[i][0]<<" "<<A[i][1]<<" -- "<<query(0,1,1,g,A[i][0],A[i][1])<<endl;
}
if(A[i][1]==n) {
dp[1][i]=D[i];
}
else {
dp[1][i]=D[i]+query(1,1,1,g,A[i][0],A[i][1]);
// cout<<"queried: 1 : "<<A[i][0]<<" "<<A[i][1]<<" -- "<<query(1,1,1,g,A[i][0],A[i][1])<<endl;
}
ans=min(ans,dp[1][i]+dp[0][i]-D[i]);
update(0, 1, 1, g, A[i][2], dp[0][i]);
// cout<<"UP : "<<A[i][2]<<" -- "<<dp[0][i]<<endl;
update(1, 1, 1, g, A[i][2], dp[1][i]);
// cout<<"UP : 1 "<<A[i][2]<<" -- "<<dp[1][i]<<endl;
// cout<<i<<" "<<dp[0][i]<<" "<<dp[1][i]<<endl;
}
if(ans>=inf) ans=-1;
cout<<ans<<endl;
return 0;
}
Compilation message
pinball.cpp: In function 'int main()':
pinball.cpp:70:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (i<vt.size()) {
^
pinball.cpp:75:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (i<vt.size() && h==vt[i].first) {
^
pinball.cpp:56:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int m,n,x;scanf("%d %d",&m,&n);
^
pinball.cpp:58:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x);
^
pinball.cpp:60:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x);
^
pinball.cpp:62:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&x);
^
pinball.cpp:64:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%lld",D+i);
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
2040 KB |
Output is correct |
| 2 |
Correct |
0 ms |
2040 KB |
Output is correct |
| 3 |
Correct |
0 ms |
2040 KB |
Output is correct |
| 4 |
Correct |
0 ms |
2040 KB |
Output is correct |
| 5 |
Correct |
0 ms |
2040 KB |
Output is correct |
| 6 |
Correct |
0 ms |
2040 KB |
Output is correct |
| 7 |
Correct |
0 ms |
2040 KB |
Output is correct |
| 8 |
Correct |
0 ms |
2040 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
2040 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
2040 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
2212 KB |
Execution killed because of forbidden syscall futex (202) |
| 2 |
Halted |
0 ms |
0 KB |
- |
