oj.uz

Submission #12065

# Submission time Handle Problem Language Result Execution time Memory
12065 2014-12-20T14:44:51 Z dohyun0324 허수아비 (JOI14_scarecrows) C++
100 / 100
 268 ms 15028 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];
long long 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++;
}
long long pro(int x,int y){
    int i,j,ky=b[(x+y)/2+1].y,r=1,s2=1,w1=0,w2=0,w=0;
    long long dap=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;
}
long long 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;
    long long dap=0;
    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("%lld",dap);
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
85.0 / 85.0

# Verdict Execution time Memory Grader output
1 Correct 156 ms 15028 KB Output is correct
2 Correct 256 ms 13592 KB Output is correct
3 Correct 172 ms 13592 KB Output is correct
4 Correct 160 ms 13592 KB Output is correct
5 Correct 184 ms 13592 KB Output is correct
6 Correct 204 ms 13592 KB Output is correct
7 Correct 240 ms 13592 KB Output is correct
8 Correct 260 ms 13592 KB Output is correct
9 Correct 164 ms 13592 KB Output is correct
10 Correct 216 ms 13624 KB Output is correct
11 Correct 232 ms 13592 KB Output is correct
12 Correct 252 ms 13592 KB Output is correct
13 Correct 268 ms 13592 KB Output is correct
14 Correct 164 ms 13592 KB Output is correct
15 Correct 240 ms 13592 KB Output is correct
16 Correct 248 ms 13592 KB Output is correct
17 Correct 136 ms 13592 KB Output is correct
18 Correct 244 ms 13592 KB Output is correct
19 Correct 240 ms 13592 KB Output is correct
20 Correct 240 ms 13592 KB Output is correct