Submission #1066181

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066181		jerzyk	Comparing Plants (IOI20_plants)	C++17	100 / 100	709 ms	84560 KiB

plants

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

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 1<<18;
int n, k;
int drz[2 * N], laz[2 * N];
int tab[N];
ll jp[N][20];
ll jp2[N][20];
vector<int> cur;

inline void Push(int v)
{
    drz[v * 2] += laz[v]; laz[v * 2] += laz[v];
    drz[v * 2 + 1] += laz[v]; laz[v * 2 + 1] += laz[v];
    laz[v] = 0;
}

int Find(int v, int a, int b, int pz, int kz)
{
    if(b < pz || a > kz || drz[v] > 0) return -1;
    if(v > N)
    {
        drz[v] = II;
        return v - N;
    }
    Push(v);
    int ans = Find(v * 2 + 1, (a + b) / 2 + 1, b, pz, kz);
    drz[v] = min(drz[v * 2], drz[v * 2 + 1]);
    if(ans != -1) return ans;
    ans = Find(v * 2, a, (a + b) / 2, pz, kz);
    drz[v] = min(drz[v * 2], drz[v * 2 + 1]);
    return ans;
}

void Add(int v, int a, int b, int pz, int kz)
{
    if(b < pz || a > kz) return;
    if(a >= pz && b <= kz)
    {
        --drz[v]; --laz[v];
        return;
    }
    Add(v * 2, a, (a + b) / 2, pz, kz);
    Add(v * 2 + 1, (a + b) / 2 + 1, b, pz, kz);
    drz[v] = min(drz[v * 2], drz[v * 2 + 1]) + laz[v];
}

int F(int i)
{
    int a = -1;
    if(i > 1)
        a = Find(1, 0, N - 1, max(i - k, 1), i - 1);
    if(a != -1) return a;
    if(i <= k)
        a = Find(1, 0, N - 1, n - (k - i), n);
    return a;
}

void D(int i)
{
    if(i > 1)
        Add(1, 0, N - 1, max(i - k, 1), i - 1);
    if(i <= k)
        Add(1, 0, N - 1, n - (k - i), n);
}

inline int Dis(int i, int j)
{
    if(i < j)
        return j - i;
    return n - (i - j);
}

inline int J(int i, ll d)
{
    i += d % (ll)n;
    if(i > n) i -= n;
    if(i < 1) i += n;
    return i;
}

void DoJP1()
{
    //cerr << n << " " << k << "\n";
    set<pair<int, int>> zbi;
    set<pair<int, int>>::iterator it;
    for(int i = 2; i <= k + 1; ++i)
        zbi.insert(make_pair(tab[i], i));
    for(int i = 1; i <= n; ++i)
    {
        it = zbi.lower_bound(make_pair(tab[i], 0));
        //cerr << "jp1 " << (*it).nd << "\n";
        if(it == zbi.end())
            jp[i][0] = 0;
        else
            jp[i][0] = Dis(i, (*it).nd);
        if(i < n)
            zbi.erase(make_pair(tab[i + 1], i + 1));
        int nxt = J(i, k + 1);
        zbi.insert(make_pair(tab[nxt], nxt));
    }

    for(int j = 1; j <= 19; ++j)
        for(int i = 1; i <= n; ++i)
            jp[i][j] = jp[i][j - 1] + jp[J(i, jp[i][j - 1])][j - 1];
    /*for(int i = 1; i <= n; ++i)
        cerr << jp[i][0] << " ";
    cerr << "\n";*/
}

void DoJP2()
{
    set<pair<int, int>> zbi;
    set<pair<int, int>>::iterator it;
    for(int i = n; i > n - k; --i)
        zbi.insert(make_pair(tab[i], i));
    for(int i = 1; i <= n; ++i)
    {
        it = zbi.lower_bound(make_pair(tab[i], 0));
        //cerr << "jp2: " << (*it).nd << "\n";
        if(it == zbi.end())
            jp2[i][0] = 0;
        else
            jp2[i][0] = -Dis((*it).nd, i);
        int pr = J(i, -k);
        zbi.erase(make_pair(tab[pr], pr));
        
        zbi.insert(make_pair(tab[i], i));
    }

    for(int j = 1; j <= 19; ++j)
        for(int i = 1; i <= n; ++i)
            jp2[i][j] = jp2[i][j - 1] + jp2[J(i, jp2[i][j - 1])][j - 1];
    //for(int i = 1; i <= n; ++i)
        //cerr << jp2[i][0] << " ";
    //cerr << "\n";
}

void init(int KK, vector<int> r) 
{
    n = r.size(); 
    k = KK - 1;
    /*cerr << "init: \n";
    for(int i = 0; i < n; ++i)
        cerr << r[i] << " ";
    cerr << "\n";*/
    for(int i = 0; i < n; ++i)
        drz[i + N + 1] = r[i];
    drz[N] = II;
    for(int i = n + 1; i < N; ++i)
        drz[i + N] = II;
    for(int i = N - 1; i >= 1; --i)
        drz[i] = min(drz[i * 2], drz[i * 2 + 1]);
    for(int i = n; i >= 1; --i)
    {
        vector<int> cur;
        cur.pb(Find(1, 0, N - 1, 1, n));
        //cerr << "cur: " << i << "\n";
        while(cur.size() > 0)
        {
            //cout << "beg: " << cur.back() << "\n";
            int x = F(cur.back());
            while(x != -1)
            {
                cur.pb(x);
                x = F(x);
            }
            int v = cur.back();
            //cerr << i << " " << v << "\n";
            tab[v] = i; --i;
            D(v);
            cur.pop_back();
        }
        //cerr << "\n";
        ++i;
    }
    /*for(int i = 1; i <= n; ++i)
        cerr << tab[i] << " ";
    cerr << "\n";*/
    //cerr << "xd\n";
    //cerr << k << "\n";
    DoJP1();
    DoJP2();
}

int Jump(int a, int d)
{
    for(int i = 19; i >= 0; --i)
        if(jp[a][i] <= (ll)d)
        {
            d -= jp[a][i];
            a = J(a, jp[a][i]);
        }
    return a;
}

int Jump2(int a, int d)
{
    for(int i = 19; i >= 0; --i)
        if(-jp2[a][i] <= (ll)d)
        {
            d += jp2[a][i];
            a = J(a, jp2[a][i]);
        }
    return a;
}

bool Cp(int x, int y)
{
    int a = Jump(x, Dis(x, y));
    int b = Jump2(x, -Dis(x, y) + n);
    //cerr << -Dis(x, y) + n << "\n";
    if(a == y || b == y) return true;
    if(Dis(a, y) <= k && tab[a] < tab[y]) return true;
    if(Dis(y, b) <= k && tab[b] < tab[y]) return true;
    return false;
}

int compare_plants(int x, int y) 
{
    ++x; ++y;
    int answer = 0;
    if(tab[x] < tab[y] && Cp(x, y))
        answer = -1;
    if(tab[x] > tab[y] && Cp(y, x))
        answer = 1;
    //cerr << "que: " << x << " " << y << " tab: " << tab[x] << " " << tab[y] << " ans: " << answer << "\n";
    return answer;
}

• 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