oj.uz

Submission #1062848

# Submission time Handle Problem Language Result Execution time Memory
1062848 2024-08-17T11:14:53 Z vjudge1 Comparing Plants (IOI20_plants) C++17
100 / 100
 922 ms 98016 KB 
#include "plants.h"

#include <bits/stdc++.h>

using namespace std;

using ii = pair<int, int>;
using vi = vector<int>;
struct AINT {
    int n;
    vector<ii> V;
    vi Lz;
    AINT() {}
    AINT(int N) : n(N), V(4 * N, ii{0, 0}), Lz(4 * N, 0) {}

    void prop(int u, int s, int d) {
        if(!Lz[u]) return;
        V[u].first += Lz[u];
        if(s != d) {
            Lz[u << 1] += Lz[u];
            Lz[u << 1 | 1] += Lz[u];
        }
        Lz[u] = 0;
    }

    void update(int p, ii v, int u, int s, int d) {
        if(d < p || p < s) return;
        if(s == d) {
            V[u] = v;
            return;
        }
        update(p, v, u << 1, s, (s + d) >> 1);
        update(p, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
        V[u] = min(V[u << 1], V[u << 1 | 1]);
    }

    void update(int l, int r, int v, int u, int s, int d) {
        prop(u, s, d);
        if(d < l || r < s) return;
        if(l <= s && d <= r) {
            Lz[u] += v;
            prop(u, s, d);
            return;
        }
        update(l, r, v, u << 1, s, (s + d) >> 1);
        update(l, r, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
        V[u] = min(V[u << 1], V[u << 1 | 1]);
    }

    void update(int p, ii v) { update(p, v, 1, 0, n - 1); }
    void update(int l, int r, int v) { 
        if(l >= 0 && r < n) {
            update(l, r, v, 1, 0, n - 1);
            return;
        }
        if(l < 0 && r >= n) {
            update(0, n - 1, v, 1, 0, n - 1);
            return;
        }
        if(l < 0) {
            update(0, r, v, 1, 0, n - 1);
            update(n + l, n - 1, v, 1, 0, n - 1);
        }
        else if(r >= n) {
            update(l, n - 1, v, 1, 0, n - 1);
            update(0, r - n, v, 1, 0, n - 1);
        }
    }

    ii query() { return V[1]; }

    ii query(int l, int r, int u, int s, int d) {
        int mij = (s + d) >> 1;
        if(l <= s && d <= r) return V[u];
        if(r <= mij) return query(l, r, u << 1, s, mij);
        if(l > mij) return query(l, r, u << 1 | 1, mij + 1, d);
        return min(query(l, r, u << 1, s, mij), query(l, r, u << 1 | 1, mij + 1, d));
    }

    ii query(int l, int r) {
        if(l < 0 && r < 0) {
            l += n; r += n;
        }
        if(l >= n && r >= n) {
            l -= n; r -= n;
        }
        if(l < 0 && r >= n) return query(0, n - 1, 1, 0, n - 1);
        if(l >= 0 && r < n) return query(l, r, 1, 0, n - 1);
        if(l < 0) return min(query(0, r, 1, 0, n - 1), query(l + n, n - 1, 1, 0, n - 1));
        if(r >= n) return min(query(l, n - 1, 1, 0, n - 1), query(0, r - n, 1, 0, n - 1));
    }

    void afis(int u, int s, int d) {
        prop(u, s, d);
        if(s == d) {
            printf("(%d %d) ", V[u].first, V[u].second);
            return;
        }
        afis(u << 1, s, (s + d) >> 1);
        afis(u << 1 | 1, ((s + d) >> 1) + 1, d);
    }
    void afis(string s = "") {
        cout << s;
        afis(1, 0, n - 1);
        cout << "\n";
    }
};

AINT Val;
AINT Block;

const int INF = 1e9;

vi P0;

vector<vi> ST, DR;
int n;


void init(int k, vi r) {
    n = int(r.size());
    Val = AINT(n); Block = AINT(n);
    for(int i = 0; i < n; ++i) {
        Val.update(i, {r[i], i});
        Block.update(i, {INF, i});
    }
    vi Re(n, -1);
    int cnt = n;
    vi ord;
    for(int nr = 0; nr < n; ++nr) {
        while(Val.query().first == 0) {
            int p = Val.query().second; // pozitia asta a devenit 0
            Val.update(p, p, INF);
            Block.update(p + 1, p + k - 1, 1);
            Block.update(p, p, -INF); // am deblocat un 0 practic
        }
        if(Block.query().first == 0) { /// un 0 care poate fi scos
            int p = Block.query().second;
            Block.update(p, p, INF); /// nu voi mai face nimic cu el... ever
            Val.update(p - k + 1, p - 1, - 1);
            int dr = min(p + k - 1, 2 * n - 1);
            Block.update(p + 1, dr, -1);
            Re[p] = --cnt;
            ord.push_back(p);
        }
    }
    P0 = Re;

    ST.emplace_back();
    DR.emplace_back();
    ST[0].resize(2 * n, -1);
    DR[0].resize(2 * n, -1);

    AINT A2(n);
    for(int i = 0; i < n; ++i)
        A2.update(i, {-Re[i], i});
    for(auto it : ord) {
        A2.update(it, it, INF);
        auto [v1, p1] = A2.query(it - k + 1, it - 1);
        if(v1 <= 0) {
            if(p1 > it) p1 -= n;
            ST[0][it] = p1;
            ST[0][it + n] = p1 + n;
        }
        auto [v2, p2] = A2.query(it + 1, it + k - 1);
        if(v2 <= 0) {
            if(p2 < it)
                p2 += n;
            DR[0][it] = p2;
            DR[0][it + n] = p2 + n;
        }
    }
    for(int k = 1; (1 << k) <= 2 * n; ++k) {
        ST.push_back(ST.back());
        DR.push_back(DR.back());
        for(int i = 0; i < 2 * n; ++i) {
            ST[k][i] = (ST[k - 1][i] < 0 || ST[k - 1][i] >= 2 * n) ? ST[k - 1][i] : ST[k - 1][ST[k - 1][i]];
            DR[k][i] = (DR[k - 1][i] < 0 || DR[k - 1][i] >= 2 * n) ? DR[k - 1][i] : DR[k - 1][DR[k - 1][i]];
        }
    }
}

bool ok_st(int x, int y) {
    if(P0[x] < P0[y])
        swap(x, y);
    if(x < y) x += n;
    else {
        x += n;
        y += n;
    }
    while(x > y) {
        if(ST[0][x] < 0) return false;
        for(int k = int(ST.size()) - 1; k >= 0; --k) {
            if(ST[k][x] >= 0 && ST[k][x] > y) {
                x = ST[k][x];
                if(P0[x % n] < P0[y % n]) return false;
            }
        }
        if(ST[0][x] < 0) return false;
        if(ST[0][x] > y) {
            x = ST[0][x];
            if(P0[x % n] < P0[y % n]) return false;
            continue;
        }
        else return true;
    }
    return true;
}

bool ok_dr(int x, int y) {
    if(P0[x] < P0[y]) {
        swap(x, y);
    }
    if(y < x) y += n;
    while(x < y) {
        if(DR[0][x] < 0) return false;
        for(int k = int(DR.size()) - 1; k >= 0; --k) {
            if(DR[k][x] < 2 * n && DR[k][x] >= 0 && DR[k][x] < y) {
                x = DR[k][x];
                if(P0[x % n] < P0[y % n]) return false;
            }
        }
        if(DR[0][x] < 0) return false;
        if(DR[0][x] < y) {
            x = DR[0][x];
            if(P0[x % n] < P0[y % n]) return false;
        } else return true;
    }
    return true;
}

bool ok(int x, int y) {
    return ok_st(x, y) || ok_dr(x, y);
}

int compare_plants(int x, int y) {
    if(!ok(x, y)) return 0;
    if(P0[x] < P0[y]) return -1;
	return 1;
}

Compilation message

plants.cpp: In member function 'ii AINT::query(int, int)':
plants.cpp:91:5: warning: control reaches end of non-void function [-Wreturn-type]
   91 |     }
      |     ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 428 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 34 ms 4176 KB Output is correct
7 Correct 90 ms 13140 KB Output is correct
8 Correct 513 ms 97372 KB Output is correct
9 Correct 440 ms 97480 KB Output is correct
10 Correct 470 ms 97480 KB Output is correct
11 Correct 473 ms 97480 KB Output is correct
12 Correct 449 ms 97248 KB Output is correct
13 Correct 462 ms 97476 KB Output is correct
14 Correct 466 ms 97480 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 4 ms 856 KB Output is correct
7 Correct 52 ms 6276 KB Output is correct
8 Correct 2 ms 600 KB Output is correct
9 Correct 4 ms 860 KB Output is correct
10 Correct 54 ms 6320 KB Output is correct
11 Correct 63 ms 5980 KB Output is correct
12 Correct 64 ms 6312 KB Output is correct
13 Correct 54 ms 6320 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 4 ms 856 KB Output is correct
7 Correct 52 ms 6276 KB Output is correct
8 Correct 2 ms 600 KB Output is correct
9 Correct 4 ms 860 KB Output is correct
10 Correct 54 ms 6320 KB Output is correct
11 Correct 63 ms 5980 KB Output is correct
12 Correct 64 ms 6312 KB Output is correct
13 Correct 54 ms 6320 KB Output is correct
14 Correct 121 ms 12384 KB Output is correct
15 Correct 922 ms 96708 KB Output is correct
16 Correct 110 ms 12624 KB Output is correct
17 Correct 884 ms 96832 KB Output is correct
18 Correct 595 ms 96452 KB Output is correct
19 Correct 625 ms 96452 KB Output is correct
20 Correct 771 ms 96456 KB Output is correct

Subtask #4
17.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 54 ms 5152 KB Output is correct
4 Correct 613 ms 96196 KB Output is correct
5 Correct 652 ms 96152 KB Output is correct
6 Correct 746 ms 96200 KB Output is correct
7 Correct 847 ms 96472 KB Output is correct
8 Correct 855 ms 96456 KB Output is correct
9 Correct 614 ms 96196 KB Output is correct
10 Correct 597 ms 96196 KB Output is correct
11 Correct 491 ms 96224 KB Output is correct
12 Correct 516 ms 96200 KB Output is correct
13 Correct 596 ms 96200 KB Output is correct

Subtask #5
11.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 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 428 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 11 ms 1480 KB Output is correct
8 Correct 9 ms 1368 KB Output is correct
9 Correct 10 ms 1368 KB Output is correct
10 Correct 10 ms 1288 KB Output is correct
11 Correct 10 ms 1368 KB Output is correct
12 Correct 11 ms 1476 KB Output is correct
13 Correct 9 ms 1372 KB Output is correct

Subtask #6
15.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 604 KB Output is correct
6 Correct 640 ms 95720 KB Output is correct
7 Correct 758 ms 96868 KB Output is correct
8 Correct 806 ms 97208 KB Output is correct
9 Correct 848 ms 97440 KB Output is correct
10 Correct 624 ms 96708 KB Output is correct
11 Correct 651 ms 97224 KB Output is correct
12 Correct 512 ms 96572 KB Output is correct
13 Correct 615 ms 96576 KB Output is correct
14 Correct 705 ms 96824 KB Output is correct
15 Correct 807 ms 96968 KB Output is correct
16 Correct 537 ms 96524 KB Output is correct
17 Correct 625 ms 96708 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 428 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 34 ms 4176 KB Output is correct
7 Correct 90 ms 13140 KB Output is correct
8 Correct 513 ms 97372 KB Output is correct
9 Correct 440 ms 97480 KB Output is correct
10 Correct 470 ms 97480 KB Output is correct
11 Correct 473 ms 97480 KB Output is correct
12 Correct 449 ms 97248 KB Output is correct
13 Correct 462 ms 97476 KB Output is correct
14 Correct 466 ms 97480 KB Output is correct
15 Correct 0 ms 600 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 4 ms 856 KB Output is correct
21 Correct 52 ms 6276 KB Output is correct
22 Correct 2 ms 600 KB Output is correct
23 Correct 4 ms 860 KB Output is correct
24 Correct 54 ms 6320 KB Output is correct
25 Correct 63 ms 5980 KB Output is correct
26 Correct 64 ms 6312 KB Output is correct
27 Correct 54 ms 6320 KB Output is correct
28 Correct 121 ms 12384 KB Output is correct
29 Correct 922 ms 96708 KB Output is correct
30 Correct 110 ms 12624 KB Output is correct
31 Correct 884 ms 96832 KB Output is correct
32 Correct 595 ms 96452 KB Output is correct
33 Correct 625 ms 96452 KB Output is correct
34 Correct 771 ms 96456 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 54 ms 5152 KB Output is correct
38 Correct 613 ms 96196 KB Output is correct
39 Correct 652 ms 96152 KB Output is correct
40 Correct 746 ms 96200 KB Output is correct
41 Correct 847 ms 96472 KB Output is correct
42 Correct 855 ms 96456 KB Output is correct
43 Correct 614 ms 96196 KB Output is correct
44 Correct 597 ms 96196 KB Output is correct
45 Correct 491 ms 96224 KB Output is correct
46 Correct 516 ms 96200 KB Output is correct
47 Correct 596 ms 96200 KB Output is correct
48 Correct 0 ms 344 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 428 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 1 ms 348 KB Output is correct
54 Correct 11 ms 1480 KB Output is correct
55 Correct 9 ms 1368 KB Output is correct
56 Correct 10 ms 1368 KB Output is correct
57 Correct 10 ms 1288 KB Output is correct
58 Correct 10 ms 1368 KB Output is correct
59 Correct 11 ms 1476 KB Output is correct
60 Correct 9 ms 1372 KB Output is correct
61 Correct 49 ms 5460 KB Output is correct
62 Correct 96 ms 13140 KB Output is correct
63 Correct 516 ms 97468 KB Output is correct
64 Correct 631 ms 97572 KB Output is correct
65 Correct 767 ms 97736 KB Output is correct
66 Correct 808 ms 97992 KB Output is correct
67 Correct 863 ms 98016 KB Output is correct
68 Correct 649 ms 97364 KB Output is correct
69 Correct 673 ms 97992 KB Output is correct
70 Correct 571 ms 97424 KB Output is correct
71 Correct 675 ms 97480 KB Output is correct
72 Correct 745 ms 97736 KB Output is correct
73 Correct 847 ms 97976 KB Output is correct
74 Correct 547 ms 97504 KB Output is correct
75 Correct 629 ms 97476 KB Output is correct