oj.uz

Submission #622740

# Submission time Handle Problem Language Result Execution time Memory
622740 2022-08-04T14:04:49 Z leaked Comparing Plants (IOI20_plants) C++17
27 / 100
 834 ms 48076 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<<' '<<t[v].f<<' '<<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];

    vec<int> ids(n);iota(all(ids),0);
    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=0;i<n;i++) cout<<ht[i]<<' '<<lft[i][0]<<' '<<rgt[i][0]<<endl;
//    cout<<endl;

    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;
}


/*
10 2 1
0 1 1 0 1 0 1 0 0 1
7 9
*/

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 6504 KB Output is correct
5 Correct 3 ms 6484 KB Output is correct
6 Incorrect 172 ms 10420 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6580 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6584 KB Output is correct
5 Correct 4 ms 6612 KB Output is correct
6 Correct 8 ms 6868 KB Output is correct
7 Correct 123 ms 12116 KB Output is correct
8 Correct 6 ms 6716 KB Output is correct
9 Correct 7 ms 6868 KB Output is correct
10 Correct 122 ms 12096 KB Output is correct
11 Correct 121 ms 12012 KB Output is correct
12 Correct 161 ms 12212 KB Output is correct
13 Correct 117 ms 12144 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6484 KB Output is correct
2 Correct 3 ms 6580 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6584 KB Output is correct
5 Correct 4 ms 6612 KB Output is correct
6 Correct 8 ms 6868 KB Output is correct
7 Correct 123 ms 12116 KB Output is correct
8 Correct 6 ms 6716 KB Output is correct
9 Correct 7 ms 6868 KB Output is correct
10 Correct 122 ms 12096 KB Output is correct
11 Correct 121 ms 12012 KB Output is correct
12 Correct 161 ms 12212 KB Output is correct
13 Correct 117 ms 12144 KB Output is correct
14 Correct 175 ms 15012 KB Output is correct
15 Correct 834 ms 47984 KB Output is correct
16 Correct 201 ms 14932 KB Output is correct
17 Correct 819 ms 48020 KB Output is correct
18 Correct 540 ms 48068 KB Output is correct
19 Correct 602 ms 47944 KB Output is correct
20 Correct 817 ms 48076 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 4 ms 6484 KB Output is correct
3 Incorrect 202 ms 11492 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6580 KB Output is correct
2 Correct 4 ms 6484 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Incorrect 3 ms 6484 KB Output isn't correct
5 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 6504 KB Output is correct
5 Correct 3 ms 6484 KB Output is correct
6 Incorrect 172 ms 10420 KB Output isn't correct
7 Halted 0 ms 0 KB -