Submission #115561

#	Time	Username	Problem	Language	Result	Execution time	Memory
115561		gs18065	허수아비 (JOI14_scarecrows)	C++14	0 / 100	638 ms	22840 KiB

scarecrows

#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;
        if(root[l[k2-1]]==t1){
            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 (stderr)

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);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 85