Submission #537798

#	Time	Username	Problem	Language	Result	Execution time	Memory
537798		EqualTurtle	Comparing Plants (IOI20_plants)	C++14	100 / 100	1157 ms	61732 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int pot = 262144;
constexpr int inf = 1e9 + 7;

class Tree{
public:
	int b[pot * 2 + 7]; // - pot
	int e[pot * 2 + 7]; // - pot
	int mini[pot * 2 + 7];
	int lazy[pot * 2 + 7]; // < 0
	int lmo[pot * 2 + 7]; // if no 0 than -1                - pot
	int rmo[pot * 2 + 7]; // if no 0 than -1                - pot
	int cand[pot * 2 + 7]; // -1 <=> doesn't exist          - pot

	int k, n;

    void quick_update(int w){
        if (w >= pot)
            return;
        mini[w] = min(mini[w * 2], mini[w * 2 + 1]);
        lmo[w] = (mini[w * 2] == 0 ? lmo[w * 2] : lmo[w * 2 + 1]);
        rmo[w] = (mini[w * 2 + 1] == 0 ? rmo[w * 2 + 1] : rmo[w * 2]);

        if (max(cand[w * 2], cand[w * 2 + 1]) != -1)
            cand[w] = max(cand[w * 2], cand[w * 2 + 1]);
        else
        {
            if (mini[w * 2 + 1] == 0 && (lmo[w * 2 + 1] - max(rmo[w * 2], b[w * 2] - 1) >= k))
                cand[w] = lmo[w * 2 + 1];
            else
                cand[w] = -1;
        }

        if (w == 1 && cand[w] == -1)
            cand[w] = lmo[w];
    }

    void newo(int w){
        if (w >= pot){
            lmo[w] = w - pot;
            rmo[w] = w - pot;
            return;
        }
        push_lazy(w * 2);
        push_lazy(w * 2 + 1);
        quick_update(w);
    }

    void push_lazy(int w){
        if (lazy[w] == 0)
            return;
        
        if (w < pot){
            mini[w * 2] += lazy[w];
            lazy[w * 2] += lazy[w];
            mini[w * 2 + 1] += lazy[w];
            lazy[w * 2 + 1] += lazy[w];
        }
        lazy[w] = 0;

        if (mini[w] == 0)
            newo(w);
    }
	
	void init(int ck, vector <int> r){
		k = ck;
		n = (int)r.size();

        for (int i = pot; i < pot * 2; i++) // bottom layer
        {
            b[i] = i - pot;
            e[i] = i - pot;
            mini[i] = (i - pot < n ? r[i - pot] : inf);
            lazy[i] = 0;
            lmo[i] = (mini[i] == 0 ? i - pot : -1);
            rmo[i] = (mini[i] == 0 ? i - pot : -1);
            cand[i] = -1;
        }
        for (int i = pot - 1; i > 0; i--)
        {
            b[i] = b[i * 2];
            e[i] = e[i * 2 + 1];
            lazy[i] = 0;
            quick_update(i);
        }
	}

    void sub(int bq, int eq, int w){
        if (bq > e[w] || b[w] > eq)
            return;
        if (bq <= b[w] && e[w] <= eq){
            mini[w]--;
            lazy[w]--;
            push_lazy(w);
            return;
        }

        push_lazy(w);
        sub(bq, eq, w * 2);
        sub(bq, eq, w * 2 + 1);
        quick_update(w);
    }

    void del(int bq, int eq, int w){
        if (bq > e[w] || b[w] > eq)
            return;
        if (bq <= b[w] && e[w] <= eq){
            mini[w] = inf;
            lmo[w] = -1;
            rmo[w] = -1;
            cand[w] = -1;
            lazy[w] = 0;
            return;
        }
        
        push_lazy(w);
        del(bq, eq, w * 2);
        del(bq, eq, w * 2 + 1);
        quick_update(w);
    }

    int get_big(){
        int curr = cand[1];
        del(curr, curr, 1);

        if (curr - k + 1 >= 0)
            sub(curr - k + 1, curr, 1);
        else{
            sub(0, curr, 1);
            sub(n - k + curr + 1, n - 1, 1);
        }

        return curr;
    }
};

int n;
Tree tree;
vector <int> h;
vector <int> lef[23], rig[23];

void debug(){
    for (int i : lef[1])
		cout << i << " ";
	cout << "\n";
    for (int i : rig[1])
		cout << i << " ";
	cout << "\n";
}

int conv(int a, int b){
    return (a - b + n) % n;
}

void get_dag(int k)
{
    lef[0].resize(n);
    rig[0].resize(n);

    set <pair <int, int> > sett; // h, id
    for (int i = 1; i < k; i++)
        sett.insert({h[i], i});
    
    for (int i = 0; i < n; i++)
    {
        int j = (i + k) % n;
        set <pair <int, int> >::iterator it;
        it = sett.lower_bound(make_pair(h[i], i));
        if (it == sett.begin())
            rig[0][i] = -1;
        else
            rig[0][i] = prev(it)->second; 
        
        it = sett.lower_bound(make_pair(h[j], j));
        if (it == sett.begin())
            lef[0][j] = -1;
        else
            lef[0][j] = prev(it)->second; 

        // --------------------------------------------

        sett.erase(make_pair(h[(i + 1) % n], (i + 1) % n));
        sett.insert({h[j], j});
    }

    for (int step = 1; step <= 20; step++){
        lef[step].resize(n);
        rig[step].resize(n);

        for (int i = 0; i < n; i++){
            lef[step][i] = (lef[step - 1][i] > -1 ? lef[step - 1][lef[step - 1][i]] : -1);
            rig[step][i] = (rig[step - 1][i] > -1 ? rig[step - 1][rig[step - 1][i]] : -1);

            if (conv(lef[step - 1][i], i) < conv(lef[step][i], i))
                lef[step][i] = -1;
            if (conv(rig[step - 1][i], i) > conv(rig[step][i], i))
                rig[step][i] = -1;
        }
    }
}

void init(int k, vector<int> r) 
{
    n = (int)r.size();
	tree.init(k, r);
	h.resize(n);

	for (int i = n; i > 0; i--){
		int curr = tree.get_big();
		h[curr] = i;
	}

    get_dag(k);

	//debug();
	return;
}

bool is_path(int x, int y)
{
    int xl = x;
    for (int step = 20; step >= 0; step--){
        if (lef[step][xl] > -1 && conv(lef[step][xl], x) >= conv(y, x) && (conv(lef[step][xl], x) < conv(xl, x) || xl == x))
            xl = lef[step][xl];
    }
    
    if (xl == y)
        return true;
    
    if (lef[0][xl] > -1)
        if (h[y] < h[xl])
            return true;

    int xr = x;
    for (int step = 20; step >= 0; step--){
        if (rig[step][xr] > -1 && conv(rig[step][xr], x) <= conv(y, x) && conv(rig[step][xr], x) > conv(xr, x))
            xr = rig[step][xr];
    }
    
    if (xr == y)
        return true;
    
    if (rig[0][xr] > -1)
        if (h[y] < h[xr])
            return true;
    return false;
}

int compare_plants(int x, int y) {
    if (is_path(x, y)){
        return 1;
    }
    //return -1;
    if (is_path(y, x)){
        return -1;
    }
	return 0;
}

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