Submission #431834

#	Time	Username	Problem	Language	Result	Execution time	Memory
431834		Peti	Comparing Plants (IOI20_plants)	C++14	27 / 100	2788 ms	141576 KiB

plants

#include <bits/stdc++.h>
#include "plants.h"

using namespace std;

const int maxn = 1<<18, logn = 18;

pair<int, int> st[maxn<<1];
int add[maxn<<1] = {};

void prop(int x){
    if(x < maxn){
        add[2*x] += add[x];
        st[2*x].first += add[x];
        add[2*x+1] += add[x];
        st[2*x+1].first += add[x];
    }
    add[x] = 0;
}

inline void upd(int &x){
    if(x < maxn) st[x] = min(st[2*x], st[2*x+1]);
}

void build(vector<int> &v){
    for(int i = 0; i < (int)v.size(); i++)
        st[maxn+i] = make_pair(v[i], i);
    for(int i = maxn-1; i > 0; i--)
        upd(i);
}

void kivesz(int ind, int x, int l, int r){
    prop(x);
    if(l+1 == r){
        st[x].first = (int)1e9;
        return;
    }
    int m = (l+r)/2;
    if(ind < m)
        kivesz(ind, 2*x, l, m);
    else
        kivesz(ind, 2*x+1, m, r);
    upd(x);
}

void update(int s, int e, int x, int l, int r){
    prop(x);
    if(e <= l || r <= s)
        return;
    if(s <= l && r <= e){
        st[x].first--;
        add[x]--;
        return;
    }
    int m = (l+r)/2;
    update(s, e, 2*x, l, m);
    update(s, e, 2*x+1, m, r);
    upd(x);
}

void update(int l, int r, int n){
    if(l > r){
        update(l, n, 1, 0, maxn);
        update(0, r, 1, 0, maxn);
    } else
        update(l, r, 1, 0, maxn);
}

pair<int, int> keres(int s, int e, int x, int l, int r){
    prop(x);
    if(e <= l || r <= s)
        return make_pair((int)1e9, 0);
    if(s <= l && r <= e)
        return st[x];
    int m = (l+r)/2;
    return min(keres(s, e, 2*x, l, m), keres(s, e, 2*x+1, m, r));
}

int keres(int l, int r, int n){
    if(r < l){
        pair<int, int> temp = keres(l, n, 1, 0, maxn);
        if(temp.first == 0)
            return temp.second;
        temp = keres(0, r, 1, 0, maxn);
        if(temp.first == 0)
            return temp.second;
        return -1;
    }
    pair<int, int> temp = keres(l, r, 1, 0, maxn);
    if(temp.first == 0)
        return temp.second;
    return -1;
}

struct node{
    int l = -1, r = -1;
    long long lc, rc;
    vector<int> indL, indR;
    vector<long long> hL, hR;
};

vector<node> g;
vector<int> vh;
int n, K;

void init(int k, std::vector<int> r) {
    n = (int)r.size();
    K = k;
    g.resize(n);
    vh.resize(n);
    for(int &x : r)
        x = k-x-1;
    build(r);

    int x = keres(0, n, n), h = 0;
    vector<int> sor;
    while(x != -1){
        int y = keres((x-k+1 < 0 ? n+x-k+1 : x-k+1), x, n);
        while(y != -1){
            x = y;
            y = keres((x-k+1 < 0 ? n+x-k+1 : x-k+1), x, n);
        }
        vh[x] = h++;
        sor.push_back(x);
        update((x-k+1 < 0 ? n+x-k+1 : x-k+1), x, n);
        kivesz(x, 1, 0, maxn);
        x = keres(x+1, x, n);
    }

    set<pair<int, int>, greater<pair<int, int>>> nums;
    for(int i = n-k+1; i < n; i++)
        nums.insert(make_pair(vh[i], i));
    for(int i = 0; i < n; i++){
        auto it = nums.lower_bound(make_pair(vh[i], i));
        if(it != nums.end())
            g[i].l = it->second;

        int j = i-k+1;
        if(j < 0) j += n;
        nums.erase(make_pair(vh[j], j));
        nums.insert(make_pair(vh[i], i));
    }
    nums.clear();
    for(int i = 0; i < k-1; i++)
        nums.insert(make_pair(vh[i], i));
    for(int i = n-1; i >= 0; i--){
        auto it = nums.lower_bound(make_pair(vh[i], i));
        if(it != nums.end())
            g[i].r = it->second;

        int j = i+k-1;
        if(j >= n) j -= n;
        nums.erase(make_pair(vh[j], j));
        nums.insert(make_pair(vh[i], i));
    }

    for(int x : sor){
        g[x].lc = x - g[x].l;
        if(g[x].lc < 0) g[x].lc += n;
        g[x].rc = g[x].r - x;
        if(g[x].rc < 0) g[x].rc += n;
        if(g[x].l == -1)
            g[x].lc = 0;
        if(g[x].r == -1)
            g[x].rc = 0;
        g[x].indL.assign(logn, -1);
        g[x].indR.assign(logn, -1);
        g[x].hL.assign(logn, (long long)1e9);
        g[x].hR.assign(logn, (long long)1e9);
        g[x].indL[0] = g[x].l;
        g[x].hL[0] = g[x].lc;
        g[x].indR[0] = g[x].r;
        g[x].hR[0] = g[x].rc;
        for(int i = 1; i < logn; i++){
            if(g[x].indL[i-1] == -1)
                break;
            g[x].indL[i] = g[g[x].indL[i-1]].indL[i-1];
            if(g[x].indL[i] != -1)
                g[x].hL[i] = g[x].hL[i-1] + g[g[x].indL[i-1]].hL[i-1];
        }
        for(int i = 1; i < logn; i++){
            if(g[x].indR[i-1] == -1)
                break;
            g[x].indR[i] = g[g[x].indR[i-1]].indR[i-1];
            if(g[x].indR[i] != -1)
                g[x].hR[i] = g[x].hR[i-1] + g[g[x].indR[i-1]].hR[i-1];
        }
    }

    /*cout<<"vh: ";
    for(int x : vh)
        cout<<x<<" ";
    cout<<"\n";

    for(int i = 0; i < n; i++){
        cout<<"pont "<<i<<": "<<g[i].l<<" "<<g[i].r<<" | "<<g[i].lc<<" "<<g[i].rc<<"\n";
        cout<<"inds: ";
        for(int x : g[i].indL)
            cout<<x<<" ";
        cout<<"\n";
        cout<<"h: ";
        for(int x : g[i].hL)
            cout<<x<<" ";
        cout<<"\n";
    }*/
	return;
}

bool benne(long long l1, long long r1, long long l2, long long r2){
    return l1 <= l2 && r2 <= r1;
}

int compare_plants(int x, int y) {
    int ret = 1;
    if(vh[x] < vh[y]){
        ret = -1;
        swap(x, y);
    }

    long long d = x-y;
    if(d < 0) d += n;
    int a = x;
    for(int i = logn-1; i >= 0; i--){
        if(d >= g[a].hL[i]){
            d -= g[a].hL[i];
            a = g[a].indL[i];
        }
    }

    if(d < K && vh[a] >= vh[y])
        return ret;

    d = y-x;
    if(d < 0) d += n;
    a = x;
    for(int i = logn-1; i >= 0; i--){
        if(d >= g[a].hR[i]){
            d -= g[a].hR[i];
            a = g[a].indR[i];
        }
    }

    if(d < K && vh[a] >= vh[y])
        return ret;

    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