Submission #603610

#	Time	Username	Problem	Language	Result	Execution time	Memory
603610		rrrr10000	Comparing Plants (IOI20_plants)	C++14	100 / 100	2356 ms	243288 KiB

plants

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef tuple<ll,ll,ll> PP;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<P> vp;
typedef vector<bool> vb;
typedef vector<vb> vvb;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,k,n) for(ll i=(ll)(k);i<(ll)(n);i++)
#define pb emplace_back
#define fi first
#define se second
template<class T> void out(T a){cout<<a<<endl;}
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<endl;}
const ll inf=1001001001001001001;
struct segtree{
    vp seg;vi lazy;
    ll n=1;
    segtree(vp v){
        while(n<v.size())n*=2;
        seg=vp(n*2,P(2*inf,0));lazy=vi(n*2);
        rep(i,v.size())seg[i+n]=v[i];
        for(ll i=n-1;i>0;i--)seg[i]=min(seg[i*2],seg[i*2+1]);
    }
    void eval(ll k,ll l,ll r){
        seg[k].fi+=lazy[k];
        if(r-l>1)rep(j,2)lazy[k*2+j]+=lazy[k];
        lazy[k]=0;
    }
    P get(ll a,ll b,ll k=1,ll l=0,ll r=-1){
        if(r==-1)r=n;
        eval(k,l,r);
        if(r<=a||b<=l)return P(2*inf,0);
        if(a<=l&&r<=b)return seg[k];
        return min(get(a,b,k*2,l,(l+r)/2),get(a,b,k*2+1,(l+r)/2,r));
    }
    void add(ll x,ll a,ll b,ll k=1,ll l=0,ll r=-1){
        if(r==-1)r=n;
        eval(k,l,r);
        if(r<=a||b<=l)return;
        if(a<=l&&r<=b){
            lazy[k]+=x;eval(k,l,r);return;
        }
        add(x,a,b,k*2,l,(l+r)/2);
        add(x,a,b,k*2+1,(l+r)/2,r);
        seg[k]=min(seg[k*2],seg[k*2+1]);
    }
};
vi num,al,rv;
vvi ma,mi;
void init(int k,vector<int> v){
    ll n=v.size();
    vp tmp1(n),tmp2(n);
    rep(i,n)tmp1[i]=P(v[i],i);
    rep(i,n)tmp2[i]=P(inf,i);
    segtree seg1(tmp1),seg2(tmp2);
    auto dif=[&](ll x){
        return (x%n+n)%n;
    };
    ll cnt=0;
    num=vi(n);
    while(true){
        while(true){
            auto tmp=seg1.get(0,n);
            if(tmp.fi>0)break;
            ll i=tmp.se;
            seg1.add(inf,i,i+1);
            seg2.add(-inf,i,i+1);
            if(i+k<=n)seg2.add(1,i+1,i+k);
            else{
                seg2.add(1,i+1,n);
                seg2.add(1,0,i+k-n);
            }
        }
        auto tmp=seg2.get(0,n);
        if(tmp.fi>0)break;
        ll i=tmp.se;
        seg2.add(inf,i,i+1);
        num[i]=cnt++;
        if(i-k+1>=0)seg1.add(-1,i-k+1,i);
        else{
            seg1.add(-1,0,i);
            seg1.add(-1,i-k+1+n,n);
        }
        if(i+k<=n)seg2.add(-1,i+1,i+k);
        else{
            seg2.add(-1,i+1,n);
            seg2.add(-1,0,i+k-n);
        }
    }
    al=vi(n*3);
    rep(i,n)al[num[i]*3]=i;
    rep(i,n)al[num[i]*3+2]=i+n;
    rep(i,n)al[num[i]*3+1]=i+n*2;
    rv=vi(n*3);
    rep(i,n*3)rv[al[i]]=i;
    ma=vvi(20,vi(n*3,-1));
    mi=vvi(20,vi(n*3,-1));
    rep(i,n*3)ma[0][i]=mi[0][i]=i;
    {
        set<ll> S;
        for(int i=n*3-1;i>=0;i--){
            if(i+k<n*3)S.erase(rv[i+k]);
            auto itr=S.lower_bound(rv[i]);
            if(itr!=S.end())ma[0][rv[i]]=*itr;
            S.insert(rv[i]);
        }
    }
    {
        set<ll> S;
        rep(i,n*3){
            if(i-k>=0)S.erase(rv[i-k]);
            auto itr=S.lower_bound(rv[i]);
            if(itr!=S.end())mi[0][rv[i]]=*itr;
            S.insert(rv[i]);
        }
    }
    // outv(ma[0]);outv(mi[0]);
    rep(j,19)rep(i,n*3)ma[j+1][i]=ma[j][ma[j][i]];
    rep(j,19)rep(i,n*3)mi[j+1][i]=mi[j][mi[j][i]];
    // outv(num);
    // outv(al);
}
int compare_plants(int x,int y){
    int f=-1;
    if(num[x]<num[y]){
        swap(x,y);
        f=1;
    }
    ll i=rv[y+num.size()],j=rv[x+num.size()];
    // cout<<x<<' '<<y<<' '<<i<<' '<<j<<endl;
    {
        ll cur=i;
        for(ll t=19;t>=0;t--)if(ma[t][cur]<=j)cur=ma[t][cur];
        ll tmp=x+num.size();
        if(x<y)tmp+=num.size();
        if(al[cur]>=tmp)return f;
    }
    {
        ll cur=i;
        for(ll t=19;t>=0;t--)if(mi[t][cur]<=j)cur=mi[t][cur];
        ll tmp=x+num.size();
        if(x>y)tmp-=num.size();
        if(al[cur]<=tmp)return f;
    }
    return 0;
}

Compilation message (stderr)

plants.cpp: In constructor 'segtree::segtree(vp)':
plants.cpp:24:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |         while(n<v.size())n*=2;
      |               ~^~~~~~~~~
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:61:10: warning: variable 'dif' set but not used [-Wunused-but-set-variable]
   61 |     auto dif=[&](ll x){
      |          ^~~

• 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