oj.uz

Submission #115676

# Submission time Handle Problem Language Result Execution time Memory
115676 2019-06-08T14:52:34 Z gs18065 허수아비 (JOI14_scarecrows) C++14
15 / 100
 120 ms 19564 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5120 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Correct 6 ms 5120 KB Output is correct
6 Correct 6 ms 5120 KB Output is correct
7 Correct 6 ms 5120 KB Output is correct
8 Correct 6 ms 5120 KB Output is correct
9 Correct 6 ms 4992 KB Output is correct
10 Correct 5 ms 4992 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 5760 KB Output is correct
2 Correct 13 ms 5624 KB Output is correct
3 Correct 12 ms 5632 KB Output is correct
4 Correct 12 ms 5632 KB Output is correct
5 Correct 12 ms 5632 KB Output is correct
6 Correct 13 ms 5632 KB Output is correct
7 Correct 13 ms 5632 KB Output is correct
8 Correct 11 ms 5632 KB Output is correct
9 Correct 12 ms 5632 KB Output is correct
10 Correct 13 ms 5632 KB Output is correct
11 Correct 12 ms 5632 KB Output is correct
12 Correct 11 ms 5632 KB Output is correct

Subtask #3
0 / 85.0

# Verdict Execution time Memory Grader output
1 Runtime error 120 ms 19564 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -