oj.uz

Submission #115675

# Submission time Handle Problem Language Result Execution time Memory
115675 2019-06-08T14:51:10 Z gs18065 허수아비 (JOI14_scarecrows) C++14
15 / 100
 129 ms 24528 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],temp[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++){
        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<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 5120 KB Output is correct
3 Correct 6 ms 5120 KB Output is correct
4 Correct 6 ms 5120 KB Output is correct
5 Correct 7 ms 5120 KB Output is correct
6 Correct 7 ms 5120 KB Output is correct
7 Correct 7 ms 5120 KB Output is correct
8 Correct 8 ms 5120 KB Output is correct
9 Correct 7 ms 5120 KB Output is correct
10 Correct 7 ms 5120 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
0 / 85.0

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