#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int m, n;
int a[100100], b[100100], c[100100];
ll d[100100];
vector<int> comp;
ll INF = 1LL<<50;
ll tree[1050000];
ll l[100100], r[100100];
int key = 524288;
void upd(int idx, ll val) {
idx+=key;
while(idx>0) {
tree[idx] = min(tree[idx],val);
idx>>=1;
}
}
ll getv(int s, int e) {
ll mini = INF;
s+=key;e+=key;
while(s<=e) {
if (s&1) mini = min(mini,tree[s++]);
if (~e&1) mini = min(mini,tree[e--]);
s>>=1;e>>=1;
}
return mini;
}
int main() {
int i;
scanf("%d%d",&m,&n);
for (i=0;i<m;i++) scanf("%d%d%d%lld",&a[i],&b[i],&c[i],&d[i]);
comp.push_back(1); comp.push_back(n);
for (i=0;i<m;i++) {
comp.push_back(a[i]);
comp.push_back(b[i]);
comp.push_back(c[i]);
}
sort(comp.begin(),comp.end());
comp.erase(unique(comp.begin(),comp.end()),comp.end());
for (i=0;i<m;i++) {
a[i] = lower_bound(comp.begin(),comp.end(),a[i])-comp.begin();
b[i] = lower_bound(comp.begin(),comp.end(),b[i])-comp.begin();
c[i] = lower_bound(comp.begin(),comp.end(),c[i])-comp.begin();
}
for (i=0;i<key*2;i++) tree[i] = INF;
upd((int)comp.size()-1,0);
for (i=0;i<m;i++) {
r[i] = getv(a[i],b[i])+d[i];
upd(c[i],r[i]);
}
for (i=0;i<key*2;i++) tree[i] = INF;
upd(0,0);
for (i=0;i<m;i++) {
l[i] = getv(a[i],b[i])+d[i];
upd(c[i],l[i]);
}
ll mini = INF;
for (i=0;i<m;i++) {
if (l[i]>=INF||r[i]>=INF) continue;
if (mini>l[i]+r[i]-d[i]) mini=l[i]+r[i]-d[i];
}
if (mini==INF) printf("-1\n");
else printf("%lld\n",mini);
return 0;
}
Compilation message
pinball.cpp: In function 'int main()':
pinball.cpp:38:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d",&m,&n);
^
pinball.cpp:39:66: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for (i=0;i<m;i++) scanf("%d%d%d%lld",&a[i],&b[i],&c[i],&d[i]);
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
13744 KB |
Output is correct |
2 |
Correct |
3 ms |
13744 KB |
Output is correct |
3 |
Correct |
0 ms |
13744 KB |
Output is correct |
4 |
Correct |
3 ms |
13744 KB |
Output is correct |
5 |
Correct |
3 ms |
13744 KB |
Output is correct |
6 |
Correct |
0 ms |
13744 KB |
Output is correct |
7 |
Correct |
0 ms |
13744 KB |
Output is correct |
8 |
Correct |
0 ms |
13744 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
13744 KB |
Output is correct |
2 |
Correct |
0 ms |
13744 KB |
Output is correct |
3 |
Correct |
6 ms |
13744 KB |
Output is correct |
4 |
Correct |
0 ms |
13744 KB |
Output is correct |
5 |
Correct |
0 ms |
13744 KB |
Output is correct |
6 |
Correct |
6 ms |
13744 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
13744 KB |
Output is correct |
2 |
Correct |
0 ms |
13744 KB |
Output is correct |
3 |
Correct |
6 ms |
13744 KB |
Output is correct |
4 |
Correct |
3 ms |
13744 KB |
Output is correct |
5 |
Correct |
3 ms |
13744 KB |
Output is correct |
6 |
Correct |
6 ms |
13744 KB |
Output is correct |
7 |
Correct |
3 ms |
13744 KB |
Output is correct |
8 |
Correct |
0 ms |
13744 KB |
Output is correct |
9 |
Correct |
0 ms |
13744 KB |
Output is correct |
10 |
Correct |
6 ms |
13744 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
23 ms |
14016 KB |
Output is correct |
2 |
Correct |
56 ms |
14596 KB |
Output is correct |
3 |
Correct |
156 ms |
15364 KB |
Output is correct |
4 |
Correct |
136 ms |
16900 KB |
Output is correct |
5 |
Correct |
96 ms |
15364 KB |
Output is correct |
6 |
Correct |
143 ms |
16900 KB |
Output is correct |
7 |
Correct |
199 ms |
16900 KB |
Output is correct |
8 |
Correct |
193 ms |
16900 KB |
Output is correct |
9 |
Correct |
19 ms |
14212 KB |
Output is correct |
10 |
Correct |
86 ms |
15364 KB |
Output is correct |
11 |
Correct |
143 ms |
16900 KB |
Output is correct |
12 |
Correct |
209 ms |
16900 KB |
Output is correct |
13 |
Correct |
179 ms |
16900 KB |
Output is correct |
14 |
Correct |
176 ms |
16900 KB |
Output is correct |