Submission #306055

#	Time	Username	Problem	Language	Result	Execution time	Memory
306055		gs18115	Comparing Plants (IOI20_plants)	C++14	100 / 100	2486 ms	87720 KiB

plants

#include"plants.h"
#include<iostream>
#include<vector>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
const int mx=200010;
struct seg
{
    pi t[mx*4];
    int lz[mx*4];
    void init(int n,int s,int e,vector<int>&v)
    {
        lz[n]=0;
        if(s==e)
        {
            t[n]=pi(v[s],s);
            return;
        }
        int m=s+(e-s)/2;
        init(n*2,s,m,v);
        init(n*2+1,m+1,e,v);
        t[n]=min(t[n*2],t[n*2+1]);
        return;
    }
    inline void put(int n,int p)
    {
        t[n].fi+=p;
        lz[n]+=p;
        return;
    }
    inline void prop(int n)
    {
        if(lz[n]==0)
            return;
        put(n*2,lz[n]);
        put(n*2+1,lz[n]);
        lz[n]=0;
        return;
    }
    void upd(int n,int s,int e,int S,int E,int p)
    {
        if(s>E||S>e)
            return;
        if(S<=s&&e<=E)
            return put(n,p);
        prop(n);
        int m=s+(e-s)/2;
        upd(n*2,s,m,S,E,p);
        upd(n*2+1,m+1,e,S,E,p);
        t[n]=min(t[n*2],t[n*2+1]);
        return;
    }
}st1,st2;
struct seg2
{
    int t[mx*4];
    void init(int n,int s,int e,int v)
    {
        t[n]=v;
        if(s==e)
            return;
        int m=s+(e-s)/2;
        init(n*2,s,m,v);
        init(n*2+1,m+1,e,v);
        return;
    }
    void put(int n,int s,int e,int x,int p)
    {
        if(s==e)
        {
            t[n]=p;
            return;
        }
        int m=s+(e-s)/2;
        if(x>m)
            put(n*2+1,m+1,e,x,p);
        else
            put(n*2,s,m,x,p);
        t[n]=min(t[n*2],t[n*2+1]);
        return;
    }
    int query(int n,int s,int e,int S,int E)
    {
        if(s>E||S>e)
            return inf;
        if(S<=s&&e<=E)
            return t[n];
        int m=s+(e-s)/2;
        return min(query(n*2,s,m,S,E),query(n*2+1,m+1,e,S,E));
    }
}st3;
int ord[mx];
vector<int>ov;
int spa1[mx][20],spd1[mx][20];
int spa2[mx][20],spd2[mx][20];
int n;
void init(int k,vector<int>r)
{
    n=r.size();
    st1.init(1,0,n-1,r);
    st2.init(1,0,n-1,r);
    for(int i=0;i<n;i++)
    {
        while(st2.t[1].fi==0)
        {
            int cur=st2.t[1].se;
            st2.upd(1,0,n-1,cur,cur,inf);
            st1.upd(1,0,n-1,cur+1,cur+k-1,1),st1.upd(1,0,n-1,0,cur+k-1-n,1);
        }
        int cur=st1.t[1].se;
        ord[cur]=i;
        ov.eb(cur);
        st1.upd(1,0,n-1,cur,cur,inf);
        st1.upd(1,0,n-1,cur-k+1+n,n-1,-1),st1.upd(1,0,n-1,cur-k+1,cur-1,-1);
        st1.upd(1,0,n-1,cur+1,cur+k-1,-1),st1.upd(1,0,n-1,0,cur+k-1-n,-1);
        st2.upd(1,0,n-1,cur-k+1+n,n-1,-1),st2.upd(1,0,n-1,cur-k+1,cur-1,-1);
    }
    st3.init(1,0,n-1,n);
    auto get3=[&](const int&p)->int{return min(st3.query(1,0,n-1,p-k+1,p-1),
    st3.query(1,0,n-1,p-k+1+n,n-1));};
    auto get4=[&](const int&p)->int{return min(st3.query(1,0,n-1,p+1,p+k-1),
    st3.query(1,0,n-1,0,p+k-1-n));};
    ov.eb(ord[n]=n);
    for(int i=0;i<20;i++)
        spa1[n][i]=spa2[n][i]=n,spd1[n][i]=spd2[n][i]=0;
    for(int i=n;i-->0;)
    {
        int cur=ov[i];
        int nx=ov[get3(cur)];
        spa1[cur][0]=nx,spd1[cur][0]=nx>cur?1:0;
        nx=ov[get4(cur)];
        spa2[cur][0]=nx,spd2[cur][0]=nx<cur?1:0;
        st3.put(1,0,n-1,cur,i);
    }
    for(int j=0;j<19;j++)
        for(int i=0;i<=n;i++)
            spa1[i][j+1]=spa1[spa1[i][j]][j],
            spd1[i][j+1]=spd1[spa1[i][j]][j]+spd1[i][j],
            spa2[i][j+1]=spa2[spa2[i][j]][j],
            spd2[i][j+1]=spd2[spa2[i][j]][j]+spd2[i][j];
    return;
}
int compare_plants(int x,int y)
{
    int p=1;
    if(ord[x]>ord[y])
        swap(x,y),p=-1;
    int l=x,ld=0;
    int r=x,rd=0;
    for(int i=20;i-->0;)
        if(ord[spa1[l][i]]<=ord[y])
            ld+=spd1[l][i],l=spa1[l][i];
    for(int i=20;i-->0;)
        if(ord[spa2[r][i]]<=ord[y])
            rd+=spd2[r][i],r=spa2[r][i];
    l-=n*min(2,ld),r+=n*min(2,rd);
    for(int i=-1;i<=1;i++)
        if(l+i*n<=y&&y<=r+i*n)
            return p;
    return 0;
}

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