oj.uz

Submission #721199

# Submission time Handle Problem Language Result Execution time Memory
721199 2023-04-10T13:42:26 Z bin9638 Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 71808 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;
    for(int i=0;i<n;i++)
    {
        build(T.get_min(1,1,n*2,1,n*2).sc);
     //   for(int i=0;i<n;i++)cout<<T.get_max(1,1,n*2,i+1,i+1).fs<<" ";cout<<endl;
    }*/
        int dem=n;
    for(int t=0;t<n;t++)
    {
    for(int i=0;i<n;i++)
        if(check_hihi(i))
        {
            h[i]=--dem;
            for(int j=0;j<k;j++)
                a[(i-j+n)%n]--;
            break;
        }
    }
 //   for(int i=0;i<n;i++)cout<<h[i]<<" ";cout<<endl;
    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;
  //  cout<<dis(x,y)<<endl;
    if(dis(vt,y)>k-1)
    {
        for(int k=LOG;k>=0;k--)
            if(pre[vt][k]!=-1&&dis(pre[vt][k],y)>k-1)
                vt=pre[vt][k];
    }
    if(dis(vt,y)>k-1)
        vt=pre[vt][0];
    if(vt!=-1&&h[vt]>=h[y])
        return 1;
    vt=x;
     if(dis(vt,y)>k-1)
     {
    for(int k=LOG;k>=0;k--)
        if(nxt[vt][k]!=-1&&dis(nxt[vt][k],y)>k-1)
            vt=nxt[vt][k];
     }
     if(dis(vt,y)>k-1)
        vt=nxt[vt][0];
     if(vt!=-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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 65988 KB Output is correct
2 Correct 26 ms 66048 KB Output is correct
3 Correct 25 ms 65992 KB Output is correct
4 Correct 25 ms 66056 KB Output is correct
5 Correct 26 ms 66068 KB Output is correct
6 Incorrect 76 ms 68764 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 65996 KB Output is correct
2 Correct 28 ms 66004 KB Output is correct
3 Correct 33 ms 65968 KB Output is correct
4 Correct 30 ms 65940 KB Output is correct
5 Correct 26 ms 66032 KB Output is correct
6 Correct 37 ms 66212 KB Output is correct
7 Correct 275 ms 69688 KB Output is correct
8 Correct 24 ms 66132 KB Output is correct
9 Correct 36 ms 66148 KB Output is correct
10 Correct 289 ms 69692 KB Output is correct
11 Correct 205 ms 69556 KB Output is correct
12 Correct 218 ms 69732 KB Output is correct
13 Correct 324 ms 69704 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 65996 KB Output is correct
2 Correct 28 ms 66004 KB Output is correct
3 Correct 33 ms 65968 KB Output is correct
4 Correct 30 ms 65940 KB Output is correct
5 Correct 26 ms 66032 KB Output is correct
6 Correct 37 ms 66212 KB Output is correct
7 Correct 275 ms 69688 KB Output is correct
8 Correct 24 ms 66132 KB Output is correct
9 Correct 36 ms 66148 KB Output is correct
10 Correct 289 ms 69692 KB Output is correct
11 Correct 205 ms 69556 KB Output is correct
12 Correct 218 ms 69732 KB Output is correct
13 Correct 324 ms 69704 KB Output is correct
14 Correct 2239 ms 71808 KB Output is correct
15 Execution timed out 4067 ms 26324 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 65936 KB Output is correct
2 Correct 26 ms 65984 KB Output is correct
3 Incorrect 143 ms 69032 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 66032 KB Output is correct
2 Correct 25 ms 65952 KB Output is correct
3 Correct 27 ms 66024 KB Output is correct
4 Correct 24 ms 65964 KB Output is correct
5 Incorrect 25 ms 65932 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 65952 KB Output is correct
2 Correct 26 ms 65972 KB Output is correct
3 Correct 25 ms 66008 KB Output is correct
4 Correct 24 ms 65980 KB Output is correct
5 Incorrect 30 ms 66072 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 65988 KB Output is correct
2 Correct 26 ms 66048 KB Output is correct
3 Correct 25 ms 65992 KB Output is correct
4 Correct 25 ms 66056 KB Output is correct
5 Correct 26 ms 66068 KB Output is correct
6 Incorrect 76 ms 68764 KB Output isn't correct
7 Halted 0 ms 0 KB -