oj.uz

Submission #1062770

# Submission time Handle Problem Language Result Execution time Memory
1062770 2024-08-17T10:36:37 Z ewirlan Comparing Plants (IOI20_plants) C++17
5 / 100
 387 ms 115984 KB 
//
#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] = max(0, tre[2*w]+tre2[w]);
    tre2[2*w] += tre2[w];
    tre[2*w+1] = max(0, 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] = max(0, 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);
}
void init(int k, vector <int> r)
{
    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]);
    set <int> s;
    rep(c, 1, n+1){
        while(tre[1] == 0){
            int f(find());
            add(f, f, 1e9);
            s.insert(f);
        }
        // cerr << "r: " << r << '\n';
        // cerr << "S ";
        // for(auto i: s)cerr << i << ' ';
        // cerr << '\n';
        int a(-1);
        for(auto i: s){
            bool b(1);
            rep(j, 1, k)b &= !!r[(n+i-j)%n];
            if(b){
                s.erase(i);
                a = i;
                break;
            }
        }
        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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 3 ms 6748 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 48 ms 9464 KB Output is correct
7 Correct 81 ms 19188 KB Output is correct
8 Correct 311 ms 111404 KB Output is correct
9 Correct 332 ms 111100 KB Output is correct
10 Correct 331 ms 111188 KB Output is correct
11 Correct 381 ms 111676 KB Output is correct
12 Correct 366 ms 111616 KB Output is correct
13 Correct 387 ms 115984 KB Output is correct
14 Correct 379 ms 106580 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6748 KB Output is correct
2 Correct 4 ms 6748 KB Output is correct
3 Correct 4 ms 6816 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 4 ms 6748 KB Output is correct
6 Incorrect 6 ms 7004 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6748 KB Output is correct
2 Correct 4 ms 6748 KB Output is correct
3 Correct 4 ms 6816 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Correct 4 ms 6748 KB Output is correct
6 Incorrect 6 ms 7004 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 3 ms 6744 KB Output is correct
3 Incorrect 60 ms 10292 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 2 ms 6748 KB Output is correct
5 Incorrect 3 ms 6748 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6744 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 4 ms 6748 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Incorrect 4 ms 6964 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 2 ms 6748 KB Output is correct
4 Correct 3 ms 6748 KB Output is correct
5 Correct 3 ms 6748 KB Output is correct
6 Correct 48 ms 9464 KB Output is correct
7 Correct 81 ms 19188 KB Output is correct
8 Correct 311 ms 111404 KB Output is correct
9 Correct 332 ms 111100 KB Output is correct
10 Correct 331 ms 111188 KB Output is correct
11 Correct 381 ms 111676 KB Output is correct
12 Correct 366 ms 111616 KB Output is correct
13 Correct 387 ms 115984 KB Output is correct
14 Correct 379 ms 106580 KB Output is correct
15 Correct 3 ms 6748 KB Output is correct
16 Correct 4 ms 6748 KB Output is correct
17 Correct 4 ms 6816 KB Output is correct
18 Correct 2 ms 6748 KB Output is correct
19 Correct 4 ms 6748 KB Output is correct
20 Incorrect 6 ms 7004 KB Output isn't correct
21 Halted 0 ms 0 KB -