Submission #1062522

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062522		RaresFelix	Comparing Plants (IOI20_plants)	C++17	44 / 100	598 ms	28480 KiB

plants

#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
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25