Submission #1078234

#	Time	Username	Problem	Language	Result	Execution time	Memory
1078234		anango	Comparing Plants (IOI20_plants)	C++17	27 / 100	487 ms	10020 KiB

plants

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

int K;
int n;
vector<int> b;
int INF = 1LL<<30;

int tree[524288];
int lazy[524288]; //min add segtree

void push(int v, int tl, int tr) {
    if (tl<tr) {
        lazy[2*v]+=lazy[v];
        lazy[2*v+1]+=lazy[v];
    }
    tree[v]+=lazy[v];
    lazy[v] = 0;
}

void update(int v, int l, int r, int tl, int tr, int addend) {
    push(v,tl,tr);
    if (l>tr || r<tl) return;
    if (l<=tl && tr<=r) {
        if (tl<tr) {
            lazy[2*v]+=addend;
            lazy[2*v+1]+=addend;
        }
        tree[v]+=addend;
        return;
    }
    int m = (tl+tr)/2;
    update(2*v,l,r,tl,m,addend);
    update(2*v+1,l,r,m+1,tr,addend);
    tree[v] = min(tree[2*v],tree[2*v+1]);
}

int query(int v, int l, int r, int tl, int tr) {
    push(v,tl,tr);
    if (l>tr || r<tl) return INF;
    if (l<=tl && tr<=r) return tree[v];
    int m = (tl+tr)/2;
    return min(query(2*v,l,r,tl,m),query(2*v+1,l,r,m+1,tr));
}

int query2(int v, int l, int r, int tl, int tr) {
    //cout << v <<" " << l <<" " << r <<" " << tl <<" " << tr << endl;
    //finds the first 0 in range (l,r)
    push(v,tl,tr);
    if (l>tr || r<tl) return INF;
    /*for (int i=l; i<=r; i++) {
        update(1,i,i,0,262143,0); //to push
        if (tree[262144+i]==0) {
            return i;
        }
    }*/
    if (tree[v]>0) return INF;
    if (tl==tr) {
        return tl;
    }
    int m = (tl+tr)/2;
    int an = query2(2*v,l,r,tl,m);
    if (an!=INF) {
        return an;
    }
    return query2(2*v+1,l,r,m+1,tr);


}

vector<int> p;
vector<int> pref;

int cyclicpref(int l, int r) {
    if (l<=r) {
        return pref[r+1]-pref[l];
    }
    return (pref[n]-pref[l])+(pref[r+1]); 
}

void init(int k, std::vector<int> r) {
    for (int i=0; i<524288; i++) tree[i] = lazy[i] = INF;
    K=k;
    b=r;
    n=r.size();
    p=vector<int>(n,-1);
    if (K==2) {
        pref=vector<int>(n+1,0);
        for (int i=0; i<n; i++) {
            pref[i+1] = pref[i] + r[i];
        }
        return;
    }
    for (int i=0; i<n; i++) {
        update(1,i,i,0,262143,r[i]);
    }
    //let l[i] be the number of plants j in the k-1 indices before i such that i is higher than j
    //any 0 value is higher than the k-1 indices after it
    //get any 0 that does not have a 0 in the k-1 indices before
    //and subtract 1 from these indices
    int height = n;
    for (int op=0; op<n; op++) {
        /*cout << "SEGTREE STATE" << endl;
        for (int i=0; i<n; i++) {
            cout << query(1,i,i,0,262143) <<" ";
        }
        cout << endl;*/
        int x = query2(1,0,n-1,0,262143);
        assert(x!=INF);
        int li = x-k+1; li%=n; li+=n; li%=n;
        int ri = x-1; ri%=n; ri+=n; ri%=n;
        int an = INF;
        int jambloat = -1;
        
        if (li<=ri) {
            an=min(query(1,li,ri,0,262143),INF);
        }
        else {
            an=min(query(1,li,n-1,0,262143),query(1,0,ri,0,262143));
        }
        if (an!=0) {
            jambloat = x;
        }
        else {
            if (li<=ri) {
                jambloat=min(query2(1,li,ri,0,262143),INF);
            }
            else {
                if (query2(1,li,n-1,0,262143)>=INF/2) {
                    jambloat = query2(1,0,ri,0,262143);
                }
                else {
                    jambloat=query2(1,li,n-1,0,262143);  
                }
            }
        }
        li = jambloat-k+1; li%=n; li+=n; li%=n;
        ri = jambloat-1; ri%=n; ri+=n; ri%=n;
        if (li<=ri) {
            update(1,li,ri,0,262143,-1);
        }
        else {
            update(1,li,n-1,0,262143,-1);
            update(1,0,ri,0,262143,-1);
        }
        update(1,jambloat,jambloat,0,262143,INF-query(1,jambloat,jambloat,0,262143));
        //cout << "doing " << jambloat << endl;
        p[jambloat] = height;
        height--;

    }
    /*for (int i=0; i<n; i++) {
        cout << p[i] <<" ";
    }
    cout << endl;*/
	return;
}

int pre(int x) {
    x--;
    x+=n;
    x%=n;
    return x;
}

int compare_plants(int x, int y) {
    if (K==2) {
        int c1 = cyclicpref(x,pre(y));
        int c2 = cyclicpref(y,pre(x));
        int m1 = (y-x+8*n)%n;
        int m2 = (x-y+8*n)%n;
        if (m1==c1) {
            return -1;
        }
        if (m2==c2) {
            return 1;
        }
        return 0;
    }
    if (p[x]>p[y]) return 1;
    else if (p[x]<p[y]) return -1;
	return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25