oj.uz

Submission #721264

# Submission time Handle Problem Language Result Execution time Memory
721264 2023-04-10T15:13:00 Z bin9638 Comparing Plants (IOI20_plants) C++17
30 / 100
 2338 ms 229520 KB 
#include <bits/stdc++.h>

#ifndef SKY
#include "plants.h"
#endif // SKY

using namespace std;

#define N 1000010
#define ll long long
#define fs first
#define sc second
#define ii pair<int,int>
#define pb push_back

int dem,k,n,h[N],a[N],pre[N][21],nxt[N][21],dis_pre[N][21],dis_nxt[N][21],LOG;

struct IT
{
    struct node
    {
        ii min_val,max_val;
        int t=0;
    }ST[N*4];

    void down(int id)
    {
        ST[id*2].min_val.fs+=ST[id].t;
        ST[id*2].max_val.fs+=ST[id].t;
        ST[id*2].t+=ST[id].t;
        ST[id*2+1].min_val.fs+=ST[id].t;
        ST[id*2+1].max_val.fs+=ST[id].t;
        ST[id*2+1].t+=ST[id].t;
        ST[id].t=0;
    }

    void update(int id,int l,int r,int i,ii val)
    {
        if(l>i||r<i)
            return;
        if(l==r)
        {
            ST[id].min_val=ST[id].max_val=val;
            return;
        }
        down(id);
        int mid=(l+r)/2;
        update(id*2,l,mid,i,val);
        update(id*2+1,mid+1,r,i,val);
        ST[id].min_val=min(ST[id*2].min_val,ST[id*2+1].min_val);
        ST[id].max_val=max(ST[id*2].max_val,ST[id*2+1].max_val);
    }

    void them(int id,int l,int r,int u,int v,int val)
    {
        if(l>r||l>v||r<u)
            return;
        if(l>=u&&r<=v)
        {
            ST[id].t+=val;
            ST[id].min_val.fs+=val;
            ST[id].max_val.fs+=val;
            return;
        }
        down(id);
        int mid=(l+r)/2;
        them(id*2,l,mid,u,v,val);
        them(id*2+1,mid+1,r,u,v,val);
        ST[id].min_val=min(ST[id*2].min_val,ST[id*2+1].min_val);
        ST[id].max_val=max(ST[id*2].max_val,ST[id*2+1].max_val);
    }

    ii get_min(int id,int l,int r,int u,int v)
    {
        if(l>v||r<u)
            return {1e9,-1};
        if(l>=u&&r<=v)
            return ST[id].min_val;
        down(id);
        int mid=(l+r)/2;
        return min(get_min(id*2,l,mid,u,v),get_min(id*2+1,mid+1,r,u,v));
    }

    ii get_max(int id,int l,int r,int u,int v)
    {
        if(l>v||r<u)
            return {-1e9,-1};
        if(l>=u&&r<=v)
            return ST[id].max_val;
        down(id);
        int mid=(l+r)/2;
        return max(get_max(id*2,l,mid,u,v),get_max(id*2+1,mid+1,r,u,v));
    }
}T;

void build(int i)
{
    while(T.get_min(1,1,n*2,i+1+n-k+1,i+1+n-1).fs==0)
    {
        build(T.get_min(1,1,n*2,i+1+n-k+1,i+1+n-1).sc);
    }
    T.them(1,1,n*2,i+1+n-k+1,i+1+n-1,-1);
    if(i-k+1>=0)
    {
        T.them(1,1,n*2,i+1-k+1,i+1-1,-1);
    }else
    {
        T.them(1,1,n*2,1,i+1-1,-1);
        T.them(1,1,n*2,n*2-(k-i-2),n*2,-1);
    }
    T.update(1,1,n*2,i+1,{1e9,i});
    T.update(1,1,n*2,i+n+1,{1e9,i});
    h[i]=--dem;
}

void init(int cc, vector<int> r)
{
	k=cc;
	n=r.size();
	for(int i=0;i<n;i++)
    {
        a[i]=r[i];
        T.update(1,1,n*2,i+1,{a[i],i});
        T.update(1,1,n*2,i+n+1,{a[i],i});
    }
    dem=n;
    while(T.get_min(1,1,n*2,1,n*2).fs==0)
    {
        build(T.get_min(1,1,n*2,1,n*2).sc);
    }
 //   for(int i=0;i<n;i++)cout<<h[i]<<" ";
    for(int i=0;i<n;i++)
    {
        T.update(1,1,n*2,i+1,{-1e9,-1});
        T.update(1,1,n*2,i+n+1,{-1e9,-1});
    }
    vector<ii>s;
    for(int i=0;i<n;i++)
        s.pb({h[i],i});
    sort(s.begin(),s.end());
    memset(pre,-1,sizeof(pre));
    memset(nxt,-1,sizeof(nxt));
    for(auto cc:s)
    {
        int i=cc.sc;
        pre[i][0]=T.get_max(1,1,n*2,i+1+n-k+1,i+1+n-1).sc;
        nxt[i][0]=T.get_max(1,1,n*2,i+1+1,i+1+k-1).sc;
        int vt=T.get_max(1,1,n*2,i+1+n-k+1,i+1+n-1).sc;
        if(vt!=-1)
        {
            dis_pre[i][0]=(vt<=i ? i-vt :i+n-vt);
        }
        vt=T.get_max(1,1,n*2,i+1+1,i+1+k-1).sc;
        if(vt!=-1)
        {
            dis_nxt[i][0]=(vt>=i ? vt-i : vt+n-i);
        }
        T.update(1,1,n*2,i+1,cc);
        T.update(1,1,n*2,i+n+1,cc);
        //cout<<i<<" "<<pre[i][0]<<" "<<nxt[i][0]<<endl;
    }
    LOG=log2(n);
    for(int k=1;k<=LOG;k++)
        for(int i=0;i<n;i++)
        {
            pre[i][k]=(pre[i][k-1]==-1 ? -1 : pre[pre[i][k-1]][k-1]);
            nxt[i][k]=(nxt[i][k-1]==-1 ? -1 :nxt[nxt[i][k-1]][k-1]);
            dis_pre[i][k]=(pre[i][k-1]==-1 ? 1e9 : dis_pre[i][k-1]+dis_pre[pre[i][k-1]][k-1]);
            dis_nxt[i][k]=(nxt[i][k-1]==-1 ? 1e9 : dis_nxt[i][k-1]+dis_nxt[nxt[i][k-1]][k-1]);
        }
}

bool check(int x,int y)
{
    LOG=log2(n);
    if(x<y)
    {
        int vt=x,dis=x+n-y;
        for(int k=LOG;k>=0;k--)
            if(pre[vt][k]!=-1&&dis_pre[vt][k]<=dis)
            {
                dis-=dis_pre[vt][k];
                vt=pre[vt][k];
            }
        if(dis<=k-1&&h[vt]>=h[y])
            return 1;
        vt=x;
        dis=y-x;
        for(int k=LOG;k>=0;k--)
            if(nxt[vt][k]!=-1&&dis_nxt[vt][k]<=dis)
            {
                dis-=dis_nxt[vt][k];
                vt=nxt[vt][k];
            }
        if(dis<=k-1&&h[vt]>=h[y])
            return 1;
    }else
    {
        int vt=x,dis=x-y;
         for(int k=LOG;k>=0;k--)
            if(pre[vt][k]!=-1&&dis_pre[vt][k]<=dis)
            {
                dis-=dis_pre[vt][k];
                vt=pre[vt][k];
            }
        if(dis<=k-1&&h[vt]>=h[y])
            return 1;
        vt=x;
        dis=(y+n-x);
        for(int k=LOG;k>=0;k--)
            if(nxt[vt][k]!=-1&&dis_nxt[vt][k]<=dis)
            {
                dis-=dis_nxt[vt][k];
                vt=nxt[vt][k];
            }
        if(dis<=k-1&&h[vt]>=h[y])
            return 1;
    }
    return 0;
}

int compare_plants(int x, int y)
{
    if(check(x,y))
        return 1;
    if(check(y,x))
        return -1;
    return 0;
}

#ifdef SKY
int main()
{
    freopen("A.inp","r",stdin);
    freopen("A.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    int n,k;
    cin>>n>>k;
    vector<int>r(n);
    for(int i=0;i<n;i++)
        cin>>r[i];//,cout<<r[i]<<endl;
    init(k,r);
    int q;
    cin>>q;
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        cout<<compare_plants(x,y)<<endl;
    }
    return 0;
}
#endif

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 164624 KB Output is correct
2 Correct 64 ms 164596 KB Output is correct
3 Correct 70 ms 164668 KB Output is correct
4 Correct 64 ms 164628 KB Output is correct
5 Correct 67 ms 164688 KB Output is correct
6 Correct 139 ms 167664 KB Output is correct
7 Correct 247 ms 173740 KB Output is correct
8 Correct 1079 ms 225336 KB Output is correct
9 Correct 1097 ms 225320 KB Output is correct
10 Correct 1153 ms 225436 KB Output is correct
11 Correct 1117 ms 225404 KB Output is correct
12 Correct 1118 ms 225376 KB Output is correct
13 Correct 1118 ms 225452 KB Output is correct
14 Correct 1185 ms 225600 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 164684 KB Output is correct
2 Correct 69 ms 164588 KB Output is correct
3 Correct 72 ms 164632 KB Output is correct
4 Correct 65 ms 164692 KB Output is correct
5 Correct 70 ms 164620 KB Output is correct
6 Correct 77 ms 165092 KB Output is correct
7 Correct 156 ms 169548 KB Output is correct
8 Correct 72 ms 164812 KB Output is correct
9 Correct 69 ms 165060 KB Output is correct
10 Correct 156 ms 169572 KB Output is correct
11 Correct 161 ms 169424 KB Output is correct
12 Correct 191 ms 169808 KB Output is correct
13 Correct 153 ms 169540 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 164684 KB Output is correct
2 Correct 69 ms 164588 KB Output is correct
3 Correct 72 ms 164632 KB Output is correct
4 Correct 65 ms 164692 KB Output is correct
5 Correct 70 ms 164620 KB Output is correct
6 Correct 77 ms 165092 KB Output is correct
7 Correct 156 ms 169548 KB Output is correct
8 Correct 72 ms 164812 KB Output is correct
9 Correct 69 ms 165060 KB Output is correct
10 Correct 156 ms 169572 KB Output is correct
11 Correct 161 ms 169424 KB Output is correct
12 Correct 191 ms 169808 KB Output is correct
13 Correct 153 ms 169540 KB Output is correct
14 Correct 273 ms 173960 KB Output is correct
15 Incorrect 2338 ms 225780 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 164688 KB Output is correct
2 Correct 63 ms 164704 KB Output is correct
3 Correct 158 ms 168344 KB Output is correct
4 Correct 1511 ms 229520 KB Output is correct
5 Correct 1516 ms 226004 KB Output is correct
6 Correct 1823 ms 225760 KB Output is correct
7 Correct 1978 ms 225680 KB Output is correct
8 Incorrect 2094 ms 225588 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 164584 KB Output is correct
2 Correct 65 ms 164632 KB Output is correct
3 Correct 65 ms 164704 KB Output is correct
4 Correct 64 ms 164684 KB Output is correct
5 Correct 64 ms 164600 KB Output is correct
6 Correct 65 ms 164736 KB Output is correct
7 Correct 82 ms 165564 KB Output is correct
8 Correct 81 ms 165668 KB Output is correct
9 Correct 81 ms 165600 KB Output is correct
10 Correct 82 ms 165556 KB Output is correct
11 Correct 82 ms 165644 KB Output is correct
12 Correct 82 ms 165580 KB Output is correct
13 Correct 89 ms 165624 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 164804 KB Output is correct
2 Correct 64 ms 164684 KB Output is correct
3 Correct 64 ms 164584 KB Output is correct
4 Correct 64 ms 164716 KB Output is correct
5 Correct 69 ms 164940 KB Output is correct
6 Correct 1316 ms 225456 KB Output is correct
7 Correct 1720 ms 225480 KB Output is correct
8 Correct 1869 ms 225360 KB Output is correct
9 Incorrect 1980 ms 225468 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 164624 KB Output is correct
2 Correct 64 ms 164596 KB Output is correct
3 Correct 70 ms 164668 KB Output is correct
4 Correct 64 ms 164628 KB Output is correct
5 Correct 67 ms 164688 KB Output is correct
6 Correct 139 ms 167664 KB Output is correct
7 Correct 247 ms 173740 KB Output is correct
8 Correct 1079 ms 225336 KB Output is correct
9 Correct 1097 ms 225320 KB Output is correct
10 Correct 1153 ms 225436 KB Output is correct
11 Correct 1117 ms 225404 KB Output is correct
12 Correct 1118 ms 225376 KB Output is correct
13 Correct 1118 ms 225452 KB Output is correct
14 Correct 1185 ms 225600 KB Output is correct
15 Correct 68 ms 164684 KB Output is correct
16 Correct 69 ms 164588 KB Output is correct
17 Correct 72 ms 164632 KB Output is correct
18 Correct 65 ms 164692 KB Output is correct
19 Correct 70 ms 164620 KB Output is correct
20 Correct 77 ms 165092 KB Output is correct
21 Correct 156 ms 169548 KB Output is correct
22 Correct 72 ms 164812 KB Output is correct
23 Correct 69 ms 165060 KB Output is correct
24 Correct 156 ms 169572 KB Output is correct
25 Correct 161 ms 169424 KB Output is correct
26 Correct 191 ms 169808 KB Output is correct
27 Correct 153 ms 169540 KB Output is correct
28 Correct 273 ms 173960 KB Output is correct
29 Incorrect 2338 ms 225780 KB Output isn't correct
30 Halted 0 ms 0 KB -