oj.uz

Submission #415179

# Submission time Handle Problem Language Result Execution time Memory
415179 2021-05-31T16:03:23 Z MKopchev Comparing Plants (IOI20_plants) C++14
14 / 100
 4000 ms 136676 KB 
#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[2*nmax],go_right[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[i]=query(1,1,2*my_n,i+1,i+my_k-1,outp[i]);

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

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

        go_left[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[i]==-1)go_left[i-my_n]=-1;
        else go_left[i-my_n]=go_right[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;
    */
}

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;

    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;



    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;

    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;

    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37836 KB Output is correct
2 Correct 20 ms 37884 KB Output is correct
3 Correct 25 ms 37864 KB Output is correct
4 Correct 25 ms 37836 KB Output is correct
5 Incorrect 21 ms 37848 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 37900 KB Output is correct
2 Correct 22 ms 37908 KB Output is correct
3 Correct 29 ms 37876 KB Output is correct
4 Correct 25 ms 37836 KB Output is correct
5 Correct 25 ms 37872 KB Output is correct
6 Correct 30 ms 38252 KB Output is correct
7 Correct 104 ms 42692 KB Output is correct
8 Correct 23 ms 37964 KB Output is correct
9 Correct 28 ms 38196 KB Output is correct
10 Correct 104 ms 42688 KB Output is correct
11 Correct 193 ms 42644 KB Output is correct
12 Correct 671 ms 42776 KB Output is correct
13 Correct 104 ms 42692 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 37900 KB Output is correct
2 Correct 22 ms 37908 KB Output is correct
3 Correct 29 ms 37876 KB Output is correct
4 Correct 25 ms 37836 KB Output is correct
5 Correct 25 ms 37872 KB Output is correct
6 Correct 30 ms 38252 KB Output is correct
7 Correct 104 ms 42692 KB Output is correct
8 Correct 23 ms 37964 KB Output is correct
9 Correct 28 ms 38196 KB Output is correct
10 Correct 104 ms 42688 KB Output is correct
11 Correct 193 ms 42644 KB Output is correct
12 Correct 671 ms 42776 KB Output is correct
13 Correct 104 ms 42692 KB Output is correct
14 Correct 214 ms 49288 KB Output is correct
15 Correct 1972 ms 134360 KB Output is correct
16 Correct 229 ms 51152 KB Output is correct
17 Correct 1896 ms 136488 KB Output is correct
18 Execution timed out 4054 ms 136676 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 37836 KB Output is correct
2 Correct 25 ms 37796 KB Output is correct
3 Incorrect 223 ms 41284 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37836 KB Output is correct
2 Correct 26 ms 37832 KB Output is correct
3 Correct 29 ms 37904 KB Output is correct
4 Incorrect 22 ms 37836 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 37812 KB Output is correct
2 Correct 25 ms 37792 KB Output is correct
3 Correct 26 ms 37836 KB Output is correct
4 Incorrect 27 ms 37908 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 37836 KB Output is correct
2 Correct 20 ms 37884 KB Output is correct
3 Correct 25 ms 37864 KB Output is correct
4 Correct 25 ms 37836 KB Output is correct
5 Incorrect 21 ms 37848 KB Output isn't correct
6 Halted 0 ms 0 KB -