제출 #790622

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
790622		resting	식물 비교 (IOI20_plants)	C++17	44 / 100	1157 ms	122408 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

#define time fuck

const int mx = 2e5 + 5;

int n, k;
struct segtree {
    int l, r, lz = 0, mn = 0;
    segtree* lc = 0, * rc = 0;
    segtree* getmem();
    segtree() : segtree(-1, -1) {};
    segtree(int l, int r) : l(l), r(r) {
        if (l == r)return;
        int m = (l + r) / 2;
        lc = getmem(); *lc = segtree(l, m);
        rc = getmem(); *rc = segtree(m + 1, r);
    }
    void apply(int v) {
        mn += v; lz += v;
    }
    void push() {
        if (l == r) return;
        lc->apply(lz);rc->apply(lz);
        lz = 0;
    }
    void pull() {
        if (l == r) return;
        mn = min(lc->mn, rc->mn);
    }
    void upd(int ql, int qr, int qv) {
        if (qr < 0) { ql += n; qr += n; }
        if (ql < 0) {
            upd(0, qr, qv);
            upd((n)+ql, (n - 1), qv);
            return;
        }
        if (ql >= n) { ql -= n; qr -= n; }
        if (qr >= n) {
            upd(ql, (n - 1), qv);
            upd(0, qr - (n), qv);
            return;
        }
        if (l > qr || r < ql) return;
        if (ql <= l && r <= qr) { apply(qv); return; }
        push();
        lc->upd(ql, qr, qv);
        rc->upd(ql, qr, qv);
        pull();
    }
    int extract_min() {
        if (l == r) return l;
        push();
        if (lc->mn == mn) return lc->extract_min();
        return rc->extract_min();
    }
}mem[mx * 8]; int memsz = 0;
segtree* segtree::getmem() { return &mem[memsz++]; }

const int inf = 1e9 + 7;
namespace rmq {
    struct segtree {
        int l, r, lz = 0;
        segtree* lc = 0, * rc = 0;
        pair<int, int> v = { 0, -1 };
        segtree* getmem();
        segtree() : segtree(-1, -1) {};
        segtree(int l, int r) : l(l), r(r) {
            if (l == r)return;
            int m = (l + r) / 2;
            lc = getmem(); *lc = segtree(l, m);
            rc = getmem(); *rc = segtree(m + 1, r);
        }
        void upd(int qi, int qv) {
            if (l == r) { v = { qv, qi };return; }
            if (qi <= lc->r) lc->upd(qi, qv);
            else rc->upd(qi, qv);
            v = min(lc->v, rc->v);
        }
        pair<int, int> q(int ql, int qr) {
            if (qr < 0) { ql += n; qr += n; }
            if (ql < 0) {
                return min(q(0, qr), q((n)+ql, (n - 1)));
            }
            if (ql >= n) { ql -= n; qr -= n; }
            if (qr >= n) {
                return min(q(ql, (n - 1)), q(0, qr - (n)));
            }
            if (l > qr || r < ql)return { 0, -1 };
            if (ql <= l && r <= qr) return v;
            return min(lc->q(ql, qr), rc->q(ql, qr));
        }
    }mem[mx * 4]; int memsz = 0;
    segtree* segtree::getmem() { return &mem[memsz++]; }
}


vector<int> time, rtime;
int parl[mx][20], parr[mx][20];
void init(int kk, std::vector<int> r) {
    n = r.size();k = kk;k--;
    time = rtime = vector<int>(n, 0);
    segtree parta(0, n - 1), partb(0, n - 1); partb.upd(0, n - 1, 1);
    for (int i = 0; i < n; i++) parta.upd(i, i, r[i]);
    for (int i = 0; i < n; i++) {
        while (parta.mn == 0) {
            int t = parta.extract_min();
            parta.upd(t, t, mx);
            partb.upd(t, t, -1);
            partb.upd(t + 1, t + k, 1);
        }
        int t = partb.extract_min();
        time[t] = i;
        rtime[i] = t;
        partb.upd(t, t, mx);
        partb.upd(t + 1, t + k, -1);
        parta.upd(t - k, t, -1);
    }
    rmq::segtree tim(0, n - 1);
    for (int i = 0; i < n; i++) {
        int t = tim.q(rtime[i] - k, rtime[i]).second;
        if (t == -1) parl[rtime[i]][0] = rtime[i];
        else parl[rtime[i]][0] = t;
        t = tim.q(rtime[i], rtime[i] + k).second;
        if (t == -1) parr[rtime[i]][0] = rtime[i];
        else parr[rtime[i]][0] = t;
    }
    for (int i = 1; i < 20; i++) {
        for (int j = 0; j < n; j++) {
            if (parl[j][0] > j) parl[j][i] = parl[j][i - 1];
            else if (parl[parl[j][i - 1]][i - 1] > j) parl[j][i] = parl[j][i - 1];
            else parl[j][i] = parl[parl[j][i - 1]][i - 1];
        }
    }
    for (int i = 1; i < 20; i++) {
        for (int j = 0; j < n; j++) {
            if (parr[j][0] < j) parr[j][i] = parr[j][i - 1];
            else if (parr[parr[j][i - 1]][i - 1] < j) parr[j][i] = parr[j][i - 1];
            else parr[j][i] = parr[parr[j][i - 1]][i - 1];

        }
    }
    return;
}

int compare_plants(int x, int y) {
    //compare zero
    if (x + k >= y || y + k - n >= x) { return time[x] < time[y] ? 1 : -1; }

    //compare one
    int t = x;
    for (int i = 19; i >= 0; i--) {
        if (parr[t][i] + k < y) t = parr[t][i];
    }
    t = parr[t][0];
    if (t + k >= y && time[t] > time[y]) return -1;

    //compare two
    t = parl[x][19];
    if (y + k - n >= t && time[y] < time[t]) return -1;
    t = parl[t][0];
    for (int i = 19; i >= 0; i--) {
        if (y + k < parl[t][i]) t = parl[t][i];
    }
    t = parl[t][0];
    if (y + k >= t && time[y] < time[t])return -1;

    //compare three
    t = y;
    for (int i = 19; i >= 0; i--) {
        if (x + k < parl[t][i]) t = parl[t][i];
    }
    t = parl[t][0];
    if (x + k >= t && time[t] > time[x]) return 1;

    //compare four
    t = parr[y][19];
    if (t + k - n >= x && time[t] > time[x]) return 1;
    t = parr[t][0];
    for (int i = 19; i >= 0; i--) {
        if (parr[t][i] + k < x) t = parr[t][i];
    }
    t = parr[t][0];
    if (t + k >= x && time[t] > time[x]) return 1;
    return 0;
}

// int main() {
//     init(3, { 0, 1, 1, 2 });
//     cout << compare_plants(0, 2) << endl;
//     cout << compare_plants(1, 2) << endl;
// }

• 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