oj.uz

Submission #893647

# Submission time Handle Problem Language Result Execution time Memory
893647 2023-12-27T08:39:01 Z abcvuitunggio Comparing Plants (IOI20_plants) C++17
0 / 100
 120 ms 22080 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
const int INF=1e9;
struct T{
    int mn,pos;
}st[800001];
T operator +(T a, T b){
    return (a.mn>b.mn?b:a);
}
int n,k,lazy[800001],p[200001],id,l[200001][20],r[200001][20],dl[200001][20],dr[200001][20],pos[200001];
vector <int> a;
void down(int node, int l, int r){
    if (!lazy[node]||l==r)
        return;
    st[node<<1].mn+=lazy[node];
    st[node<<1|1].mn+=lazy[node];
    lazy[node<<1]+=lazy[node];
    lazy[node<<1|1]+=lazy[node];
    lazy[node]=0;
}
void build(int node, int l, int r){
    if (l==r){
        st[node]={a[l],l};
        return;
    }
    int mid=(l+r)>>1;
    build(node<<1,l,mid);
    build(node<<1|1,mid+1,r);
    st[node]=st[node<<1]+st[node<<1|1];
}
void update(int node, int l, int r, int u, int v, int val){
    if (l>v||r<u||u>v)
        return;
    if (l>=u&&r<=v){
        st[node].mn+=val;
        lazy[node]+=val;
        return;
    }
    down(node,l,r);
    int mid=(l+r)>>1;
    update(node<<1,l,mid,u,v,val);
    update(node<<1|1,mid+1,r,u,v,val);
    st[node]=st[node<<1]+st[node<<1|1];
}
T get(int node, int l, int r, int u, int v){
    if (l>v||r<u||u>v)
        return {INF,0};
    if (l>=u&&r<=v)
        return st[node];
    down(node,l,r);
    int mid=(l+r)>>1;
    return get(node<<1,l,mid,u,v)+get(node<<1|1,mid+1,r,u,v);
}
T calc(int j){
    if (j<k)
        return get(1,0,n-1,0,j-1)+get(1,0,n-1,n+j-k+1,n-1);
    else
        return get(1,0,n-1,j-k+1,j-1);
}
void dfs(int i){
    while (!calc(i).mn)
        dfs(calc(i).pos);
    p[i]=id;
    id--;
    if (i<k){
        update(1,0,n-1,0,i-1,-1);
        update(1,0,n-1,n+i-k+1,n-1,-1);
    }
    else
        update(1,0,n-1,i-k+1,i-1,-1);
    update(1,0,n-1,i,i,INF);
}
void init(int K, vector <int> R){
    k=K;
    a=R;
    n=id=a.size();
    build(1,0,n-1);
    while (!st[1].mn)
        dfs(st[1].pos);
    for (int i=0;i<n;i++){
        a[i]=-p[i];
        pos[p[i]]=i;
    }
    build(1,0,n-1);
    for (int j=n;j;j--){
        int i=pos[j];
        update(1,0,n-1,i,i,INF);
        l[i][0]=(calc(i).mn>0?i:calc(i).pos);
        dl[i][0]=(i-l[i][0]+n)%n;
        r[i][0]=(calc(i+k).mn>0?i:calc(i+k).pos);
        dr[i][0]=(r[i][0]-i+n)%n;
    }
    for (int j=1;j<20;j++)
        for (int i=0;i<n;i++){
            l[i][j]=l[l[i][j-1]][j-1];
            dl[i][j]=min(dl[i][j-1]+dl[l[i][j-1]][j-1],INF);
            r[i][j]=r[r[i][j-1]][j-1];
            dr[i][j]=min(dr[i][j-1]+dr[r[i][j-1]][j-1],INF);
        }
}
int check(int x, int y){
    int z=x,dist=(x-y+n)%n;
    for (int i=19;i>=0;i--)
        if (dl[z][i]<dist){
            dist-=dl[z][i];
            z=l[z][i];
        }
    if (dl[z][0]>=dist&&p[z]>p[y])
        return 1;
    z=x,dist=(y-x+n)%n;
    for (int i=19;i>=0;i--)
        if (dr[z][i]<dist){
            dist-=dr[z][i];
            z=r[z][i];
        }
    return (dr[z][0]>=dist&&p[z]>p[y]);
}
int compare_plants(int x, int y){
	return (check(x,y)?1:(check(y,x)?-1:0));
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 12632 KB Output is correct
2 Correct 1 ms 12636 KB Output is correct
3 Correct 1 ms 12636 KB Output is correct
4 Correct 1 ms 12632 KB Output is correct
5 Correct 1 ms 12636 KB Output is correct
6 Correct 73 ms 15444 KB Output is correct
7 Incorrect 120 ms 22080 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 12632 KB Output is correct
2 Correct 1 ms 12636 KB Output is correct
3 Correct 1 ms 12636 KB Output is correct
4 Correct 1 ms 12632 KB Output is correct
5 Correct 1 ms 12636 KB Output is correct
6 Correct 73 ms 15444 KB Output is correct
7 Incorrect 120 ms 22080 KB Output isn't correct
8 Halted 0 ms 0 KB -