oj.uz

Submission #721265

# Submission time Handle Problem Language Result Execution time Memory
721265 2023-04-10T15:14:37 Z bin9638 Comparing Plants (IOI20_plants) C++17
100 / 100
 2096 ms 167160 KB 
#include <bits/stdc++.h>

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

using namespace std;

#define N 400010
#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];
ll dis_pre[N][21],dis_nxt[N][21];
int 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 24 ms 66004 KB Output is correct
2 Correct 24 ms 66004 KB Output is correct
3 Correct 27 ms 66092 KB Output is correct
4 Correct 24 ms 65980 KB Output is correct
5 Correct 25 ms 65972 KB Output is correct
6 Correct 86 ms 68884 KB Output is correct
7 Correct 204 ms 78496 KB Output is correct
8 Correct 1094 ms 159700 KB Output is correct
9 Correct 1043 ms 159588 KB Output is correct
10 Correct 1079 ms 159632 KB Output is correct
11 Correct 1084 ms 159720 KB Output is correct
12 Correct 1111 ms 159644 KB Output is correct
13 Correct 1107 ms 159596 KB Output is correct
14 Correct 1181 ms 159588 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 66068 KB Output is correct
2 Correct 26 ms 66000 KB Output is correct
3 Correct 28 ms 66056 KB Output is correct
4 Correct 26 ms 66088 KB Output is correct
5 Correct 27 ms 66024 KB Output is correct
6 Correct 31 ms 66516 KB Output is correct
7 Correct 123 ms 71376 KB Output is correct
8 Correct 28 ms 66104 KB Output is correct
9 Correct 34 ms 66516 KB Output is correct
10 Correct 116 ms 71392 KB Output is correct
11 Correct 118 ms 71276 KB Output is correct
12 Correct 170 ms 71412 KB Output is correct
13 Correct 117 ms 71292 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 66068 KB Output is correct
2 Correct 26 ms 66000 KB Output is correct
3 Correct 28 ms 66056 KB Output is correct
4 Correct 26 ms 66088 KB Output is correct
5 Correct 27 ms 66024 KB Output is correct
6 Correct 31 ms 66516 KB Output is correct
7 Correct 123 ms 71376 KB Output is correct
8 Correct 28 ms 66104 KB Output is correct
9 Correct 34 ms 66516 KB Output is correct
10 Correct 116 ms 71392 KB Output is correct
11 Correct 118 ms 71276 KB Output is correct
12 Correct 170 ms 71412 KB Output is correct
13 Correct 117 ms 71292 KB Output is correct
14 Correct 238 ms 78396 KB Output is correct
15 Correct 1990 ms 159532 KB Output is correct
16 Correct 240 ms 80704 KB Output is correct
17 Correct 1972 ms 163224 KB Output is correct
18 Correct 1343 ms 162884 KB Output is correct
19 Correct 1473 ms 163356 KB Output is correct
20 Correct 1842 ms 163256 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 66004 KB Output is correct
2 Correct 24 ms 65972 KB Output is correct
3 Correct 118 ms 69752 KB Output is correct
4 Correct 1388 ms 163708 KB Output is correct
5 Correct 1492 ms 159936 KB Output is correct
6 Correct 1855 ms 159472 KB Output is correct
7 Correct 1962 ms 159428 KB Output is correct
8 Correct 2081 ms 159444 KB Output is correct
9 Correct 1337 ms 162828 KB Output is correct
10 Correct 1400 ms 162608 KB Output is correct
11 Correct 1127 ms 162452 KB Output is correct
12 Correct 1287 ms 162828 KB Output is correct
13 Correct 1375 ms 162720 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 66004 KB Output is correct
2 Correct 25 ms 66004 KB Output is correct
3 Correct 26 ms 66004 KB Output is correct
4 Correct 27 ms 66004 KB Output is correct
5 Correct 24 ms 66012 KB Output is correct
6 Correct 27 ms 66100 KB Output is correct
7 Correct 45 ms 66892 KB Output is correct
8 Correct 40 ms 66764 KB Output is correct
9 Correct 45 ms 66756 KB Output is correct
10 Correct 40 ms 66768 KB Output is correct
11 Correct 42 ms 66848 KB Output is correct
12 Correct 43 ms 66772 KB Output is correct
13 Correct 39 ms 66848 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 65996 KB Output is correct
2 Correct 25 ms 66004 KB Output is correct
3 Correct 24 ms 65992 KB Output is correct
4 Correct 29 ms 66088 KB Output is correct
5 Correct 32 ms 66464 KB Output is correct
6 Correct 1332 ms 159468 KB Output is correct
7 Correct 1752 ms 159468 KB Output is correct
8 Correct 1825 ms 159424 KB Output is correct
9 Correct 1999 ms 159632 KB Output is correct
10 Correct 1213 ms 161976 KB Output is correct
11 Correct 1575 ms 162452 KB Output is correct
12 Correct 1263 ms 166564 KB Output is correct
13 Correct 1418 ms 162132 KB Output is correct
14 Correct 1759 ms 161980 KB Output is correct
15 Correct 1944 ms 162092 KB Output is correct
16 Correct 1220 ms 161512 KB Output is correct
17 Correct 1289 ms 161844 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 66004 KB Output is correct
2 Correct 24 ms 66004 KB Output is correct
3 Correct 27 ms 66092 KB Output is correct
4 Correct 24 ms 65980 KB Output is correct
5 Correct 25 ms 65972 KB Output is correct
6 Correct 86 ms 68884 KB Output is correct
7 Correct 204 ms 78496 KB Output is correct
8 Correct 1094 ms 159700 KB Output is correct
9 Correct 1043 ms 159588 KB Output is correct
10 Correct 1079 ms 159632 KB Output is correct
11 Correct 1084 ms 159720 KB Output is correct
12 Correct 1111 ms 159644 KB Output is correct
13 Correct 1107 ms 159596 KB Output is correct
14 Correct 1181 ms 159588 KB Output is correct
15 Correct 25 ms 66068 KB Output is correct
16 Correct 26 ms 66000 KB Output is correct
17 Correct 28 ms 66056 KB Output is correct
18 Correct 26 ms 66088 KB Output is correct
19 Correct 27 ms 66024 KB Output is correct
20 Correct 31 ms 66516 KB Output is correct
21 Correct 123 ms 71376 KB Output is correct
22 Correct 28 ms 66104 KB Output is correct
23 Correct 34 ms 66516 KB Output is correct
24 Correct 116 ms 71392 KB Output is correct
25 Correct 118 ms 71276 KB Output is correct
26 Correct 170 ms 71412 KB Output is correct
27 Correct 117 ms 71292 KB Output is correct
28 Correct 238 ms 78396 KB Output is correct
29 Correct 1990 ms 159532 KB Output is correct
30 Correct 240 ms 80704 KB Output is correct
31 Correct 1972 ms 163224 KB Output is correct
32 Correct 1343 ms 162884 KB Output is correct
33 Correct 1473 ms 163356 KB Output is correct
34 Correct 1842 ms 163256 KB Output is correct
35 Correct 24 ms 66004 KB Output is correct
36 Correct 24 ms 65972 KB Output is correct
37 Correct 118 ms 69752 KB Output is correct
38 Correct 1388 ms 163708 KB Output is correct
39 Correct 1492 ms 159936 KB Output is correct
40 Correct 1855 ms 159472 KB Output is correct
41 Correct 1962 ms 159428 KB Output is correct
42 Correct 2081 ms 159444 KB Output is correct
43 Correct 1337 ms 162828 KB Output is correct
44 Correct 1400 ms 162608 KB Output is correct
45 Correct 1127 ms 162452 KB Output is correct
46 Correct 1287 ms 162828 KB Output is correct
47 Correct 1375 ms 162720 KB Output is correct
48 Correct 25 ms 66004 KB Output is correct
49 Correct 25 ms 66004 KB Output is correct
50 Correct 26 ms 66004 KB Output is correct
51 Correct 27 ms 66004 KB Output is correct
52 Correct 24 ms 66012 KB Output is correct
53 Correct 27 ms 66100 KB Output is correct
54 Correct 45 ms 66892 KB Output is correct
55 Correct 40 ms 66764 KB Output is correct
56 Correct 45 ms 66756 KB Output is correct
57 Correct 40 ms 66768 KB Output is correct
58 Correct 42 ms 66848 KB Output is correct
59 Correct 43 ms 66772 KB Output is correct
60 Correct 39 ms 66848 KB Output is correct
61 Correct 116 ms 71496 KB Output is correct
62 Correct 226 ms 80568 KB Output is correct
63 Correct 1189 ms 162492 KB Output is correct
64 Correct 1427 ms 162628 KB Output is correct
65 Correct 1923 ms 162760 KB Output is correct
66 Correct 2047 ms 162908 KB Output is correct
67 Correct 2096 ms 163100 KB Output is correct
68 Correct 1359 ms 163028 KB Output is correct
69 Correct 1703 ms 163104 KB Output is correct
70 Correct 1420 ms 167160 KB Output is correct
71 Correct 1640 ms 162972 KB Output is correct
72 Correct 1896 ms 162756 KB Output is correct
73 Correct 2082 ms 162924 KB Output is correct
74 Correct 1284 ms 162464 KB Output is correct
75 Correct 1494 ms 162688 KB Output is correct