oj.uz

Submission #721238

# Submission time Handle Problem Language Result Execution time Memory
721238 2023-04-10T14:25:40 Z bin9638 Comparing Plants (IOI20_plants) C++17
11 / 100
 4000 ms 69180 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 t=0;t<n;t++)
    {
        for(int i=0;i<n;i++)
            if(T.get_min(1,1,n*2,i+1,i+1).fs==0&&T.get_min(1,1,n*2,i+1+n-k+1,i+1+n-1).fs!=0)
                build(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;
    }
    //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 24 ms 66004 KB Output is correct
2 Correct 28 ms 66032 KB Output is correct
3 Correct 29 ms 66004 KB Output is correct
4 Correct 26 ms 66044 KB Output is correct
5 Correct 27 ms 66052 KB Output is correct
6 Correct 88 ms 68888 KB Output is correct
7 Execution timed out 4078 ms 5420 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 65952 KB Output is correct
2 Correct 25 ms 66032 KB Output is correct
3 Correct 26 ms 66076 KB Output is correct
4 Correct 30 ms 66140 KB Output is correct
5 Correct 26 ms 66008 KB Output is correct
6 Correct 147 ms 66116 KB Output is correct
7 Execution timed out 4054 ms 69180 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 65952 KB Output is correct
2 Correct 25 ms 66032 KB Output is correct
3 Correct 26 ms 66076 KB Output is correct
4 Correct 30 ms 66140 KB Output is correct
5 Correct 26 ms 66008 KB Output is correct
6 Correct 147 ms 66116 KB Output is correct
7 Execution timed out 4054 ms 69180 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 66044 KB Output is correct
2 Correct 26 ms 66020 KB Output is correct
3 Correct 1248 ms 69024 KB Output is correct
4 Execution timed out 4053 ms 26312 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 66004 KB Output is correct
2 Correct 24 ms 66024 KB Output is correct
3 Correct 26 ms 66072 KB Output is correct
4 Correct 29 ms 65964 KB Output is correct
5 Correct 26 ms 65976 KB Output is correct
6 Correct 28 ms 66036 KB Output is correct
7 Correct 51 ms 66636 KB Output is correct
8 Correct 54 ms 66704 KB Output is correct
9 Correct 62 ms 66672 KB Output is correct
10 Correct 59 ms 66684 KB Output is correct
11 Correct 52 ms 66688 KB Output is correct
12 Correct 59 ms 66688 KB Output is correct
13 Correct 63 ms 66640 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 65996 KB Output is correct
2 Correct 27 ms 66028 KB Output is correct
3 Correct 26 ms 65980 KB Output is correct
4 Correct 26 ms 65996 KB Output is correct
5 Correct 140 ms 66080 KB Output is correct
6 Execution timed out 4025 ms 26220 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 66004 KB Output is correct
2 Correct 28 ms 66032 KB Output is correct
3 Correct 29 ms 66004 KB Output is correct
4 Correct 26 ms 66044 KB Output is correct
5 Correct 27 ms 66052 KB Output is correct
6 Correct 88 ms 68888 KB Output is correct
7 Execution timed out 4078 ms 5420 KB Time limit exceeded
8 Halted 0 ms 0 KB -