# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
837590 |
2023-08-25T12:32:02 Z |
Andrey |
Sails (IOI07_sails) |
C++14 |
|
162 ms |
25944 KB |
#include<bits/stdc++.h>
using namespace std;
vector<long long> seg(1000001);
vector<long long> sb(1000001);
vector<long long> big(1000001);
long long yo;
void upd(long long l, long long r, long long ql, long long qr, long long x, long long br) {
if(l == ql && r == qr) {
seg[x]+=br;
big[x]+=br;
sb[x]+=br*(r-l+1);
return;
}
long long m = (l+r)/2;
if(qr <= m) {
upd(l,m,ql,qr,x*2+1,br);
}
else if(ql > m) {
upd(m+1,r,ql,qr,x*2+2,br);
}
else {
upd(l,m,ql,m,x*2+1,br);
upd(m+1,r,m+1,qr,x*2+2,br);
}
big[x] = max(big[x*2+1],big[x*2+2])+seg[x];
sb[x] = sb[x*2+1]+sb[x*2+2]+seg[x]*(r-l+1);
}
long long calc(long long l, long long r, long long ql, long long qr, long long x, long long br) {
if(l == ql && r == qr) {
return sb[x]+br*(r-l+1);
}
long long m = (l+r)/2;
if(qr <= m) {
return calc(l,m,ql,qr,x*2+1,br+seg[x]);
}
else if(ql > m) {
return calc(m+1,r,ql,qr,x*2+2,br+seg[x]);
}
else {
return calc(l,m,ql,m,x*2+1,br+seg[x])+calc(m+1,r,m+1,qr,x*2+2,br+seg[x]);
}
}
long long banana(long long a, long long l, long long r, long long x, long long br) {
if(l == r) {
return l;
}
long long m = (l+r)/2;
br+=seg[x];
if(br+big[x*2+2] < a || m+1 > yo) {
return banana(a,l,m,x*2+1,br);
}
else {
return banana(a,m+1,r,x*2+2,br);
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long long n,a,b,ans = 0;
cin >> n;
vector<pair<long long,long long>> haha(0);
vector<long long> yay(0);
for(long long i = 0; i < n; i++) {
cin >> a >> b;
haha.push_back({a,b});
}
sort(haha.begin(),haha.end());
upd(0,200000,0,0,0,1000000);
for(long long i = 0; i < n; i++) {
a = haha[i].first;
b = haha[i].second;
yo = a;
ans+=calc(0,200000,a-b+1,a,0,0);
long long c = calc(0,200000,a-b+1,a-b+1,0,0);
long long p = banana(c,0,200000,0,0);
if(p+1 < a) {
upd(0,200000,p+1,a,0,1);
}
long long p1 = banana(c+1,0,200000,0,0);
if(p1+1 <= p1+b-(a-p)) {
upd(0,200000,p1+1,p1+b-(a-p),0,1);
}
}
cout << ans;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
10 ms |
23764 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
23764 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
23764 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
9 ms |
23764 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
23892 KB |
Output is correct |
2 |
Correct |
9 ms |
23764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
23 ms |
24068 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
58 ms |
24452 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
86 ms |
24916 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
125 ms |
25936 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
147 ms |
25928 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
162 ms |
25944 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |