oj.uz

Submission #1062522

# Submission time Handle Problem Language Result Execution time Memory
1062522 2024-08-17T08:14:12 Z RaresFelix Comparing Plants (IOI20_plants) C++17
44 / 100
 598 ms 28480 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]; }

    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;

void init(int k, vi r) {
    int 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;
  //  Val.afis("Val = ");
  //  Block.afis("Block = ");
  //  cout << "\n";
    for(int nr = 0; nr < n; ++nr) {
        while(Val.query().first == 0) {
            int p = Val.query().second; // pozitia asta a devenit 0
            //cout << "A aparut 0 pe " << p << "\n";
            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;
            //cout << "Am luat 0-ul de pe " << p << "\n";
            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;
        }
       // Val.afis("Val = ");
       // Block.afis("Block = ");
       // cout << "Re: ";
       // cout << "\n";
       // cout << "\n";
    }
    P0 = Re;
	return;
}

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

Subtask #1
0 / 5.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 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 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 3 ms 460 KB Output is correct
7 Correct 41 ms 3816 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 3 ms 604 KB Output is correct
10 Correct 41 ms 3580 KB Output is correct
11 Correct 37 ms 3664 KB Output is correct
12 Correct 38 ms 5592 KB Output is correct
13 Correct 42 ms 5712 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 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 3 ms 460 KB Output is correct
7 Correct 41 ms 3816 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 3 ms 604 KB Output is correct
10 Correct 41 ms 3580 KB Output is correct
11 Correct 37 ms 3664 KB Output is correct
12 Correct 38 ms 5592 KB Output is correct
13 Correct 42 ms 5712 KB Output is correct
14 Correct 79 ms 7508 KB Output is correct
15 Correct 598 ms 28220 KB Output is correct
16 Correct 78 ms 7512 KB Output is correct
17 Correct 597 ms 28244 KB Output is correct
18 Correct 394 ms 27984 KB Output is correct
19 Correct 386 ms 28480 KB Output is correct
20 Correct 541 ms 28244 KB Output is correct

Subtask #4
17.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 Correct 34 ms 3412 KB Output is correct
4 Correct 337 ms 24568 KB Output is correct
5 Correct 401 ms 27780 KB Output is correct
6 Correct 490 ms 27984 KB Output is correct
7 Correct 571 ms 27988 KB Output is correct
8 Correct 579 ms 28368 KB Output is correct
9 Correct 383 ms 27612 KB Output is correct
10 Correct 362 ms 27708 KB Output is correct
11 Correct 276 ms 27476 KB Output is correct
12 Correct 336 ms 27740 KB Output is correct
13 Correct 402 ms 27732 KB Output is correct

Subtask #5
0 / 11.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 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 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Incorrect 0 ms 348 KB Output isn't correct
5 Halted 0 ms 0 KB -