oj.uz

Submission #302069

# Submission time Handle Problem Language Result Execution time Memory
302069 2020-09-18T12:16:35 Z VEGAnn Comparing Plants (IOI20_plants) C++14
27 / 100
 904 ms 22952 KB 
#include "plants.h"
#include <bits/stdc++.h>
#define PB push_back
#define sz(x) ((int)x.size())
#define i2 array<int,2>
using namespace std;
const int N = 200100;
const int oo = 2e9;
set<int> locs;
set<int>::iterator iter;
set<i2> mx;
vector<int> vc, glob;
int per[N], psh[4 * N], n;
i2 st[4 * N];

void build(int v, int l, int r){
    if (l == r){
        st[v] = {glob[l], l};
        return;
    }

    int md = (l + r) >> 1;

    build(v + v, l, md);
    build(v + v + 1, md + 1, r);

    st[v] = min(st[v + v], st[v + v + 1]);
}

void push(int v){
    if (psh[v] != 0){
//        cerr << st[v][0] << " " << st[v][1] << '\n';
        st[v][0] += psh[v];

//        cerr << st[v][0] << " " << st[v][1] << '\n';

        if (v + v + 1 < 4 * N){
            psh[v + v] += psh[v];
            psh[1 + v + v] += psh[v];
        }

        psh[v] = 0;
    }
}

void del(int v, int tl, int tr, int l, int r, int vl){
    push(v);

    if (l > r) return;

    if (tl == l && tr == r) {
        psh[v] = vl;
        push(v);
        return;
    }

    int md = (tl + tr) >> 1;

    del(v + v, tl, md, l, min(r, md), vl);
    del(v + v + 1, md + 1, tr, max(md + 1, l), r, vl);

    st[v] = min(st[v + v], st[v + v + 1]);
}

i2 get(int v, int tl, int tr, int l, int r){
    push(v);

    if (l > r) return {oo, 0};

    if (tl == l && tr == r) return st[v];

    int md = (tl + tr) >> 1;

    return min(get(v + v, tl, md, l, min(r, md)),
               get(v + v + 1, md + 1, tr, max(md + 1, l), r));
}

int dist(int fi, int se){
    if (se > fi)
        return se - fi;
    else return se - fi + n;
}

void uhodi(int vl){
    if (sz(locs) <= 2){
        locs.erase(vl);
        mx.clear();
    } else {
        iter = locs.find(vl);

        int PREV, NEXT;

        if (iter == locs.begin())
            PREV = (*(--locs.end()));
        else PREV = (*prev(iter));

        if (next(iter) == locs.end())
            NEXT = (*locs.begin());
        else NEXT = (*next(iter));

        mx.erase({dist(PREV, vl), vl});
        mx.erase({dist(vl, NEXT), NEXT});

        locs.erase(iter);

        mx.insert({dist(PREV, NEXT), NEXT});
    }
}

void prihodi(int vl){
    if (sz(locs) == 0){
        locs.insert(vl);
        return;
    }

    locs.insert(vl);

    iter = locs.find(vl);

    int PREV, NEXT;

    if (iter == locs.begin())
        PREV = (*(--locs.end()));
    else PREV = (*prev(iter));

    if (next(iter) == locs.end())
        NEXT = (*locs.begin());
    else NEXT = (*next(iter));

    mx.erase({dist(PREV, NEXT), NEXT});

    mx.insert({dist(PREV, vl), vl});
    mx.insert({dist(vl, NEXT), NEXT});
}

void init(int k, vector<int> r) {
    n = sz(r);

    assert(2 * k > n);

    glob = r;

    build(1, 0, n - 1);

    vc.clear();

    for (int i = 0; i < n; i++)
        if (r[i] == 0)
            vc.PB(i);

    for (int it = 0; it < sz(vc); it++){
        int cur = vc[it];
        int nxt = vc[(it + 1) % sz(vc)];

        locs.insert(cur);

        del(1, 0, n - 1, cur, cur, oo);

        if (sz(vc) == 1) continue;

        if (cur == vc.back()){
            mx.insert({nxt + n - cur, nxt});
        } else {
            mx.insert({nxt - cur, nxt});
        }
    }

    for (int it = n - 1; it >= 0; it--){
        assert(sz(locs) > 0);

        int cand = -1;

        if (sz(locs) == 1){
            int vl = (*locs.begin());

            cand = vl;

            uhodi(vl);
        } else {
            cand = (*(--mx.end()))[1];

            uhodi(cand);
        }

        // delete with segment tree

//        cerr << st[2][0] << " " << st[2][1] << '\n';

        int rt = cand, lf = cand - k + 1;

        per[cand] = it;

        if (lf < 0){
            lf += n;

            del(1, 0, n - 1, 0, rt, -1);

            i2 cur = get(1, 0, n - 1, 0, rt);

//            cerr << cur[0] << " " <<cur[1] << '\n';

            while (cur[0] == 0){
                prihodi(cur[1]);
                del(1, 0, n - 1, cur[1], cur[1], oo);
                cur = get(1, 0, n - 1, 0, rt);
            }

            del(1, 0, n - 1, lf, n - 1,  -1);

            cur = get(1, 0, n - 1, lf, n - 1);

            while (cur[0] == 0){
                prihodi(cur[1]);
                del(1, 0, n - 1, cur[1], cur[1], oo);
                cur = get(1, 0, n - 1, lf, n - 1);
            }
        } else {
            del(1, 0, n - 1, lf, rt, -1);

            i2 cur = get(1, 0, n - 1, lf, rt);

            while (cur[0] == 0){
                prihodi(cur[1]);
                del(1, 0, n - 1, cur[1], cur[1], oo);
                cur = get(1, 0, n - 1, lf, rt);
            }

//            cerr << cur[0] << " " <<cur[1] << '\n';
        }
    }

    return;
}

int compare_plants(int x, int y) {
    return (per[x] > per[y] ? 1 : -1);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Runtime error 2 ms 512 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 83 ms 3704 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 4 ms 512 KB Output is correct
10 Correct 84 ms 3576 KB Output is correct
11 Correct 81 ms 3708 KB Output is correct
12 Correct 78 ms 3576 KB Output is correct
13 Correct 80 ms 3576 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 83 ms 3704 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 4 ms 512 KB Output is correct
10 Correct 84 ms 3576 KB Output is correct
11 Correct 81 ms 3708 KB Output is correct
12 Correct 78 ms 3576 KB Output is correct
13 Correct 80 ms 3576 KB Output is correct
14 Correct 136 ms 4728 KB Output is correct
15 Correct 842 ms 13048 KB Output is correct
16 Correct 131 ms 4608 KB Output is correct
17 Correct 904 ms 13176 KB Output is correct
18 Correct 801 ms 22952 KB Output is correct
19 Correct 542 ms 13052 KB Output is correct
20 Correct 717 ms 13108 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Runtime error 2 ms 512 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Runtime error 2 ms 512 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Runtime error 2 ms 512 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -