oj.uz

Submission #415206

# Submission time Handle Problem Language Result Execution time Memory
415206 2021-05-31T16:41:21 Z MKopchev Comparing Plants (IOI20_plants) C++14
100 / 100
 2362 ms 197612 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[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)
{
    if(x>RHS)return x;

    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)
{
    if(x<LHS)return x;

    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);
    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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 38092 KB Output is correct
2 Correct 21 ms 38092 KB Output is correct
3 Correct 21 ms 38124 KB Output is correct
4 Correct 26 ms 38168 KB Output is correct
5 Correct 26 ms 38116 KB Output is correct
6 Correct 113 ms 40900 KB Output is correct
7 Correct 341 ms 55396 KB Output is correct
8 Correct 1600 ms 193852 KB Output is correct
9 Correct 1851 ms 193956 KB Output is correct
10 Correct 1867 ms 193860 KB Output is correct
11 Correct 1859 ms 193952 KB Output is correct
12 Correct 1586 ms 193868 KB Output is correct
13 Correct 1169 ms 193764 KB Output is correct
14 Correct 1430 ms 193896 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 38092 KB Output is correct
2 Correct 25 ms 38092 KB Output is correct
3 Correct 22 ms 38092 KB Output is correct
4 Correct 26 ms 38132 KB Output is correct
5 Correct 23 ms 38220 KB Output is correct
6 Correct 27 ms 38840 KB Output is correct
7 Correct 122 ms 44484 KB Output is correct
8 Correct 27 ms 38216 KB Output is correct
9 Correct 31 ms 38808 KB Output is correct
10 Correct 124 ms 44484 KB Output is correct
11 Correct 113 ms 44488 KB Output is correct
12 Correct 147 ms 44612 KB Output is correct
13 Correct 115 ms 44500 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 38092 KB Output is correct
2 Correct 25 ms 38092 KB Output is correct
3 Correct 22 ms 38092 KB Output is correct
4 Correct 26 ms 38132 KB Output is correct
5 Correct 23 ms 38220 KB Output is correct
6 Correct 27 ms 38840 KB Output is correct
7 Correct 122 ms 44484 KB Output is correct
8 Correct 27 ms 38216 KB Output is correct
9 Correct 31 ms 38808 KB Output is correct
10 Correct 124 ms 44484 KB Output is correct
11 Correct 113 ms 44488 KB Output is correct
12 Correct 147 ms 44612 KB Output is correct
13 Correct 115 ms 44500 KB Output is correct
14 Correct 241 ms 55528 KB Output is correct
15 Correct 1920 ms 193828 KB Output is correct
16 Correct 242 ms 55616 KB Output is correct
17 Correct 1912 ms 193900 KB Output is correct
18 Correct 1291 ms 193868 KB Output is correct
19 Correct 1593 ms 195940 KB Output is correct
20 Correct 2052 ms 196020 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 38188 KB Output is correct
2 Correct 22 ms 38108 KB Output is correct
3 Correct 161 ms 42304 KB Output is correct
4 Correct 1998 ms 193708 KB Output is correct
5 Correct 1952 ms 196576 KB Output is correct
6 Correct 2028 ms 196924 KB Output is correct
7 Correct 2148 ms 196892 KB Output is correct
8 Correct 2056 ms 197104 KB Output is correct
9 Correct 1678 ms 196460 KB Output is correct
10 Correct 1595 ms 196432 KB Output is correct
11 Correct 1014 ms 196384 KB Output is correct
12 Correct 1491 ms 196636 KB Output is correct
13 Correct 1325 ms 196556 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 38100 KB Output is correct
2 Correct 28 ms 38128 KB Output is correct
3 Correct 29 ms 38148 KB Output is correct
4 Correct 24 ms 38148 KB Output is correct
5 Correct 24 ms 38132 KB Output is correct
6 Correct 32 ms 38212 KB Output is correct
7 Correct 58 ms 38948 KB Output is correct
8 Correct 44 ms 38936 KB Output is correct
9 Correct 50 ms 38932 KB Output is correct
10 Correct 44 ms 38920 KB Output is correct
11 Correct 52 ms 38908 KB Output is correct
12 Correct 52 ms 38976 KB Output is correct
13 Correct 40 ms 38964 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 38080 KB Output is correct
2 Correct 29 ms 38148 KB Output is correct
3 Correct 27 ms 38096 KB Output is correct
4 Correct 29 ms 38120 KB Output is correct
5 Correct 28 ms 38732 KB Output is correct
6 Correct 1913 ms 193776 KB Output is correct
7 Correct 1752 ms 193820 KB Output is correct
8 Correct 1545 ms 193792 KB Output is correct
9 Correct 1932 ms 193848 KB Output is correct
10 Correct 1859 ms 194020 KB Output is correct
11 Correct 1564 ms 193836 KB Output is correct
12 Correct 1324 ms 195920 KB Output is correct
13 Correct 1680 ms 196088 KB Output is correct
14 Correct 1458 ms 196448 KB Output is correct
15 Correct 1812 ms 196472 KB Output is correct
16 Correct 1344 ms 195896 KB Output is correct
17 Correct 1474 ms 196172 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 38092 KB Output is correct
2 Correct 21 ms 38092 KB Output is correct
3 Correct 21 ms 38124 KB Output is correct
4 Correct 26 ms 38168 KB Output is correct
5 Correct 26 ms 38116 KB Output is correct
6 Correct 113 ms 40900 KB Output is correct
7 Correct 341 ms 55396 KB Output is correct
8 Correct 1600 ms 193852 KB Output is correct
9 Correct 1851 ms 193956 KB Output is correct
10 Correct 1867 ms 193860 KB Output is correct
11 Correct 1859 ms 193952 KB Output is correct
12 Correct 1586 ms 193868 KB Output is correct
13 Correct 1169 ms 193764 KB Output is correct
14 Correct 1430 ms 193896 KB Output is correct
15 Correct 21 ms 38092 KB Output is correct
16 Correct 25 ms 38092 KB Output is correct
17 Correct 22 ms 38092 KB Output is correct
18 Correct 26 ms 38132 KB Output is correct
19 Correct 23 ms 38220 KB Output is correct
20 Correct 27 ms 38840 KB Output is correct
21 Correct 122 ms 44484 KB Output is correct
22 Correct 27 ms 38216 KB Output is correct
23 Correct 31 ms 38808 KB Output is correct
24 Correct 124 ms 44484 KB Output is correct
25 Correct 113 ms 44488 KB Output is correct
26 Correct 147 ms 44612 KB Output is correct
27 Correct 115 ms 44500 KB Output is correct
28 Correct 241 ms 55528 KB Output is correct
29 Correct 1920 ms 193828 KB Output is correct
30 Correct 242 ms 55616 KB Output is correct
31 Correct 1912 ms 193900 KB Output is correct
32 Correct 1291 ms 193868 KB Output is correct
33 Correct 1593 ms 195940 KB Output is correct
34 Correct 2052 ms 196020 KB Output is correct
35 Correct 22 ms 38188 KB Output is correct
36 Correct 22 ms 38108 KB Output is correct
37 Correct 161 ms 42304 KB Output is correct
38 Correct 1998 ms 193708 KB Output is correct
39 Correct 1952 ms 196576 KB Output is correct
40 Correct 2028 ms 196924 KB Output is correct
41 Correct 2148 ms 196892 KB Output is correct
42 Correct 2056 ms 197104 KB Output is correct
43 Correct 1678 ms 196460 KB Output is correct
44 Correct 1595 ms 196432 KB Output is correct
45 Correct 1014 ms 196384 KB Output is correct
46 Correct 1491 ms 196636 KB Output is correct
47 Correct 1325 ms 196556 KB Output is correct
48 Correct 24 ms 38100 KB Output is correct
49 Correct 28 ms 38128 KB Output is correct
50 Correct 29 ms 38148 KB Output is correct
51 Correct 24 ms 38148 KB Output is correct
52 Correct 24 ms 38132 KB Output is correct
53 Correct 32 ms 38212 KB Output is correct
54 Correct 58 ms 38948 KB Output is correct
55 Correct 44 ms 38936 KB Output is correct
56 Correct 50 ms 38932 KB Output is correct
57 Correct 44 ms 38920 KB Output is correct
58 Correct 52 ms 38908 KB Output is correct
59 Correct 52 ms 38976 KB Output is correct
60 Correct 40 ms 38964 KB Output is correct
61 Correct 204 ms 43968 KB Output is correct
62 Correct 384 ms 57696 KB Output is correct
63 Correct 2261 ms 196732 KB Output is correct
64 Correct 2120 ms 196956 KB Output is correct
65 Correct 2086 ms 197120 KB Output is correct
66 Correct 2037 ms 197436 KB Output is correct
67 Correct 2161 ms 197612 KB Output is correct
68 Correct 2109 ms 196928 KB Output is correct
69 Correct 1846 ms 197436 KB Output is correct
70 Correct 1825 ms 196764 KB Output is correct
71 Correct 2362 ms 197024 KB Output is correct
72 Correct 2200 ms 197120 KB Output is correct
73 Correct 2067 ms 197464 KB Output is correct
74 Correct 2151 ms 196804 KB Output is correct
75 Correct 1726 ms 197060 KB Output is correct