Submission #1063146

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063146		new_acc	Comparing Plants (IOI20_plants)	C++14	5 / 100	485 ms	92400 KiB

plants

#include<bits/stdc++.h>
#include "plants.h"
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=4e5+10;
const int SS=1<<19;
const int INFi=1e9;
const ll INFl=1e16;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=2027865967;
const ll p=70032301;
const ull p2=913;
const int L=20;
int t[N],n,lazy[SS*2+10],k,li,t2[N],g[N],jp[N][L],jp2[N][L];
pair<int,int> seg[SS*2+10];
void push(int v){
    seg[v*2].fi+=lazy[v],seg[v*2+1].fi+=lazy[v];
    lazy[v*2]+=lazy[v],lazy[v*2+1]+=lazy[v];
    lazy[v]=0;
}
void upd(int a,int b,int x,int p=0,int k=SS-1,int v=1){
    if(p>b or k<a) return;
    if(p>=a and k<=b){
        lazy[v]+=x,seg[v].fi+=x;
        return;
    }
    int sr=(p+k)/2;
    push(v);
    upd(a,b,x,p,sr,v*2),upd(a,b,x,sr+1,k,v*2+1);
    if(seg[v*2].fi<seg[v*2+1].fi) seg[v]=seg[v*2];
    else seg[v]=seg[v*2+1];
}
pair<int,int> qr(int a,int b,int p=0,int k=SS-1,int v=1){
    if(p>b or k<a) return {INFi,-1};
    if(p>=a and k<=b) return seg[v];
    push(v);
    int sr=(p+k)/2;
    pair<int,int> q1=qr(a,b,p,sr,v*2),q2=qr(a,b,sr+1,k,v*2+1);
    if(q1.fi<q2.fi) return q1;
    return q2;
}
void build(int v){
    if(v>=SS){
        int id=v-SS;
        if(id>=1 and id<=n) seg[v]={t[id],id};
        else seg[v]={INFi,id};
    }else{
        build(v*2),build(v*2+1);
        if(seg[v*2].fi<seg[v*2+1].fi) seg[v]=seg[v*2];
        else seg[v]=seg[v*2+1];
    }
}
void zn(int a){
    if(a>=k){
        pair<int,int> xd=qr(a-k+1,a-1);
        if(xd.fi==0) zn(xd.se);
        t2[a]=--li;
    }else{
        pair<int,int> xd=qr(1,a-1);
        if(xd.fi==0) zn(xd.se);
        else{
            xd=qr(n-(k-a)+1,n);
            if(xd.fi==0) zn(xd.se);
        }
        t2[a]=--li;
    }
    if(a>=k) upd(a-k+1,a-1,-1);
    else{
        upd(1,a-1,-1);
        upd(n-(k-a)+1,n,-1);
    }
    upd(a,a,INFi);
}
void init(int kk,vi r){
    k=kk;
    n=r.size();
    for(int i=1;i<=n;i++) t[i]=r[i-1];
    build(1);
    li=n+1;
    pair<int,int> curr=qr(1,n);
    while(curr.fi==0){
        zn(curr.se);
        curr=qr(1,n);
    }
    for(int i=n+1;i<=n*2;i++) t2[i]=t2[i-n];        
    for(int i=1;i<=n;i++) g[t2[i]]=i;
    n*=2;
    for(int i=1;i<=n;i++) t[i]=INFi;
    build(1);
    n/=2;
    for(int i=n;i>=1;i--){
        upd(g[i],g[i],-INFi+i); 
        upd(g[i]+n,g[i]+n,-INFi+i); 
        pair<int,int> xd=qr(g[i]+1,g[i]+k-1);
        if(xd.fi>=INFi) jp[g[i]][0]=g[i],jp[g[i]+n][0]=n+g[i];
        else{
            jp[g[i]][0]=xd.se;
            if(xd.se<=n) jp[g[i]+n][0]=xd.se+n;
            else jp[g[i]+n][0]=g[i]+n;
        }
        xd=qr(g[i]+n-k+1,g[i]+n-1);
        if(xd.fi>=INFi) jp2[g[i]][0]=g[i],jp2[g[i]+n][0]=n+g[i];
        else{
            jp2[g[i]+n][0]=xd.se;
            if(xd.se>n) jp2[g[i]][0]=xd.se-n;
            else jp2[g[i]][0]=g[i];
        }
    }
    //for(int i=1;i<=n;i++) cout<<jp[i][0]<<" ";
    //cout<<"\n";
    for(int i2=1;i2<L;i2++){
        for(int i=1;i<=n*2;i++){
            jp[i][i2]=jp[jp[i][i2-1]][i2-1];
            jp2[i][i2]=jp2[jp2[i][i2-1]][i2-1];
        }
    }
}
int compare_plants(int x,int y){
    x++,y++;
    int curr=x; 
    for(int i=L-1;i>=0;i--)
        if(jp[curr][i]<=y) curr=jp[curr][i];
    int curr2=y;
    for(int i=L-1;i>=0;i--)
        if(jp[curr2][i]<=x+n) curr2=jp[curr2][i];
    if(t2[curr]<=t2[y] and y-curr<k) return -1;
    if(t2[curr2]<=t2[x+n] and x+n-curr2<k) return 1;
    curr=y; 
    for(int i=L-1;i>=0;i--){
        if(jp2[curr][i]>=x) curr=jp2[curr][i];
    }
    curr2=x+n;
    for(int i=L-1;i>=0;i--){
        if(jp2[curr2][i]>=y) curr2=jp2[curr2][i];
    }
    if(t2[curr]<=t2[x] and curr-x<k) return 1;
    if(t2[curr2]<=t2[y] and curr2-y<k) return -1;
    return 0;
}

• 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