oj.uz

Submission #12064

# Submission time Handle Problem Language Result Execution time Memory
12064 2014-12-20T14:41:30 Z dohyun0324 허수아비 (JOI14_scarecrows) C++
15 / 100
 148 ms 14248 KB 
#include<stdio.h>
#include<algorithm>
using namespace std;
int s,c,w,n,w1,w2,top,arr1[200010],arr2[200010],tree[200010],go[200010],cnt[200010];
struct data{
    int x,y;
    bool operator<(const data&r)const{
        return x<r.x;
    }
}a[200010];
struct data5{
    int x,y;
}a2[200010];
struct data2{
    int x,y;
    bool operator<(const data2&r)const{
        return y>r.y;
    }
}b[200010];
struct data3{
    int x,pos;
}st[200010];
struct data4{
    int x,y;
    bool operator<(const data4&r)const{
        return y<r.y;
    }
}p[200010];
void dfs(int x)
{
    if(tree[x]==0){s=x; return;}
    dfs(tree[x]);
    if(c>0) cnt[x]+=cnt[tree[x]]+1;
    tree[x]=s; c++;
}
int pro(int x,int y){
    int i,j,ky=b[(x+y)/2+1].y,r=1,s2=1,dap=0,w1=0,w2=0,w=0;
    for(i=x;i<=y;i++){
        if(a[i].y>ky){
            for(j=s2;j<=w2;j++) go[arr2[j]]=i; s2=w2+1;
            arr1[++w1]=i;
        }
        else arr2[++w2]=i;
    }
    st[0].x=2147483647; top=0;
    for(i=1;i<=w2;i++){
        while(st[top].x<a[arr2[i]].y){
            w++; p[w].x=st[top].pos; p[w].y=a[arr2[i]].x;
            top--;
        }
        top++; st[top].x=a[arr2[i]].y; st[top].pos=arr2[i];
    }
    for(i=1;i<=top;i++){w++; p[w].x=st[i].pos; p[w].y=2147483647;}
    sort(p+1,p+w+1);
    top=0; st[0].x=-1;
    for(j=1;j<=w;j++){
        for(i=r;i<=w1;i++){
            if(a[arr1[i]].x>p[j].y) break;
            while(st[top].x>a[arr1[i]].y){
                tree[st[top].pos]=arr1[i];
                top--;
            }
            top++; st[top].x=a[arr1[i]].y; st[top].pos=arr1[i];
        }
        r=i;
        if(go[p[j].x]>arr1[r-1] || go[p[j].x]==0) continue;
        if(tree[go[p[j].x]]==0){dap++; continue;}
        c=0; dfs(go[p[j].x]); dap+=cnt[go[p[j].x]]+2;
    }
    for(i=1;i<=w1;i++) a2[x+i-1].x=a[arr1[i]].x, a2[x+i-1].y=a[arr1[i]].y;
    for(i=w2;i>=1;i--) a2[y+i-w2].x=a[arr2[i]].x, a2[y+i-w2].y=a[arr2[i]].y;
    for(i=x;i<=y;i++) a[i].x=a2[i].x, a[i].y=a2[i].y;
    for(i=x;i<=y;i++) cnt[i]=0, tree[i]=0, go[i]=0;
    return dap;
}
int divide(int x,int y){
    if(x==y) return 0;
    return pro(x,y)+divide(x,(x+y)/2)+divide((x+y)/2+1,y);
}
int main()
{
    int i,dap;
    scanf("%d",&n);
    for(i=1;i<=n;i++){scanf("%d %d",&a[i].x,&a[i].y); b[i].x=a[i].x; b[i].y=a[i].y;}
    sort(b+1,b+n+1); sort(a+1,a+n+1);
    dap=divide(1,n);
    printf("%d",dap);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
0.0 / 85.0

# Verdict Execution time Memory Grader output
1 Incorrect 148 ms 14248 KB Output isn't correct
2 Halted 0 ms 0 KB -