Submission #1062848

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062848		vjudge1	Comparing Plants (IOI20_plants)	C++17	100 / 100	922 ms	98016 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]; }

    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 (stderr)

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