oj.uz

Submission #415172

# Submission time Handle Problem Language Result Execution time Memory
415172 2021-05-31T15:46:18 Z MKopchev Comparing Plants (IOI20_plants) C++14
14 / 100
 4000 ms 136332 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)
    {
        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;

        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,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)
    {
        if(l<=my_n)tree_merge[node].push_back({outp[l],l});
        else tree_merge[node].push_back({outp[l-my_n],l});
        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());
}

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++)
    {
        go_left[i]=query(1,1,2*my_n,i-(my_k-1),i-1,outp[i-my_n]);

        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 26 ms 37920 KB Output is correct
2 Correct 22 ms 37836 KB Output is correct
3 Correct 26 ms 37832 KB Output is correct
4 Incorrect 24 ms 37824 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 37848 KB Output is correct
2 Correct 28 ms 37796 KB Output is correct
3 Correct 27 ms 37860 KB Output is correct
4 Correct 26 ms 37796 KB Output is correct
5 Correct 27 ms 37836 KB Output is correct
6 Correct 31 ms 38320 KB Output is correct
7 Correct 113 ms 44236 KB Output is correct
8 Correct 25 ms 38012 KB Output is correct
9 Correct 31 ms 38340 KB Output is correct
10 Correct 118 ms 44208 KB Output is correct
11 Correct 150 ms 44088 KB Output is correct
12 Correct 196 ms 44340 KB Output is correct
13 Correct 109 ms 44248 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 37848 KB Output is correct
2 Correct 28 ms 37796 KB Output is correct
3 Correct 27 ms 37860 KB Output is correct
4 Correct 26 ms 37796 KB Output is correct
5 Correct 27 ms 37836 KB Output is correct
6 Correct 31 ms 38320 KB Output is correct
7 Correct 113 ms 44236 KB Output is correct
8 Correct 25 ms 38012 KB Output is correct
9 Correct 31 ms 38340 KB Output is correct
10 Correct 118 ms 44208 KB Output is correct
11 Correct 150 ms 44088 KB Output is correct
12 Correct 196 ms 44340 KB Output is correct
13 Correct 109 ms 44248 KB Output is correct
14 Correct 453 ms 51040 KB Output is correct
15 Execution timed out 4026 ms 136332 KB Time limit exceeded
16 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 37800 KB Output is correct
3 Incorrect 95 ms 41316 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 37828 KB Output is correct
2 Correct 26 ms 37856 KB Output is correct
3 Incorrect 26 ms 37896 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 37916 KB Output is correct
2 Correct 26 ms 37800 KB Output is correct
3 Incorrect 26 ms 37944 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

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