oj.uz

Submission #415189

# Submission time Handle Problem Language Result Execution time Memory
415189 2021-05-31T16:25:52 Z MKopchev Comparing Plants (IOI20_plants) C++14
25 / 100
 4000 ms 137248 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_left[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 25 ms 37968 KB Output is correct
2 Correct 24 ms 37892 KB Output is correct
3 Correct 24 ms 37892 KB Output is correct
4 Correct 26 ms 37892 KB Output is correct
5 Correct 22 ms 37856 KB Output is correct
6 Correct 84 ms 41600 KB Output is correct
7 Correct 233 ms 51340 KB Output is correct
8 Correct 809 ms 137116 KB Output is correct
9 Correct 898 ms 137184 KB Output is correct
10 Correct 1433 ms 137216 KB Output is correct
11 Execution timed out 4062 ms 137248 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 37888 KB Output is correct
2 Correct 30 ms 37856 KB Output is correct
3 Correct 32 ms 37884 KB Output is correct
4 Correct 24 ms 37892 KB Output is correct
5 Correct 24 ms 37908 KB Output is correct
6 Correct 32 ms 38284 KB Output is correct
7 Correct 108 ms 42820 KB Output is correct
8 Correct 25 ms 37972 KB Output is correct
9 Correct 32 ms 38220 KB Output is correct
10 Correct 127 ms 42880 KB Output is correct
11 Correct 190 ms 42720 KB Output is correct
12 Correct 586 ms 42844 KB Output is correct
13 Correct 140 ms 42820 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 37888 KB Output is correct
2 Correct 30 ms 37856 KB Output is correct
3 Correct 32 ms 37884 KB Output is correct
4 Correct 24 ms 37892 KB Output is correct
5 Correct 24 ms 37908 KB Output is correct
6 Correct 32 ms 38284 KB Output is correct
7 Correct 108 ms 42820 KB Output is correct
8 Correct 25 ms 37972 KB Output is correct
9 Correct 32 ms 38220 KB Output is correct
10 Correct 127 ms 42880 KB Output is correct
11 Correct 190 ms 42720 KB Output is correct
12 Correct 586 ms 42844 KB Output is correct
13 Correct 140 ms 42820 KB Output is correct
14 Correct 208 ms 49388 KB Output is correct
15 Correct 1806 ms 134404 KB Output is correct
16 Correct 194 ms 49284 KB Output is correct
17 Correct 1704 ms 134468 KB Output is correct
18 Execution timed out 4074 ms 134492 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 37836 KB Output is correct
2 Correct 24 ms 37876 KB Output is correct
3 Correct 237 ms 41428 KB Output is correct
4 Execution timed out 4082 ms 136752 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 37836 KB Output is correct
2 Correct 21 ms 37836 KB Output is correct
3 Correct 23 ms 37836 KB Output is correct
4 Correct 28 ms 37872 KB Output is correct
5 Correct 23 ms 37836 KB Output is correct
6 Correct 33 ms 37956 KB Output is correct
7 Correct 49 ms 38920 KB Output is correct
8 Correct 39 ms 38880 KB Output is correct
9 Correct 47 ms 38848 KB Output is correct
10 Correct 50 ms 38892 KB Output is correct
11 Correct 40 ms 38860 KB Output is correct
12 Correct 39 ms 38980 KB Output is correct
13 Correct 38 ms 38876 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 37888 KB Output is correct
2 Correct 23 ms 37808 KB Output is correct
3 Correct 30 ms 37808 KB Output is correct
4 Correct 30 ms 37896 KB Output is correct
5 Correct 27 ms 38168 KB Output is correct
6 Correct 1288 ms 136452 KB Output is correct
7 Correct 2125 ms 136768 KB Output is correct
8 Correct 1654 ms 136916 KB Output is correct
9 Correct 1869 ms 137092 KB Output is correct
10 Correct 2519 ms 136440 KB Output is correct
11 Execution timed out 4054 ms 137028 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 37968 KB Output is correct
2 Correct 24 ms 37892 KB Output is correct
3 Correct 24 ms 37892 KB Output is correct
4 Correct 26 ms 37892 KB Output is correct
5 Correct 22 ms 37856 KB Output is correct
6 Correct 84 ms 41600 KB Output is correct
7 Correct 233 ms 51340 KB Output is correct
8 Correct 809 ms 137116 KB Output is correct
9 Correct 898 ms 137184 KB Output is correct
10 Correct 1433 ms 137216 KB Output is correct
11 Execution timed out 4062 ms 137248 KB Time limit exceeded
12 Halted 0 ms 0 KB -