oj.uz

Submission #1063224

# Submission time Handle Problem Language Result Execution time Memory
1063224 2024-08-17T15:29:25 Z c2zi6 Comparing Plants (IOI20_plants) C++14
25 / 100
 4000 ms 27448 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;

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});
    }

    /*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) {
    while (pr[x] < y) {
        if (x == pr[x]) break;
        x = pr[x];
    }
    return y <= x+k-1 && b[y] > b[x];
}
bool goleft(int x, int y) {
    while (pl[x] > y) {
        if (x == pl[x]) break;
        x = pl[x];
    }
    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 1 ms 348 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 436 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 34 ms 3900 KB Output is correct
7 Correct 123 ms 6172 KB Output is correct
8 Correct 288 ms 22048 KB Output is correct
9 Correct 363 ms 22588 KB Output is correct
10 Correct 849 ms 22588 KB Output is correct
11 Execution timed out 4043 ms 21308 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 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 604 KB Output is correct
7 Correct 59 ms 4964 KB Output is correct
8 Correct 3 ms 344 KB Output is correct
9 Correct 4 ms 604 KB Output is correct
10 Correct 56 ms 5172 KB Output is correct
11 Correct 1026 ms 4880 KB Output is correct
12 Correct 696 ms 5124 KB Output is correct
13 Correct 53 ms 5088 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 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 604 KB Output is correct
7 Correct 59 ms 4964 KB Output is correct
8 Correct 3 ms 344 KB Output is correct
9 Correct 4 ms 604 KB Output is correct
10 Correct 56 ms 5172 KB Output is correct
11 Correct 1026 ms 4880 KB Output is correct
12 Correct 696 ms 5124 KB Output is correct
13 Correct 53 ms 5088 KB Output is correct
14 Correct 117 ms 6608 KB Output is correct
15 Correct 1175 ms 26744 KB Output is correct
16 Correct 121 ms 6604 KB Output is correct
17 Correct 1254 ms 27448 KB Output is correct
18 Execution timed out 4033 ms 25708 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 17.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 Correct 191 ms 4232 KB Output is correct
4 Execution timed out 4075 ms 24244 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.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 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 38 ms 1668 KB Output is correct
8 Correct 34 ms 1624 KB Output is correct
9 Correct 42 ms 1624 KB Output is correct
10 Correct 42 ms 1660 KB Output is correct
11 Correct 39 ms 1624 KB Output is correct
12 Correct 39 ms 1664 KB Output is correct
13 Correct 35 ms 1628 KB Output is correct

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 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 781 ms 21532 KB Output is correct
7 Correct 1020 ms 20792 KB Output is correct
8 Correct 887 ms 22076 KB Output is correct
9 Correct 1154 ms 25552 KB Output is correct
10 Execution timed out 4058 ms 22076 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 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 436 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 34 ms 3900 KB Output is correct
7 Correct 123 ms 6172 KB Output is correct
8 Correct 288 ms 22048 KB Output is correct
9 Correct 363 ms 22588 KB Output is correct
10 Correct 849 ms 22588 KB Output is correct
11 Execution timed out 4043 ms 21308 KB Time limit exceeded
12 Halted 0 ms 0 KB -