oj.uz

Submission #1062830

# Submission time Handle Problem Language Result Execution time Memory
1062830 2024-08-17T11:06:26 Z vjudge1 Comparing Plants (IOI20_plants) C++17
44 / 100
 4000 ms 98244 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] > 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] >= 0 && DR[k][x] < y) {
                x = DR[k][x];
                if(P0[x % n] < P0[y % n]) 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
0 / 5.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 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 1 ms 348 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 56 ms 6864 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 4 ms 860 KB Output is correct
10 Correct 60 ms 6808 KB Output is correct
11 Correct 96 ms 6604 KB Output is correct
12 Correct 61 ms 6836 KB Output is correct
13 Correct 62 ms 6844 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 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 1 ms 348 KB Output is correct
6 Correct 4 ms 860 KB Output is correct
7 Correct 56 ms 6864 KB Output is correct
8 Correct 2 ms 348 KB Output is correct
9 Correct 4 ms 860 KB Output is correct
10 Correct 60 ms 6808 KB Output is correct
11 Correct 96 ms 6604 KB Output is correct
12 Correct 61 ms 6836 KB Output is correct
13 Correct 62 ms 6844 KB Output is correct
14 Correct 113 ms 13368 KB Output is correct
15 Correct 893 ms 97976 KB Output is correct
16 Correct 119 ms 13136 KB Output is correct
17 Correct 930 ms 97500 KB Output is correct
18 Correct 595 ms 97220 KB Output is correct
19 Correct 591 ms 98244 KB Output is correct
20 Correct 773 ms 98244 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 1 ms 348 KB Output is correct
3 Correct 54 ms 5272 KB Output is correct
4 Correct 582 ms 97476 KB Output is correct
5 Correct 697 ms 97444 KB Output is correct
6 Correct 728 ms 97708 KB Output is correct
7 Correct 839 ms 97980 KB Output is correct
8 Correct 859 ms 98128 KB Output is correct
9 Correct 632 ms 97468 KB Output is correct
10 Correct 579 ms 97456 KB Output is correct
11 Correct 502 ms 97476 KB Output is correct
12 Correct 566 ms 97480 KB Output is correct
13 Correct 616 ms 97468 KB Output is correct

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 Execution timed out 4093 ms 348 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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