Submission #415197

#	Time	Username	Problem	Language	Result	Execution time	Memory
415197		MKopchev	Comparing Plants (IOI20_plants)	C++14	5 / 100	1904 ms	196932 KiB

plants

#include "plants.h"
#include<bits/stdc++.h>
using namespace std;

const int nmax=2e5+42;

int my_n,my_k;
int inp[nmax];

struct info
{
    int mini,lazy;
    int pos;
};
info tree[4*nmax];

void push(int node)
{
    tree[node*2].lazy+=tree[node].lazy;
    tree[node*2+1].lazy+=tree[node].lazy;
    tree[node].lazy=0;
}

info actual(info a)
{
    a.mini+=a.lazy;
    a.lazy=0;
    return a;
}
info my_merge(info a,info b)
{
    a=actual(a);
    b=actual(b);

    if(a.mini<b.mini)return a;
    if(a.mini>b.mini)return b;

    if(b.pos-a.pos<=my_k-1)return a;
    return b;
}

void build(int node,int l,int r)
{
    if(l==r)
    {
        tree[node].mini=inp[l];
        tree[node].lazy=0;
        tree[node].pos=l;

        return;
    }

    int av=(l+r)/2;
    build(node*2,l,av);
    build(node*2+1,av+1,r);

    tree[node]=my_merge(tree[node*2],tree[node*2+1]);
}

void update(int node,int l,int r,int lq,int rq,int val)
{
    if(l==lq&&r==rq)
    {
        tree[node].lazy+=val;
        return;
    }

    push(node);

    int av=(l+r)/2;

    if(lq<=av)update(node*2,l,av,lq,min(av,rq),val);
    if(av<rq)update(node*2+1,av+1,r,max(av+1,lq),rq,val);

    tree[node]=my_merge(tree[node*2],tree[node*2+1]);
}
int outp[2*nmax];

set<int> zeros,legit;

void test(int pos)
{
    if(zeros.size()==1)
    {
        legit.insert(pos);
        return;
    }

    set<int>::iterator it=zeros.lower_bound(pos);

    if(it==zeros.begin())it=zeros.end();

    it--;

    int prv=*it;

    if(prv>pos)prv=prv-my_n;

    //cout<<"testing "<<pos<<" : prv= "<<prv<<endl;

    if(pos-prv>=my_k)legit.insert(pos);
}
void add(int pos)
{
    if(zeros.size()==0)
    {
        zeros.insert(pos);
        legit.insert(pos);
        return;
    }

    zeros.insert(pos);

    set<int>::iterator it=zeros.lower_bound(pos);
    it++;

    if(it==zeros.end())it=zeros.begin();

    int nxt=*it;

    legit.erase(nxt);

    test(nxt);
    test(pos);
}

void sub(int pos)
{
    legit.erase(pos);
    zeros.erase(pos);

    if(zeros.size()==0)
    {
        return;
    }

    set<int>::iterator it=zeros.lower_bound(pos);
    if(it==zeros.end())it=zeros.begin();

    test(*it);
}

int pref[nmax];

vector< pair<int/*outp*/,int/*id*/> > tree_merge[4*2*nmax];

int query(int node,int l,int r,int lq,int rq,int val)//position of the highest in [lq, rq] up to val
{
    if(l==lq&&r==rq)
    {
        //cout<<"query "<<node<<" "<<lq<<" "<<rq<<" "<<val<<endl;

        int p=lower_bound(tree_merge[node].begin(),tree_merge[node].end(),make_pair(val,0))-tree_merge[node].begin();

        p--;

        if(p<0)return -1;

        //cout<<"p= "<<p<<" merge= "<<tree_merge[node][p].first<<" , "<<tree_merge[node][p].second<<endl;

        return tree_merge[node][p].second;
    }

    int ret=-1;

    int av=(l+r)/2;

    if(lq<=av)
    {
        int help=query(node*2,l,av,lq,min(av,rq),val);

        if(ret==-1)ret=help;
    }

    if(av<rq)
    {
        int help=query(node*2+1,av+1,r,max(av+1,lq),rq,val);

        if(ret==-1)ret=help;
        else if(help!=-1)
        {
            if(outp[ret]<outp[help])ret=help;
        }
    }

    return ret;
}

void build_merge(int node,int l,int r)
{
    if(l==r)
    {
        tree_merge[node].push_back({outp[l],l});
        /*
        cout<<node<<" "<<l<<" "<<r<<" : ";

        for(auto w:tree_merge[node])cout<<w.first<<" "<<w.second<<"\t";cout<<endl;
        */
        return;
    }

    int av=(l+r)/2;
    build_merge(node*2,l,av);
    build_merge(node*2+1,av+1,r);

    tree_merge[node]=tree_merge[node*2];
    for(auto w:tree_merge[node*2+1])tree_merge[node].push_back(w);

    sort(tree_merge[node].begin(),tree_merge[node].end());

    /*
    cout<<node<<" "<<l<<" "<<r<<" : ";

    for(auto w:tree_merge[node])cout<<w.first<<" "<<w.second<<"\t";cout<<endl;
    */
}

int go_left[20][2*nmax],go_right[20][2*nmax];

void init(int k, std::vector<int> r) {
	my_n=r.size();
	my_k=k;

	for(int i=1;i<=my_n;i++)inp[i]=r[i-1];

	for(int i=1;i<=my_n;i++)pref[i]=pref[i-1]+inp[i];

	build(1,1,my_n);

	for(int i=1;i<=my_n;i++)
    {
        while(1)
        {
            info cur=actual(tree[1]);

            if(cur.mini)break;

            int pos=cur.pos;

            update(1,1,my_n,pos,pos,1e9);

            add(pos);
        }

        /*
        cout<<"i= "<<i<<endl;
        cout<<"zeros= ";for(auto w:zeros)cout<<w<<" ";cout<<endl;
        cout<<"legit= ";for(auto w:legit)cout<<w<<" ";cout<<endl;
        */

        //cout<<"pos= "<<pos<<endl;
        int pos=*legit.begin();

        sub(pos);

        outp[pos]=my_n-i;

        int l=pos-(k-1);
        int r=pos-1;

        if(1<=l)update(1,1,my_n,l,r,-1);
        else
        {
            l=l+my_n;

            //cout<<"other "<<l<<" "<<my_n<<" and "<<1<<" "<<r<<endl;

            update(1,1,my_n,l,my_n,-1);

            if(r>=1)update(1,1,my_n,1,r,-1);
        }
    }

    for(int i=1;i<=my_n;i++)outp[i+my_n]=outp[i];

    //for(int i=1;i<=my_n;i++)printf("%i ",outp[i]);printf("\n");

    build_merge(1,1,2*my_n);

    for(int i=1;i<=my_n;i++)
    {
        go_right[0][i]=query(1,1,2*my_n,i+1,i+my_k-1,outp[i]);

        if(go_right[0][i]==-1)go_right[0][my_n+i]=-1;
        else go_right[0][my_n+i]=go_right[0][i]+my_n;
    }

    for(int i=my_n+1;i<=my_n+my_n;i++)
    {
        //cout<<"i= "<<i<<" : ";

        go_left[0][i]=query(1,1,2*my_n,i-(my_k-1),i-1,outp[i-my_n]);

        //cout<<"go_left= "<<go_left[i]<<endl;

        if(go_left[0][i]==-1)go_left[0][i-my_n]=-1;
        else go_left[0][i-my_n]=go_left[0][i]-my_n;
    }

    /*
    cout<<"go_left: ";for(int i=1;i<=2*my_n;i++)cout<<go_left[i]<<" ";cout<<endl;
    cout<<"go_right: ";for(int i=1;i<=2*my_n;i++)cout<<go_right[i]<<" ";cout<<endl;
    */

    for(int step=1;step<20;step++)
    {
        for(int i=1;i<=2*my_n;i++)
        {
            int u=go_left[step-1][i];

            if(u<0||u>2*my_n)go_left[step][i]=u;
            else go_left[step][i]=go_left[step-1][u];

            int v=go_right[step-1][i];

            if(v<0||v>2*my_n)go_right[step][i]=v;
            else go_right[step][i]=go_right[step-1][v];

        }
    }
}

int jump_right(int x,int RHS)
{
    for(int i=19;i>=0;i--)
        if(0<=go_right[i][x]&&go_right[i][x]<=RHS)x=go_right[i][x];

    return go_right[0][x];
}

int jump_left(int x,int LHS)
{
    for(int i=19;i>=0;i--)
        if(0<=go_left[i][x]&&go_left[i][x]>=LHS)x=go_left[i][x];

    return go_left[0][x];
}
int compare_plants(int x, int y) {
    x++;
    y++;

    /*
    int x_help=x;
    while(x_help>=0&&x_help<=y-my_k)x_help=go_right[x_help];
    if(x_help>=0&&outp[x_help]>=outp[y])return 1;
    */
    int x_help=jump_right(x,y-my_k+1);
    if(x_help>=0&&outp[x_help]>=outp[y])return 1;

    /*
    x_help=x+my_n;
    while(x_help>=0&&x_help>=y+my_k)x_help=go_left[x_help];
    if(x_help>=0&&outp[x_help]>=outp[y])return 1;
    */
    x_help=jump_left(x+my_n,y+my_k);
    if(x_help>=0&&outp[x_help]>=outp[y])return 1;

    /*
    int y_help=y;
    while(y_help>=0&&y_help>=x+my_k)y_help=go_left[y_help];
    if(y_help>=0&&outp[y_help]>=outp[x])return -1;
    */
    int y_help=jump_left(y,x+my_k);
    if(y_help>=0&&outp[y_help]>=outp[x])return -1;

    /*
    y_help=y;
    while(y_help>=0&&y_help<=x+my_n-my_k)y_help=go_right[y_help];
    if(y_help>=0&&outp[y_help]>=outp[x])return -1;
    */
    y_help=jump_right(y,x+my_n-my_k);
    if(y_help>=0&&outp[y_help]>=outp[x])return -1;

    return 0;
}
/*
static int n, k, q;
static std::vector<int> r;
static std:: vector<int> x;
static std:: vector<int> y;
static std:: vector<int> answer;
int main() {
	assert(scanf("%d%d%d", &n, &k, &q) == 3);
	r.resize(n);
	answer.resize(q);
	for (int i = 0; i < n; i++) {
		int value;
		assert(scanf("%d", &value) == 1);
		r[i] = value;
	}
	x.resize(q);
	y.resize(q);
	for (int i = 0; i < q; i++) {
		assert(scanf("%d%d", &x[i], &y[i]) == 2);
	}
	fclose(stdin);

	init(k, r);
	for (int i = 0; i < q; i++) {
		answer[i] = compare_plants(x[i], y[i]);
	}

	for (int i = 0; i < q; i++) {
		printf("%d\n", answer[i]);
	}

	fclose(stdout);

	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