oj.uz

Submission #622711

# Submission time Handle Problem Language Result Execution time Memory
622711 2022-08-04T13:42:42 Z leaked Comparing Plants (IOI20_plants) C++17
27 / 100
 706 ms 46208 KB 
#include <bits/stdc++.h>

#define f first
#define s second
#define vec vector
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pw(x) (1LL<<(x))
#define sz(x) (int)(x).size()
#define m_p make_pair
#define fast_ioi ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
template<class T> bool umin(T &a,const T &b){return (a>b?a=b,1:0);}
template<class T> bool umax(T &a,const T &b){return (a<b?a=b,1:0);}

const int N=2e5+1;

struct segtree{
    pii t[4*N];
    int p[4*N];
    vec<int> a;

    void push(int v,int tl,int tr){
        for(auto &u : {v<<1,v<<1|1}){
            t[u].f+=p[v];
            p[u]+=p[v];
        }
        p[v]=0;
    }

    void build(int v,int tl,int tr){
        p[v]=0;
        if(tl==tr){
            t[v]={a[tl],tl};
        }
        else{
            int tm=(tl+tr)>>1;
            build(v<<1,tl,tm);build(v<<1|1,tm+1,tr);
            t[v]=min(t[v<<1],t[v<<1|1]);
        }
    }

    void add(int l,int r,int x,int v,int tl,int tr){
        if(tl>=l&&tr<=r){
            t[v].f+=x;p[v]+=x;
//            cout<<tl<<' '<<tr<<' '<<x<<endl;
            return;
        }
        if(tl>r||tr<l) return;
        int tm=(tl+tr)>>1;push(v,tl,tr);
        add(l,r,x,v<<1,tl,tm);add(l,r,x,v<<1|1,tm+1,tr);
        t[v]=min(t[v<<1],t[v<<1|1]);
    }
    pii get(int l,int r,int v,int tl,int tr){
        if(tl>=l&&tr<=r) return t[v];
        if(tl>r||tr<l) return m_p(1e9,-1);
        int tm=(tl+tr)>>1;push(v,tl,tr);
        return min(get(l,r,v<<1,tl,tm),get(l,r,v<<1|1,tm+1,tr));
    }
}sega;

int n,k;

int h[N],it=0;

int _find(int i){
    pii c;
    if((i-k+1)<0){
        int r=k-(i+1);
        c=sega.get(n-r,n-1,1,0,n-1);
        if(c.f>0){
            c=sega.get(0,i-1,1,0,n-1);
        }
    }
    else{
        c=sega.get(i-k+1,i-1,1,0,n-1);
    }
    return (c.f<=0?c.s:-1);
}

int ht[N];

void place(int i){
    sega.add(i,i,1e9,1,0,n-1);
    int j=_find(i);
//    cout<<"PLACE "<<i<<endl;
    while(j!=-1){
        place(j);
        j=_find(i);
    }
    ht[i]=it++;

    if((i-k+1)<0){
        int r=k-(i+1);
        sega.add(n-r,n-1,-1,1,0,n-1);
        sega.add(0,i,-1,1,0,n-1);
    }
    else{
        sega.add(i-k+1,i,-1,1,0,n-1);
    }
}


int lft[N][20],rgt[N][20];


void init(int k, std::vector<int> r){
    n=sz(r);::k=k;
    sega.a=r;
    sega.build(1,0,n-1);
    fill(ht,ht+n,-1);
    while(1){
        pii c=sega.t[1];
        if(c.f>0){
            break;
        }
        int j=c.s;
        place(j);
    }

    for(int i=0;i<n;i++) ht[i]=n-ht[i]+1;

    vec<int> ids(n);
    sort(all(ids),[&](int i,int j){return ht[i]<ht[j];});

    const int inf=(int)(1e9)-1;

    for(int i=0;i<n;i++) sega.a[i]=inf;

    sega.build(1,0,n-1);

    for(auto &i : ids){
        pii c=((i+1)>=k?sega.get(i-k+1,i-1,1,0,n-1):min(sega.get(0,i-1,1,0,n-1),sega.get(n-(k-(i+1)),n-1,1,0,n-1)));

        if(c.f>=inf) lft[i][0]=0;
        else lft[i][0]=(i+n-c.s)%n;

        c=(i+k-1<n?sega.get(i+1,i+k-1,1,0,n-1):min(sega.get(i+1,n-1,1,0,n-1),sega.get(0,k-(n-i)-1,1,0,n-1)));
        if(c.f>=inf) rgt[i][0]=0;
        else rgt[i][0]=(c.s-i+n)%n;

        sega.add(i,i,-inf-ht[i],1,0,n-1);
    }

    for(int i=1;i<20;i++){
        for(int j=0;j<n;j++){
            lft[j][i]=lft[j][i]+lft[(j+n-lft[j][i])%n][i];
            rgt[j][i]=rgt[j][i]+rgt[(j+rgt[j][i])%n][i];
            if(lft[j][i]>n) lft[j][i]=0;
            if(rgt[j][i]>n) rgt[j][i]=0;
        }
    }
}
int compare_plants(int x, int y){
    int z=x;
    for(int i=19;i>=0;i--){
        if(rgt[z][i]<(y-z+n)%n)
            z=(z+rgt[z][i])%n;
    }
    if(ht[z]>ht[y] && (y-z+n)%n<k) return 1;

    z=y;
    for(int i=19;i>=0;i--){
        if(rgt[z][i]<(x-z+n)%n)
            z=(z+rgt[z][i])%n;
    }
    if(ht[z]>ht[x] && (x-z+n)%n<k) return -1;

    z=y;
    for(int i=19;i>=0;i--){
        if(lft[z][i]<(z-x+n)%n)
            z=(z-lft[z][i]+n)%n;
    }
    if(ht[z]>ht[x] && (z-x+n)%n<k) return -1;

    z=x;

    for(int i=19;i>=0;i--){
        if(lft[z][i]<(z-y+n)%n)
            z=(z-lft[z][i]+n)%n;
    }

    if(ht[z]>ht[y] && (z-y+n)%n<k) return 1;

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Incorrect 3 ms 6484 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6476 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 3 ms 6612 KB Output is correct
6 Correct 8 ms 6832 KB Output is correct
7 Correct 126 ms 10360 KB Output is correct
8 Correct 6 ms 6612 KB Output is correct
9 Correct 7 ms 6796 KB Output is correct
10 Correct 127 ms 10360 KB Output is correct
11 Correct 133 ms 10284 KB Output is correct
12 Correct 162 ms 10408 KB Output is correct
13 Correct 119 ms 10368 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6476 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Correct 3 ms 6612 KB Output is correct
6 Correct 8 ms 6832 KB Output is correct
7 Correct 126 ms 10360 KB Output is correct
8 Correct 6 ms 6612 KB Output is correct
9 Correct 7 ms 6796 KB Output is correct
10 Correct 127 ms 10360 KB Output is correct
11 Correct 133 ms 10284 KB Output is correct
12 Correct 162 ms 10408 KB Output is correct
13 Correct 119 ms 10368 KB Output is correct
14 Correct 202 ms 13112 KB Output is correct
15 Correct 688 ms 46208 KB Output is correct
16 Correct 179 ms 13184 KB Output is correct
17 Correct 706 ms 46120 KB Output is correct
18 Correct 549 ms 46144 KB Output is correct
19 Correct 593 ms 46192 KB Output is correct
20 Correct 700 ms 46120 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Incorrect 209 ms 9712 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Incorrect 4 ms 6484 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6532 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Incorrect 3 ms 6484 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6484 KB Output is correct
5 Incorrect 3 ms 6484 KB Output isn't correct
6 Halted 0 ms 0 KB -