Submission #755267

#	Time	Username	Problem	Language	Result	Execution time	Memory
755267		Rafi22	Comparing Plants (IOI20_plants)	C++14	5 / 100	730 ms	49240 KiB

plants

#include <bits/stdc++.h>

using namespace std;

#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;

const int pot=1<<18,N=200007,L=18;

int n;

struct T
{
    pair<int,int> seg[2*pot+7];
    int lzy[2*pot+7];
    T()
    {
        memset(seg,0,sizeof seg);
        memset(lzy,0,sizeof lzy);
    }
    void push(int v)
    {
        lzy[2*v]+=lzy[v];
        lzy[2*v+1]+=lzy[v];
        seg[2*v].st+=lzy[v];
        seg[2*v+1].st+=lzy[v];
        lzy[v]=0;
    }
    void add(int v,int a,int b,int l,int r,int x)
    {
        if(a<=l&&b>=r)
        {
            lzy[v]+=x;
            seg[v].st+=x;
            return ;
        }
        if(r<a||l>b) return ;
        push(v);
        add(2*v,a,b,l,(l+r)/2,x);
        add(2*v+1,a,b,(l+r)/2+1,r,x);
        seg[v]=min(seg[2*v],seg[2*v+1]);
    }
};

vector<int>p;

int skokR[N][L];
int skokL[N][L];

void init(int k,vector<int>r)
{
    n=sz(r);
    p.resize(2*n+2);
    T R,ile;
    for(int i=0;i<n;i++) R.seg[i+pot]={r[i],i+1};
    for(int i=n+1;i<=pot;i++) R.seg[i+pot-1]={inf,i};
    for(int i=1;i<=pot;i++) ile.seg[i+pot-1]={inf,i};
    for(int i=pot-1;i>0;i--)
    {
        R.seg[i]=min(R.seg[2*i],R.seg[2*i+1]);
        ile.seg[i]=min(ile.seg[2*i],ile.seg[2*i+1]);
    }
    int it=0;
    while(it<n)
    {
        while(R.seg[1].st==0)
        {
            int i=R.seg[1].nd;
            R.add(1,i,i,1,pot,inf);
            ile.add(1,i,i,1,pot,-inf);
            if(i+k-1<=n) ile.add(1,i+1,i+k-1,1,pot,1);
            else
            {
                ile.add(1,i+1,n,1,pot,1);
                ile.add(1,1,i+k-1-n,1,pot,1);
            }
        }
        int i=ile.seg[1].nd;
        ile.add(1,i,i,1,pot,inf);
        p[i]=n-it++;
        if(i+k-1<=n) ile.add(1,i+1,i+k-1,1,pot,-1);
        else
        {
            ile.add(1,i+1,n,1,pot,-1);
            ile.add(1,1,i+k-1-n,1,pot,-1);
        }
        if(i-k+1>0) R.add(1,i-k+1,i-1,1,pot,-1);
        else
        {
            R.add(1,i-k+1+n,n,1,pot,-1);
            R.add(1,1,i-1,1,pot,-1);
        }
    }
    for(int i=n+1;i<=2*n;i++) p[i]=p[i-n];
    p[2*n+1]=inf;
    p[0]=inf;
    set<pair<int,int>>S;
    S.insert({inf,0});
    for(int i=0;i<2*n;i++)
    {
        if(i-k>=0) S.erase({p[i-k+1],i-k});
        if(i>=n)
        {
            pair<int,int>x=*S.upper_bound({p[i+1],i});
            if(x.st==inf) skokR[i-n+1][0]=i-n+1;
            else skokR[i-n+1][0]=x.nd%n+1;
        }
        S.insert({p[i+1],i});
    }
    S.clear();
    S.insert({inf,0});
    for(int i=2*n-1;i>=0;i--)
    {
        if(i+k<2*n) S.erase({p[i+k+1],i+k});
        if(i<n)
        {
            pair<int,int>x=*S.upper_bound({p[i+1],i});
            if(x.st==inf) skokL[i+1][0]=i+1;
            else skokL[i+1][0]=x.nd%n+1;
        }
        S.insert({p[i+1],i});
    }
    for(int j=1;j<L;j++)
    {
        for(int i=1;i<=n;i++)
        {
            skokL[i][j]=skokL[skokL[i][j-1]][j-1];
            skokR[i][j]=skokR[skokR[i][j-1]][j-1];
        }
    }
}

int compare_plants(int x,int y)
{
    x++,y++;
    bool is=0;
    if(p[x]<p[y])
    {
        int X=x;
        for(int j=L-1;j>=0;j--) if(p[skokL[X][j]]<=p[y]) X=skokL[X][j];
        if(X==y) is=1;
        X=x;
        for(int j=L-1;j>=0;j--) if(p[skokR[X][j]]<=p[y]) X=skokR[X][j];
        if(X==y) is=1;
        if(is) return -1;
        else return 0;
    }
    else
    {
        int Y=y;
        for(int j=L-1;j>=0;j--) if(p[skokL[Y][j]]<=p[x]) Y=skokL[Y][j];
        if(Y==x) is=1;
        Y=y;
        for(int j=L-1;j>=0;j--) if(p[skokR[Y][j]]<=p[x]) Y=skokR[Y][j];
        if(Y==x) is=1;
        if(is) return 1;
        else return 0;
    }
}
/*

int main()
{
    init(2, {0, 1, 0, 1});
    cout<<compare_plants(0, 3)<<endl;
    cout<<compare_plants(1, 3)<<endl;

   /* int n,k;
    cin>>n>>k;
    vector<int>q(n);
    for(int i=0;i<n;i++) q[i]=i+1;
    random_shuffle(all(q));
    vector<int>r(n,0);
    for(int i=0;i<n;i++)
    {
        for(int j=i;j<i+k;j++) if(q[i]<q[j%n]) r[i]++;
    }
    for(int i=0;i<n;i++) cout<<q[i]<<" ";
    cout<<endl;
    for(int i=0;i<n;i++) cout<<r[i]<<" ";
    cout<<endl;
    init(k,r);
    return 0;
}*/

Compilation message (stderr)

plants.cpp:176:4: warning: "/*" within comment [-Wcomment]
  176 |    /* int n,k;
      |     
plants.cpp: In constructor 'T::T()':
plants.cpp:26:32: warning: 'void* memset(void*, int, size_t)' clearing an object of type 'struct std::pair<int, int>' with no trivial copy-assignment; use assignment instead [-Wclass-memaccess]
   26 |         memset(seg,0,sizeof seg);
      |                                ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
                 from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from plants.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<int, int>' declared here
  211 |     struct pair
      |            ^~~~

• Subtask 1: 5 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25