oj.uz

Submission #1063238

# Submission time Handle Problem Language Result Execution time Memory
1063238 2024-08-17T15:39:03 Z c2zi6 Comparing Plants (IOI20_plants) C++14
27 / 100
 1381 ms 161852 KB 
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define replr(i, a, b) for (int i = int(a); i <= int(b); ++i)
#define reprl(i, a, b) for (int i = int(a); i >= int(b); --i)
#define rep(i, n) for (int i = 0; i < int(n); ++i)
#define mkp(a, b) make_pair(a, b)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VPI;
typedef vector<VI> VVI;
typedef vector<VVI> VVVI;
typedef vector<VPI> VVPI;
typedef pair<ll, ll> PLL;
typedef vector<ll> VL;
typedef vector<PLL> VPL;
typedef vector<VL> VVL;
typedef vector<VVL> VVVL;
typedef vector<VPL> VVPL;
template<class T> T setmax(T& a, T b) {if (a < b) return a = b; return a;}
template<class T> T setmin(T& a, T b) {if (a < b) return a; return a = b;}
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template<class T>
using indset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#include "plants.h"

struct MINARGSEGTREE {
    int n;
    VPI tree;
    VI lazy;
    MINARGSEGTREE(){}
    MINARGSEGTREE(int sz) {
        n = 1;
        while (n < sz) n *= 2;
        tree = VPI(2*n, {+1e9, -1});
        lazy = VI(2*n);
    }
    void push(int N) {
        tree[N].ff += lazy[N];
        if (2*N+2 < 2*n) {
            lazy[2*N+1] += lazy[N];
            lazy[2*N+2] += lazy[N];
        }
        lazy[N] = 0;
    }
    void set(int N, int L, int R, int i, PII s) {
        push(N);
        if (i < L || i > R) return;
        if (L == R) {
            tree[N] = s;
            return;
        }
        int M = (L + R) / 2;
        set(2*N+1, L, M, i, s);
        set(2*N+2, M+1, R, i, s);
        tree[N] = min(tree[2*N+1], tree[2*N+2]);
    }
    void add(int N, int L, int R, int l, int r, int s) {
        push(N);
        if (R < l || L > r) return;
        if (l <= L && R <= r) {
            lazy[N] = s;
            push(N);
            return;
        }
        int M = (L + R) / 2;
        add(2*N+1, L, M, l, r, s);
        add(2*N+2, M+1, R, l, r, s);
        tree[N] = min(tree[2*N+1], tree[2*N+2]);
    }
    PII get(int N, int L, int R, int l, int r) {
        push(N);
        if (l <= L && R <= r) return tree[N];
        if (R < l || L > r) return {+1e9, -1};
        int M = (L + R) / 2;
        return min(get(2*N+1, L, M, l, r), get(2*N+2, M+1, R, l, r));
    }
    void set(int i, int s) {
        set(0, 0, n-1, i, {s, i});
    }
    void add(int l, int r, int s) {
        add(0, 0, n-1, l, r, s);
    }
    PII get(int l, int r) {
        return get(0, 0, n-1, l, r);
    }
};
struct FIRSTZERODS {
    int n;
    MINARGSEGTREE seg;
    FIRSTZERODS(){}
    FIRSTZERODS(VI a) {
        n = a.size();
        seg = MINARGSEGTREE(n);
        rep(i, n) seg.set(i, a[i]);
    }
    void remove(int i) {
        seg.set(i, +1e9);
    }
    void decrement(int l, int r) {
        l = (l+100*n)%n;
        r = (r+100*n)%n;
        if (l <= r) seg.add(l, r, -1);
        else {
            seg.add(l, n-1, -1);
            seg.add(0, r, -1);
        }
    }
    int get(int l, int r) {
        l = (l+100*n)%n;
        r = (r+100*n)%n;
        PII ret;
        if (l <= r) ret = seg.get(l, r);
        else {
            ret = seg.get(l, n-1);
            if (ret.ff) ret = seg.get(0, r);
        }
        if (ret.ff == 0) return ret.ss;
        return -1;
    }
    void print() {
        rep(i, n) cout << seg.get(i, i).ff << " "; cout << endl;
    }
};

int n, k;
FIRSTZERODS seg;
VI a;
int mx;

VVI gp;

void extract(int i) {
    while (true) {
        int prev = seg.get(i-k+1, i-1);
        if (prev == -1) break;
        extract(prev);
    }
    a[i] = mx--;
    seg.remove(i);
    seg.decrement(i-k+1, i-1);
}

VI b;
VI pr, pl;
VVI parr, parl;

void init(int K_ARG, VI r) {
    k = K_ARG;
    n = r.size();
    seg = FIRSTZERODS(r);
    a = VI(n, -1);
    mx = n-1;
    while (mx >= 0) extract(seg.get(0, n-1));

    if (n <= 300) {
        gp = VVI(n, VI(n));
        rep(i, n) replr(jwm, i+1, i+k-1) {
            int j = jwm%n;
            if (a[j] > a[i]) gp[i][j] = true;
            else gp[j][i] = true;
        }
        rep(m, n) rep(u, n) rep(v, n) {
            gp[u][v] |= gp[u][m] && gp[m][v];
        }
    }
    rep(_, 3) for (int x : a) b.pb(x);
    pr = pl = VI(3*n);
    rep(i, 3*n) pr[i] = pl[i] = i;

    set<PII> st;
    replr(i, 0, k-1) st.insert({b[i], i});
    replr(i, 0, 3*n-1) {
        auto it = st.upper_bound({b[i], +2e9});
        if (it != st.end()) pr[i] = it->ss;
        st.erase({b[i], i});
        if (i+k < 3*n) st.insert({b[i+k], i+k});
    }
    st = set<PII>();
    reprl(i, 3*n-1, 3*n-k) st.insert({b[i], i});
    reprl(i, 3*n-1, 0) {
        auto it = st.upper_bound({b[i], +2e9});
        if (it != st.end()) pl[i] = it->ss;
        st.erase({b[i], i});
        if (i-k >= 0) st.insert({b[i-k], i-k});
    }

    parr = parl = VVI(3*n, VI(21));
    rep(i, n) {
        parr[i][0] = pr[i];
        parl[i][0] = pl[i];
    }
    replr(k, 1, 20) {
        rep(i, 3*n) {
            parl[i][k] = parl[parl[i][k-1]][k-1];
            parr[i][k] = parr[parr[i][k-1]][k-1];
        }
    }
    /*rep(i, 3*n) cout << i << "\t"; cout << endl;*/
    /*for (int x : b) cout << x <<  " "; cout << endl;*/
    /*for (int x : pr) cout << x << " "; cout << endl;*/
    /*for (int x : pl) cout << x << " "; cout << endl;*/
}

bool goright(int x, int y) {
    replr(k, 20, 0) if (parr[x][k] < y) x = parr[x][k];
    return y <= x+k-1 && b[y] > b[x];
}
bool goleft(int x, int y) {
    replr(k, 20, 0) if (parl[x][k] > y) x = parl[x][k];
    return x <= y+k-1 && b[y] > b[x];
}
bool issmaller(int x, int y) {
    if (y > x) return goright(x, y) || goleft(x, y-n);
    return goright(x, y+n) || goleft(x, y);
}

int cp1(int x, int y) {
    x += n;
    y += n;
    if (issmaller(x, y)) return -1;
    if (issmaller(y, x)) return +1;
    return 0;
}

int cp2(int x, int y) {
    if (gp[y][x]) return +1;
    if (gp[x][y]) return -1;
    return 0;
}

int compare_plants(int x, int y) {
    return cp1(x, y);
    /*cout << cp1(x, y) << " " << cp2(x, y) << endl;*/
    /*return -314;*/
    if (cp1(x, y) != cp2(x, y)) {
        rep(i, 200) cout << "VAX QU ";
        cout << endl;

        cout << x << " " << y << endl;
        abort();
    } else return cp2(x, y);

    if (n <= 300) {
    }
    if (a[x] > a[y]) return +1;
    if (a[x] < a[y]) return -1;
	return 0;
}

Compilation message

plants.cpp: In member function 'void FIRSTZERODS::print()':
plants.cpp:9:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    9 | #define rep(i, n) for (int i = 0; i < int(n); ++i)
      |                   ^~~
plants.cpp:129:9: note: in expansion of macro 'rep'
  129 |         rep(i, n) cout << seg.get(i, i).ff << " "; cout << endl;
      |         ^~~
plants.cpp:129:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  129 |         rep(i, n) cout << seg.get(i, i).ff << " "; cout << endl;
      |                                                    ^~~~

Subtask #1
0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 4 ms 1260 KB Output is correct
7 Correct 66 ms 6992 KB Output is correct
8 Correct 2 ms 600 KB Output is correct
9 Correct 5 ms 1116 KB Output is correct
10 Correct 51 ms 7136 KB Output is correct
11 Correct 50 ms 7004 KB Output is correct
12 Correct 46 ms 7164 KB Output is correct
13 Correct 58 ms 7024 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 2 ms 348 KB Output is correct
6 Correct 4 ms 1260 KB Output is correct
7 Correct 66 ms 6992 KB Output is correct
8 Correct 2 ms 600 KB Output is correct
9 Correct 5 ms 1116 KB Output is correct
10 Correct 51 ms 7136 KB Output is correct
11 Correct 50 ms 7004 KB Output is correct
12 Correct 46 ms 7164 KB Output is correct
13 Correct 58 ms 7024 KB Output is correct
14 Correct 126 ms 18896 KB Output is correct
15 Correct 1378 ms 159196 KB Output is correct
16 Correct 124 ms 18896 KB Output is correct
17 Correct 1381 ms 160460 KB Output is correct
18 Correct 735 ms 159236 KB Output is correct
19 Correct 715 ms 161292 KB Output is correct
20 Correct 1332 ms 161852 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 43 ms 4580 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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