Submission #115676

#	Time	Username	Problem	Language	Result	Execution time	Memory
115676		gs18065	허수아비 (JOI14_scarecrows)	C++14	15 / 100	120 ms	19564 KiB

scarecrows

#include <bits/stdc++.h>
#define N 200005
using namespace std;
int n,d[N],num,lev,loc[N];
long long int ans;
typedef pair<int,int> pii;

struct emp{
    int s,e,in;
}p[N];
bool cmp1(emp a,emp b){
    return a.s<b.s;
}
vector<int> m[N];
int read_tree(int x,vector<int> &tree){
    int y=0;
    while(x>0){
        y=max(tree[x],y);
        x-=(x&-x);
    }
    return y;
}
void update_tree(int x,int y,vector<int> &tree){
    if(x<=0) return;
    while(x<tree.size()){
        tree[x]=max(tree[x],y);
        x+=(x&-x);
    }
}
void merge_sort(int x,int y,int s,int e){
    vector<int> l,r,tree(y+5,0);
    vector<pii> st;
    int j=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(m[x]));
    for(int i=0;i<y;i++){
        while(j<y&&l[j]<r[i]){
            while(!st.empty()){
                if(st[st.size()-1].second>loc[l[j]]) break;
                st.pop_back();
            }
            st.push_back({l[j],loc[l[j]]});
            j++;
        }
        int t=read_tree(loc[r[i]]-e,tree);
        ans+=(st.end()-upper_bound(st.begin(),st.end(),make_pair(t,0)));
        update_tree(loc[r[i]]-e,r[i],tree);
    }
}
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);
    }
    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++){
        p[i].s=p[i].e;
        p[i].in=i;
    }
    sort(p,p+n,cmp1);
    for(int i=0;i<n;i++){
        d[p[i].in]=i+1;
    }
    while(1){
        num=1<<lev;
        if(num>=n) break;
        lev++;
    }
    for(int i=0;i<n;i++){
        loc[d[i]]=i+1;
    }
    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 'void update_tree(int, int, std::vector<int>&)':
scarecrows.cpp:25:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(x<tree.size()){
           ~^~~~~~~~~~~~
scarecrows.cpp: In function 'int main()':
scarecrows.cpp:62:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
     ~~~~~^~~~~~~~~
scarecrows.cpp:64: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: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 85