oj.uz

Submission #721246

# Submission time Handle Problem Language Result Execution time Memory
721246 2023-04-10T14:31:42 Z bin9638 Comparing Plants (IOI20_plants) C++17
25 / 100
 4000 ms 97772 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],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;
}

bool check_hihi(int u)
{
    if(a[u]!=0)
        return 0;
    for(int j=1;j<k;j++)
        if(a[(u-j+n)%n]==0)
            return 0;
    return 1;
}

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;
        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]);
        }
}

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)
{
   // cout<<x<<" "<<y<<endl;
    int vt=x;
    for(int t=0;t<=n;t++)
    {
        if(vt!=-1&&dis(vt,y)<=k-1&&h[vt]>=h[y])
            return 1;
        if(vt!=-1)
            vt=pre[vt][0];
                else break;
    }
    vt=x;
    for(int t=0;t<=n;t++)
    {
        if(vt!=-1&&dis(vt,y)<=k-1&&h[vt]>=h[y])
            return 1;
        if(vt!=-1)
            vt=nxt[vt][0];
                else break;
    }
    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 66044 KB Output is correct
2 Correct 25 ms 65956 KB Output is correct
3 Correct 26 ms 66032 KB Output is correct
4 Correct 28 ms 66032 KB Output is correct
5 Correct 27 ms 66028 KB Output is correct
6 Correct 85 ms 68812 KB Output is correct
7 Correct 312 ms 71824 KB Output is correct
8 Correct 964 ms 93760 KB Output is correct
9 Correct 1127 ms 96596 KB Output is correct
10 Correct 2718 ms 96684 KB Output is correct
11 Execution timed out 4067 ms 96684 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 65996 KB Output is correct
2 Correct 27 ms 65996 KB Output is correct
3 Correct 26 ms 65964 KB Output is correct
4 Correct 30 ms 66076 KB Output is correct
5 Correct 27 ms 66004 KB Output is correct
6 Correct 42 ms 66124 KB Output is correct
7 Correct 2731 ms 69624 KB Output is correct
8 Correct 29 ms 66096 KB Output is correct
9 Correct 38 ms 66124 KB Output is correct
10 Correct 2672 ms 69620 KB Output is correct
11 Correct 94 ms 69532 KB Output is correct
12 Correct 1353 ms 69752 KB Output is correct
13 Correct 3684 ms 69628 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 65996 KB Output is correct
2 Correct 27 ms 65996 KB Output is correct
3 Correct 26 ms 65964 KB Output is correct
4 Correct 30 ms 66076 KB Output is correct
5 Correct 27 ms 66004 KB Output is correct
6 Correct 42 ms 66124 KB Output is correct
7 Correct 2731 ms 69624 KB Output is correct
8 Correct 29 ms 66096 KB Output is correct
9 Correct 38 ms 66124 KB Output is correct
10 Correct 2672 ms 69620 KB Output is correct
11 Correct 94 ms 69532 KB Output is correct
12 Correct 1353 ms 69752 KB Output is correct
13 Correct 3684 ms 69628 KB Output is correct
14 Execution timed out 4054 ms 71496 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 66004 KB Output is correct
2 Correct 27 ms 65964 KB Output is correct
3 Correct 714 ms 69076 KB Output is correct
4 Execution timed out 4050 ms 97772 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 66044 KB Output is correct
2 Correct 25 ms 66004 KB Output is correct
3 Correct 25 ms 66004 KB Output is correct
4 Correct 25 ms 66056 KB Output is correct
5 Correct 30 ms 66016 KB Output is correct
6 Correct 28 ms 66132 KB Output is correct
7 Correct 54 ms 66636 KB Output is correct
8 Correct 50 ms 66668 KB Output is correct
9 Correct 54 ms 66644 KB Output is correct
10 Correct 50 ms 66772 KB Output is correct
11 Correct 45 ms 66660 KB Output is correct
12 Correct 46 ms 66736 KB Output is correct
13 Correct 55 ms 66636 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 66004 KB Output is correct
2 Correct 31 ms 66020 KB Output is correct
3 Correct 25 ms 66040 KB Output is correct
4 Correct 28 ms 66032 KB Output is correct
5 Correct 32 ms 66144 KB Output is correct
6 Correct 2333 ms 93892 KB Output is correct
7 Correct 3693 ms 96208 KB Output is correct
8 Execution timed out 4035 ms 96376 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 66044 KB Output is correct
2 Correct 25 ms 65956 KB Output is correct
3 Correct 26 ms 66032 KB Output is correct
4 Correct 28 ms 66032 KB Output is correct
5 Correct 27 ms 66028 KB Output is correct
6 Correct 85 ms 68812 KB Output is correct
7 Correct 312 ms 71824 KB Output is correct
8 Correct 964 ms 93760 KB Output is correct
9 Correct 1127 ms 96596 KB Output is correct
10 Correct 2718 ms 96684 KB Output is correct
11 Execution timed out 4067 ms 96684 KB Time limit exceeded
12 Halted 0 ms 0 KB -