#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
//nlog^2n should work...?
const int MX = 1e5+20;
int seg[4*MX], lazy[4*MX];
int sz = 1;
void prop(int x, int lx, int rx) {
seg[x]+=lazy[x];
if(rx-lx!=1) {
lazy[2*x+1]+=lazy[x];
lazy[2*x+2]+=lazy[x];
}
lazy[x] = 0;
}
int numLess(int l, int r, int c, int x=0, int lx=0, int rx=sz) { //gets color with <= appear <=k times
prop(x, lx, rx);
if(lx>=r || rx<=l)
return 0;
int m = (lx+rx)/2;
if(lx>=l && rx<=r) {
if(seg[x]<=c)
return rx-lx;
else {
if(rx-lx==1)
return 0;
prop(2*x+1, lx, m), prop(2*x+2, m, rx);
if(seg[2*x+2]<=c)
return rx-m+numLess(l, r, c, 2*x+1, lx, m);
else
return numLess(l, r, c, 2*x+2, m, rx);
}
}
return numLess(l, r, c, 2*x+1, lx, m)+numLess(l, r, c, 2*x+2, m, rx);
}
void upd(int l, int r, int x=0, int lx=0, int rx=sz) { //add 1 to [l, r)
prop(x, lx, rx);
if(lx>=r || rx<=l) return;
if(lx>=l && rx<=r) {
++seg[x];
if(rx-lx!=1) {
lazy[2*x+1]++;
lazy[2*x+2]++;
}
return;
}
int m = (lx+rx)/2;
upd(l, r, 2*x+1, lx, m), upd(l, r, 2*x+2, m, rx);
seg[x] = max(seg[2*x+1], seg[2*x+2]);
}
vector<int> ret;
void push(int x=0, int lx=0, int rx=sz) {
prop(x, lx, rx);
if(rx-lx==1) {
ret.push_back(seg[x]);
return;
}
int m = (lx+rx)/2;
push(2*x+1, lx, m);
push(2*x+2, m, rx);
}
int main() {
int n; scanf("%d",&n);
while(sz<100005) sz*=2;
vector<pair<int, int>> mast(n);
for(int i=0;i<n;i++)
scanf("%d%d",&mast[i].f,&mast[i].s);
sort(mast.begin(), mast.end());
for(int i=0;i<n;i++) {
int h = mast[i].f;
int k = mast[i].s;
int lo = 0, hi = 100001;
for(int j=0;j<17;j++) {
int mid = (lo+hi)/2;
if(numLess(0, h, mid)>k) {
hi = mid;
}
else {
lo = mid+1;
}
}
int numIn = numLess(0, h, hi-1);
upd(h-numIn, h);
int numLeft = k-numIn;
int start = h-numLess(0, h, hi);
upd(start, start+numLeft);
}
push();
long long ans = 0LL;
//check for overflow
for(int i=0;i<=100000;i++) {
ans+=ret[i]*1LL*(ret[i]-1)/2;
}
printf("%lld\n",ans);
}
Compilation message
sails.cpp: In function 'int main()':
sails.cpp:64:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
64 | int n; scanf("%d",&n);
| ~~~~~^~~~~~~~~
sails.cpp:68:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
68 | scanf("%d%d",&mast[i].f,&mast[i].s);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
3044 KB |
Output is correct |
2 |
Correct |
4 ms |
3044 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
3044 KB |
Output is correct |
2 |
Correct |
4 ms |
3044 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
3044 KB |
Output is correct |
2 |
Correct |
4 ms |
3044 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
3044 KB |
Output is correct |
2 |
Correct |
8 ms |
3044 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
17 ms |
3044 KB |
Output is correct |
2 |
Correct |
15 ms |
3172 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
64 ms |
3044 KB |
Output is correct |
2 |
Correct |
220 ms |
3252 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
220 ms |
3300 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
443 ms |
3556 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
870 ms |
3684 KB |
Output is correct |
2 |
Correct |
878 ms |
3684 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
687 ms |
3812 KB |
Output is correct |
2 |
Correct |
618 ms |
3784 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
987 ms |
4216 KB |
Output is correct |
2 |
Execution timed out |
1099 ms |
2668 KB |
Time limit exceeded |