oj.uz

Submission #622704

# Submission time Handle Problem Language Result Execution time Memory
622704 2022-08-04T13:39:36 Z leaked Comparing Plants (IOI20_plants) C++17
27 / 100
 693 ms 49972 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];});

    for(int i=0;i<n;i++) sega.a[i]=1e9;
    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==1e9) 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==1e9) rgt[i][0]=0;
        else rgt[i][0]=(c.s-i+n)%n;

        sega.add(i,i,-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 6576 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 3 ms 6580 KB Output is correct
5 Incorrect 3 ms 6576 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 6484 KB Output is correct
2 Correct 4 ms 6612 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 4 ms 6612 KB Output is correct
5 Correct 3 ms 6612 KB Output is correct
6 Correct 9 ms 6844 KB Output is correct
7 Correct 142 ms 12172 KB Output is correct
8 Correct 6 ms 6716 KB Output is correct
9 Correct 8 ms 6868 KB Output is correct
10 Correct 133 ms 12264 KB Output is correct
11 Correct 124 ms 12140 KB Output is correct
12 Correct 174 ms 12380 KB Output is correct
13 Correct 114 ms 12268 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 4 ms 6612 KB Output is correct
3 Correct 3 ms 6484 KB Output is correct
4 Correct 4 ms 6612 KB Output is correct
5 Correct 3 ms 6612 KB Output is correct
6 Correct 9 ms 6844 KB Output is correct
7 Correct 142 ms 12172 KB Output is correct
8 Correct 6 ms 6716 KB Output is correct
9 Correct 8 ms 6868 KB Output is correct
10 Correct 133 ms 12264 KB Output is correct
11 Correct 124 ms 12140 KB Output is correct
12 Correct 174 ms 12380 KB Output is correct
13 Correct 114 ms 12268 KB Output is correct
14 Correct 190 ms 15328 KB Output is correct
15 Correct 693 ms 49856 KB Output is correct
16 Correct 210 ms 15464 KB Output is correct
17 Correct 679 ms 49856 KB Output is correct
18 Correct 493 ms 49500 KB Output is correct
19 Correct 542 ms 49972 KB Output is correct
20 Correct 654 ms 49916 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 247 ms 11464 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 6484 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 #6
0 / 15.0

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