#include <bits/stdc++.h>
#define N 200005
using namespace std;
int n,d[N],num,lev,val[N],root[N],loc[N],pre[N];
long long int ans;
struct emp{
int s,e,in;
}p[N],temp[N];
bool cmp1(emp a,emp b){
return a.s<b.s;
}
vector<int> m[N];
int read_tree(int x,int tree[]){
int y=0;
while(x<=N){
y=max(tree[x],y);
x+=(x&-x);
}
return y;
}
void update_tree(int x,int y,int tree[]){
while(x>0){
tree[x]=max(tree[x],y);
x-=(x&-x);
}
}
int read(int x,int y,int tre[]){
int k=0;
while(x>0){
if(tre[x]<y) k=max(k,tre[x]);
x-=(x&-x);
}
return k;
}
void update(int x,int y,int tre[]){
while(x<=N){
tre[x]=max(y,tre[x]);
x+=(x&-x);
}
return;
}
void merge_sort(int x,int y,int s,int e){
vector<int> md,l,r;
int ttree[N+5]={0,},rtree[N+5]={0,};
for(int i=0;i<y;i++){
l.push_back(m[x-1][s+i]);
r.push_back(m[x-1][e+i]);
}
merge(l.begin(),l.end(),r.begin(),r.end(),back_inserter(md));
for(int i=0;i<2*y;i++){
m[x].push_back(md[i]);
}
for(int i=0;i<y;i++){
loc[d[s+i]]=i+1;
}
for(int i=0;i<y;i++){
int k=read_tree(loc[l[i]],ttree);
if(k==0){
root[l[i]]=l[i];
val[l[i]]=1;
}
else{
root[l[i]]=root[k];
val[l[i]]=val[k]+1;
}
update_tree(loc[l[i]],l[i],ttree);
}
for(int i=0;i<y;i++){
int k=read(i+1,d[e+i],rtree);
pre[d[e+i]]=k;
update(i+1,d[e+i],rtree);
}
for(int i=0;i<y;i++){
int k1=lower_bound(l.begin(),l.end(),r[i])-l.begin();
if(k1==0) continue;
ans+=val[l[k1-1]];
int t1=root[l[k1-1]];
int t2=pre[r[i]];
if(t2<=0) continue;
int k2=lower_bound(l.begin(),l.end(),t2)-l.begin();
if(k2==0) continue;
ans-=val[l[k2-1]];
}
}
void make_mst(int x,int y){
if(x>lev)return;
for(int i=0;i<num/(2*y);i++){
merge_sort(x,y,2*i*y,(2*i+1)*y);
}
for(int i=1;i<=n;i++){
root[i]=0;
val[i]=0;
pre[i]=0;
loc[i]=0;
}
make_mst(x+1,y*2);
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d %d",&p[i].s,&p[i].e);
}
sort(p,p+n,cmp1);
for(int i=0;i<n;i++){
temp[i].s=p[i].e;
temp[i].in=i;
}
sort(temp,temp+n,cmp1);
for(int i=0;i<n;i++){
d[temp[i].in]=i+1;
}
while(1){
num=1<<lev;
if(num>=n) break;
lev++;
}
for(int i=0;i<num;i++){
m[0].push_back(d[i]);
}
make_mst(1,1);
printf("%lld",ans);
}
Compilation message
scarecrows.cpp: In function 'void merge_sort(int, int, int, int)':
scarecrows.cpp:78:13: warning: unused variable 't1' [-Wunused-variable]
int t1=root[l[k1-1]];
^~
scarecrows.cpp: In function 'int main()':
scarecrows.cpp:102:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
scarecrows.cpp:104:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&p[i].s,&p[i].e);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
44 ms |
6656 KB |
Output is correct |
| 2 |
Incorrect |
47 ms |
6656 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
610 ms |
7416 KB |
Output is correct |
| 2 |
Incorrect |
604 ms |
7656 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
131 ms |
25160 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
