| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 332915 |
2020-12-04T01:41:06 Z |
vkgainz |
Sails (IOI07_sails) |
C++17 |
|
254 ms |
3812 KB |
#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 get(int i, int x=0, int lx=0, int rx=sz) { //smallest color which has occurence strictly greater than k times
prop(x, lx, rx);
if(rx-lx==1)
return seg[x];
int m = (lx+rx)/2;
if(i<m)
return get(i, 2*x+1, lx, m);
else
return get(i, 2*x+2, m, rx);
}
int numLess(int l, int r, int c, int x=0, int lx=0, int rx=sz) { //gets color with <= appear <=k times
if(lx>=r || rx<=l)
return 0;
prop(x, lx, rx);
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 col = get(h-k);
if(col==0) {
upd(0, h);
}
else {
int cmp = get(h-k-1);
if(cmp==col) {
int x = numLess(0, h, col-1);
upd(h-x, h);
int left = k-x;
int y = numLess(0, h, col);
upd(h-y, h-y+left);
}
else {
upd(h-k, h);
}
}
}
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:74:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
74 | int n; scanf("%d",&n);
| ~~~~~^~~~~~~~~
sails.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
78 | scanf("%d%d",&mast[i].f,&mast[i].s);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
3044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
3044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
3044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
3044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
3044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
23 ms |
3044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
68 ms |
3300 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
121 ms |
3556 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
227 ms |
3572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
212 ms |
3684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
254 ms |
3812 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
