oj.uz

Submission #721258

# Submission time Handle Problem Language Result Execution time Memory
721258 2023-04-10T14:54:51 Z bin9638 Comparing Plants (IOI20_plants) C++17
30 / 100
 2229 ms 130636 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],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]);
        }
}

int dis(int x,int y)
{
    return min(min(abs(x-y),abs(x+n-y)),abs(y+n-x));
}

bool check(int x,int y)
{
    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

Compilation message

plants.cpp: In function 'bool check(int, int)':
plants.cpp:193:9: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  193 |         for(int k=LOG;k>=0;k--)
      |         ^~~
plants.cpp:199:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  199 |             if(dis<=k-1&&h[vt]>=h[y])
      |             ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 66004 KB Output is correct
2 Correct 26 ms 65976 KB Output is correct
3 Correct 26 ms 66000 KB Output is correct
4 Correct 27 ms 66080 KB Output is correct
5 Correct 26 ms 66036 KB Output is correct
6 Correct 82 ms 68824 KB Output is correct
7 Correct 201 ms 75092 KB Output is correct
8 Correct 1024 ms 126544 KB Output is correct
9 Correct 1070 ms 126864 KB Output is correct
10 Correct 1115 ms 126780 KB Output is correct
11 Correct 1218 ms 126664 KB Output is correct
12 Correct 1222 ms 129580 KB Output is correct
13 Correct 1135 ms 129576 KB Output is correct
14 Correct 1156 ms 129604 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 65992 KB Output is correct
2 Correct 26 ms 65980 KB Output is correct
3 Correct 27 ms 66056 KB Output is correct
4 Correct 27 ms 65976 KB Output is correct
5 Correct 28 ms 66032 KB Output is correct
6 Correct 31 ms 66388 KB Output is correct
7 Correct 110 ms 70508 KB Output is correct
8 Correct 30 ms 66112 KB Output is correct
9 Correct 32 ms 66344 KB Output is correct
10 Correct 114 ms 70468 KB Output is correct
11 Correct 117 ms 70616 KB Output is correct
12 Correct 143 ms 70656 KB Output is correct
13 Correct 108 ms 70520 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 65992 KB Output is correct
2 Correct 26 ms 65980 KB Output is correct
3 Correct 27 ms 66056 KB Output is correct
4 Correct 27 ms 65976 KB Output is correct
5 Correct 28 ms 66032 KB Output is correct
6 Correct 31 ms 66388 KB Output is correct
7 Correct 110 ms 70508 KB Output is correct
8 Correct 30 ms 66112 KB Output is correct
9 Correct 32 ms 66344 KB Output is correct
10 Correct 114 ms 70468 KB Output is correct
11 Correct 117 ms 70616 KB Output is correct
12 Correct 143 ms 70656 KB Output is correct
13 Correct 108 ms 70520 KB Output is correct
14 Correct 231 ms 75164 KB Output is correct
15 Incorrect 2229 ms 127236 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 66004 KB Output is correct
2 Correct 30 ms 66004 KB Output is correct
3 Correct 114 ms 69420 KB Output is correct
4 Correct 1331 ms 130636 KB Output is correct
5 Correct 1410 ms 130096 KB Output is correct
6 Correct 1762 ms 129984 KB Output is correct
7 Correct 1930 ms 130268 KB Output is correct
8 Incorrect 2067 ms 130272 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 26 ms 66076 KB Output is correct
2 Correct 27 ms 66064 KB Output is correct
3 Correct 27 ms 65996 KB Output is correct
4 Correct 26 ms 66020 KB Output is correct
5 Correct 27 ms 66036 KB Output is correct
6 Correct 28 ms 66132 KB Output is correct
7 Correct 42 ms 66708 KB Output is correct
8 Correct 40 ms 66736 KB Output is correct
9 Correct 44 ms 66792 KB Output is correct
10 Correct 40 ms 66764 KB Output is correct
11 Correct 42 ms 66764 KB Output is correct
12 Correct 42 ms 66708 KB Output is correct
13 Correct 45 ms 66704 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 65968 KB Output is correct
2 Correct 26 ms 66068 KB Output is correct
3 Correct 28 ms 66012 KB Output is correct
4 Correct 25 ms 66064 KB Output is correct
5 Correct 30 ms 66252 KB Output is correct
6 Correct 1278 ms 126556 KB Output is correct
7 Correct 1625 ms 126912 KB Output is correct
8 Correct 1795 ms 126788 KB Output is correct
9 Incorrect 2015 ms 129616 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 66004 KB Output is correct
2 Correct 26 ms 65976 KB Output is correct
3 Correct 26 ms 66000 KB Output is correct
4 Correct 27 ms 66080 KB Output is correct
5 Correct 26 ms 66036 KB Output is correct
6 Correct 82 ms 68824 KB Output is correct
7 Correct 201 ms 75092 KB Output is correct
8 Correct 1024 ms 126544 KB Output is correct
9 Correct 1070 ms 126864 KB Output is correct
10 Correct 1115 ms 126780 KB Output is correct
11 Correct 1218 ms 126664 KB Output is correct
12 Correct 1222 ms 129580 KB Output is correct
13 Correct 1135 ms 129576 KB Output is correct
14 Correct 1156 ms 129604 KB Output is correct
15 Correct 30 ms 65992 KB Output is correct
16 Correct 26 ms 65980 KB Output is correct
17 Correct 27 ms 66056 KB Output is correct
18 Correct 27 ms 65976 KB Output is correct
19 Correct 28 ms 66032 KB Output is correct
20 Correct 31 ms 66388 KB Output is correct
21 Correct 110 ms 70508 KB Output is correct
22 Correct 30 ms 66112 KB Output is correct
23 Correct 32 ms 66344 KB Output is correct
24 Correct 114 ms 70468 KB Output is correct
25 Correct 117 ms 70616 KB Output is correct
26 Correct 143 ms 70656 KB Output is correct
27 Correct 108 ms 70520 KB Output is correct
28 Correct 231 ms 75164 KB Output is correct
29 Incorrect 2229 ms 127236 KB Output isn't correct
30 Halted 0 ms 0 KB -