Submission #1062833

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062833		ewirlan	Comparing Plants (IOI20_plants)	C++17	100 / 100	645 ms	119124 KiB

plants

//
#ifndef __SIZEOF_INT128__
    #define __SIZEOF_INT128__
#endif
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
template <typename T> using oset =  tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define rep(i, p, k) for(int i(p); i < (k); ++i)
#define per(i, p, k) for(int i(p); i > (k); --i)
#define sz(x) (int)(x).size()
#define sc static_cast
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef __int128_t lll;
//#define int ll
template <typename T = int> using par = std::pair <T, T>;
#define fi first
#define se second
#define test int _number_of_tests(in()); while(_number_of_tests--)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb emplace_back
struct Timer {
    string name{""};
    time_point<high_resolution_clock> end, start{high_resolution_clock::now()};
    duration<float, std::milli> dur;
    Timer() = default;
    Timer(string nm): name(nm) {}
    ~Timer() {
        end = high_resolution_clock::now(); dur= end - start;
        cout << "@" << name << "> " << dur.count() << " ms" << '\n';
    }
};
template <typename T = int> inline T in()
{
    static T x;
    std::cin >> x;
    return x;
}
std::string yn(bool b)
{
    if(b) return "YES\n";
    else return "NO\n";
}
template <typename F, typename S> std::ostream& operator<<(std::ostream& out, const std::pair <F, S>& par);
template <typename T> std::ostream& operator<< (std::ostream& out, const std::vector <T>& wek)
{
    for(const auto& i : wek)out << i << ' ';
    return out;
}
template <typename F, typename S> std::ostream& operator<<(std::ostream& out, const std::pair <F, S>& par)
{
    out << '{'<<par.first<<", "<<par.second<<"}";
    return out;
}
#define show(x) cerr << #x << " = " << x << '\n';
#include "plants.h"
constexpr int maxn = 2e5 + 3, maxk = 20, pol = 1<<18;
int ls[maxn][maxk], rs[maxn][maxk], ko[maxn];
ll ld[maxn][maxk], rd[maxn][maxk];
int n;
constexpr int tres = pol*2+3;
struct t2t{
    int m, g;
};
t2t operator+(t2t a, t2t b){ return (a.m < b.m) ? b : a; }
t2t t2[tres];
t2t t2s(int a, int b){
    t2t o{-1, n};
    a += pol-1; b += pol+1;
    while(a+1 != b){
        if(a % 2 == 0)o = o + t2[a+1];
        if(b % 2 == 1)o = o + t2[b-1];
        a /= 2; b /= 2;
    }
    return o;
}
int tre[tres], tre2[tres];
void upd(int w){
    tre[2*w] += tre2[w];
    tre2[2*w] += tre2[w];
    tre[2*w+1] += tre2[w];
    tre2[2*w+1] += tre2[w];
    tre2[w] = 0;
}
void add(int a, int b, int c, int p = 0, int k = pol-1, int w = 1){
    if(a > k || p > b)return;
    if(a <= p && k <= b){
        tre[w] += c;
        tre2[w] += c;
        return;
    }
    upd(w);
    add(a, b, c, p, (p+k)/2, w*2);
    add(a, b, c, (p+k)/2+1, k, w*2+1);
    tre[w] = min(tre[2*w], tre[2*w+1]);
}
int find(int p = 0, int k = pol-1, int w = 1){
    if(p == k)return p;
    upd(w);
    if(tre[w*2] == 0)return find(p, (p+k)/2, w*2);
    return find((p+k)/2+1, k, w*2+1);
}
set <int> s, t;
int kk;
void supd(int a)
{
    if(sz(s) == 1){
        t.insert(a);
        return;
    }
    t.erase(a);
    auto p(s.find(a));
    if(p == s.begin())p = s.end();
    --p;
    if((a - *p + n)%n >= kk)t.insert(a);
}
void init(int k, vector <int> r)
{
    kk = k;
    n = sz(r);
    rep(i, 0, tres)t2[i] = {-1, n};
    rep(i, 0, pol)tre[i+pol] = (i < n) ? r[i] : 1e9;
    per(i, pol-1, 0)tre[i] = min(tre[2*i], tre[2*i+1]);
    rep(c, 1, n+1){
        while(tre[1] == 0){
            int f(find());
            add(f, f, 1e9);
            s.insert(f);
            supd(f);
            auto p(next(s.find(f)));
            if(p == s.end())p = s.begin();
            if(*p != f)supd(*p);
        } 
        int a(*t.begin());
        t.erase(a);
        s.erase(a);
        auto p(s.lower_bound(a));
        if(p == s.end())p = s.begin();
        if(p != s.end())supd(*p);
        if(a-k+1 < 0){
            add(n+a-k+1, n-1, -1);
            add(0, a-1, -1);
        }
        else add(a-k+1, a-1, -1);
 
        auto [lm, lg] = (a-k+1 >= 0) ? t2s(a-k+1, a-1) : t2s(n+a-k+1, n-1) + t2s(0, a-1);
        ls[a][0] = lg;
        ld[a][0] = lg == n ? -1 : (n+a-lg)%n;
        auto [rm, rg] = (a+k-1 < n) ? t2s(a+1, a+k-1) : t2s(a, n-1) + t2s(0, a+k-1-n);
        rs[a][0] = rg;
        rd[a][0] = rg == n ? -1 : (n+rg-a)%n;
 
        r[a] = -c;
        ko[a] = c;
        int t2g(a+pol);
        t2[t2g] = {ko[a], a};
        while(t2g > 1){
            t2g /= 2;
            t2[t2g] = t2[t2g*2] + t2[t2g*2+1];
        }
    }
    ko[n] = -1;
    ls[n][0] = rs[n][0] = n;
    rep(k, 1, maxk)rep(i, 0, n+1){
        ls[i][k] = ls[ls[i][k-1]][k-1];
        ld[i][k] = ld[i][k-1] + ld[ls[i][k-1]][k-1];
    }
    rep(k, 1, maxk)rep(i, 0, n+1){
        rs[i][k] = rs[rs[i][k-1]][k-1];
        rd[i][k] = rd[i][k-1] + rd[rs[i][k-1]][k-1];
    }
}
int compare_plants(int x, int y)
{
    int m(1);
    if(ko[x] > ko[y]){
        swap(x, y);
        m = -1;
    }
    int z(y);
    ll d(0);
    per(k, maxk-1, -1){
        while(ko[ls[z][k]] >= ko[x]){
            d += ld[z][k];
            z = ls[z][k];
        }
    }
    if(x < y){
        if(y-d <= x)return m;
    }
    else{
        if(y-d <= x-n)return m;
    }
    z = y;
    d = 0;
    per(k, maxk-1, -1){
        while(ko[rs[z][k]] >= ko[x]){
            d += rd[z][k];
            z = rs[z][k];
        }
    }
    if(x < y){
        if(y+d >= x+n)return m;
    }
    else{
        if(y+d >= x)return m;
    }
    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