oj.uz

Submission #1062768

# Submission time Handle Problem Language Result Execution time Memory
1062768 2024-08-17T10:34:41 Z ewirlan Comparing Plants (IOI20_plants) C++17
5 / 100
 350 ms 116048 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] += 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] = 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 2 ms 6784 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 46 ms 9452 KB Output is correct
7 Correct 79 ms 19196 KB Output is correct
8 Correct 284 ms 111440 KB Output is correct
9 Correct 295 ms 111180 KB Output is correct
10 Correct 311 ms 111184 KB Output is correct
11 Correct 319 ms 111872 KB Output is correct
12 Correct 325 ms 111700 KB Output is correct
13 Correct 340 ms 116048 KB Output is correct
14 Correct 350 ms 106580 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6744 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 3 ms 6492 KB Output is correct
4 Correct 3 ms 6576 KB Output is correct
5 Correct 3 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 2 ms 6744 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Correct 3 ms 6492 KB Output is correct
4 Correct 3 ms 6576 KB Output is correct
5 Correct 3 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 2 ms 6748 KB Output is correct
2 Correct 2 ms 6748 KB Output is correct
3 Incorrect 59 ms 10272 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 6744 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 2 ms 6848 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6748 KB Output is correct
2 Correct 3 ms 6492 KB Output is correct
3 Correct 3 ms 6492 KB Output is correct
4 Correct 3 ms 6492 KB Output is correct
5 Incorrect 5 ms 6976 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 2 ms 6784 KB Output is correct
5 Correct 2 ms 6748 KB Output is correct
6 Correct 46 ms 9452 KB Output is correct
7 Correct 79 ms 19196 KB Output is correct
8 Correct 284 ms 111440 KB Output is correct
9 Correct 295 ms 111180 KB Output is correct
10 Correct 311 ms 111184 KB Output is correct
11 Correct 319 ms 111872 KB Output is correct
12 Correct 325 ms 111700 KB Output is correct
13 Correct 340 ms 116048 KB Output is correct
14 Correct 350 ms 106580 KB Output is correct
15 Correct 2 ms 6744 KB Output is correct
16 Correct 2 ms 6748 KB Output is correct
17 Correct 3 ms 6492 KB Output is correct
18 Correct 3 ms 6576 KB Output is correct
19 Correct 3 ms 6748 KB Output is correct
20 Incorrect 6 ms 7004 KB Output isn't correct
21 Halted 0 ms 0 KB -