oj.uz

Submission #893674

# Submission time Handle Problem Language Result Execution time Memory
893674 2023-12-27T09:00:46 Z abcvuitunggio Comparing Plants (IOI20_plants) C++17
5 / 100
 618 ms 79700 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)%n).mn>0?i:calc((i+k)%n).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],n);
            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],n);
        }
}
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
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12824 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 1 ms 12632 KB Output is correct
4 Correct 1 ms 12632 KB Output is correct
5 Correct 1 ms 12632 KB Output is correct
6 Correct 70 ms 15444 KB Output is correct
7 Correct 116 ms 22100 KB Output is correct
8 Correct 556 ms 79472 KB Output is correct
9 Correct 553 ms 79700 KB Output is correct
10 Correct 547 ms 79544 KB Output is correct
11 Correct 555 ms 79436 KB Output is correct
12 Correct 586 ms 79476 KB Output is correct
13 Correct 601 ms 79512 KB Output is correct
14 Correct 618 ms 79440 KB Output is correct

Subtask #2
0 / 14.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.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 Incorrect 76 ms 17464 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

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

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12824 KB Output is correct
2 Correct 2 ms 12636 KB Output is correct
3 Correct 1 ms 12632 KB Output is correct
4 Correct 1 ms 12632 KB Output is correct
5 Correct 1 ms 12632 KB Output is correct
6 Correct 70 ms 15444 KB Output is correct
7 Correct 116 ms 22100 KB Output is correct
8 Correct 556 ms 79472 KB Output is correct
9 Correct 553 ms 79700 KB Output is correct
10 Correct 547 ms 79544 KB Output is correct
11 Correct 555 ms 79436 KB Output is correct
12 Correct 586 ms 79476 KB Output is correct
13 Correct 601 ms 79512 KB Output is correct
14 Correct 618 ms 79440 KB Output is correct
15 Correct 1 ms 12636 KB Output is correct
16 Correct 1 ms 12636 KB Output is correct
17 Correct 1 ms 12636 KB Output is correct
18 Correct 1 ms 12636 KB Output is correct
19 Incorrect 2 ms 12632 KB Output isn't correct
20 Halted 0 ms 0 KB -