#include <iostream>
#include <vector>
#include <algorithm>
#define MAX_N 200003
#define INF 2000000000
using namespace std;
int seg[MAX_N*4+1];
bool chk[MAX_N*4+1];
struct S{
int x, y;
};
bool sf1(S a, S b){
return a.x<b.x;
}
bool sf2(S a, S b){
return a.y<b.y;
}
int N;
vector<S> v, v1;
vector<int> v2;
int idx[MAX_N+1];
int mn[MAX_N+1];
int two=1;
void update(int x, int y)
{
while(x>0)
{
seg[x]+=y;
x/=2;
}
}
int sum(int x, int y)
{
int s=0;
while(x<=y)
{
if(x==y)
{
s+=seg[x];
return s;
}
if(x%2)
{
s+=seg[x];
x++;
}
if(!(y%2))
{
s+=seg[y];
y--;
}
x/=2;
y/=2;
}
return s;
}
void update2(int x)
{
while(x>0)
{
chk[x]=1;
x/=2;
}
}
bool sum2(int x, int y)
{
bool s=0;
while(x<=y)
{
if(x==y)
{
s=(s|chk[x]);
return s;
}
if(x%2)
{
s=(s|chk[x]);
x++;
}
if(!(y%2))
{
s=(s|chk[y]);
y--;
}
x/=2;
y/=2;
}
return s;
}
int find_idx(int x)
{
int tmp=x;
int st=x;
int fn=two+N;
while(st<fn)
{
if(st==fn-1)
{
if(sum2(tmp, st))
{
return st;
}
return fn;
}
int mid=(st+fn)/2;
if(sum2(tmp, mid))
{
fn=mid;
}
else
{
st=mid;
}
}
return st;
}
long long ans;
int idx2[MAX_N+1];
int main()
{
scanf("%d", &N);
while(two<=(N+1)) two*=2;
for(int i=1; i<=N; i++)
{
S scan;
scanf("%d%d", &scan.x, &scan.y);
v1.push_back(scan);
}
sort(v1.begin(), v1.end(), sf2);
for(int i=0; i<N; i++)
{
v.push_back({v1[i].x, i});
}
v.push_back({-1, N});
sort(v.begin(), v.end(), sf1);
for(int i=0; i<=N; i++)
{
idx2[v[i].y]=i;
}
v1.clear();
update2(two+N);
for(int i=1; i<=N; i++)
{
idx[i]=find_idx(two+v[i].y+1)-two;
update2(two+v[i].y);
v1.push_back({idx2[idx[i]], i});
}
sort(v1.begin(), v1.end(), sf1);
int ii=0;
while(v1[ii].x==0)
{
ii++;
}
for(int i=1; i<=N; i++)
{
while(v1[ii].x==i)
{
mn[v1[ii].y]=sum(two, two+v[v1[ii].y].y);
ii++;
}
int t=sum(two, two+v[i].y);
ans+=(long long)t;
update(two+v[i].y, 1-t);
update(two+idx[i], mn[i]);
}
cout<<ans;
return 0;
}
Compilation message
scarecrows.cpp: In function 'int main()':
scarecrows.cpp:134:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &N);
~~~~~^~~~~~~~~~
scarecrows.cpp:139:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &scan.x, &scan.y);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
936 KB |
Output is correct |
| 2 |
Incorrect |
10 ms |
936 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
366 ms |
10764 KB |
Output is correct |
| 2 |
Incorrect |
487 ms |
14620 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
