oj.uz

Submission #431878

# Submission time Handle Problem Language Result Execution time Memory
431878 2021-06-17T16:35:38 Z TryMax Comparing Plants (IOI20_plants) C++17
27 / 100
 637 ms 11956 KB 
#include "plants.h"
#include <bits/stdc++.h>
#ifdef LOCAL
    #include "grader.cpp"
#endif // LOCAL

#define f first
#define s second

using namespace std;

const int N = 2e5 + 10, inf = 1e9 + 10;

int was[N], w[4 * N], n1;
pair<int, int> t[4 * N];
vector<int> a, p;

void push(int u){
    t[2 * u + 1].f += w[u];
    t[2 * u + 2].f += w[u];
    w[2 * u + 1] += w[u];
    w[2 * u + 2] += w[u];
    w[u] = 0;
}

pair<int, int> cmp(pair<int, int> a, pair<int, int> b){
    if(a.f > b.f)
        return a;
    else if(a.f < b.f)
        return b;
    else if(a.s < b.s)
        return a;
    else
        return b;
}

void upd(int u, int tl, int tr, int l, int r, int val){
    if(l <= tl && tr <= r){
        t[u].f += val;
        w[u] += val;
        if(tl == tr)
            t[u].s = tl;
        return;
    }
    push(u);
    int tm = (tl + tr) / 2;
    if(l <= tm)
        upd(2 * u + 1, tl, tm, l, r, val);
    if(r >= tm + 1)
        upd(2 * u + 2, tm + 1, tr, l, r, val);
    t[u] = cmp(t[2 * u + 1], t[2 * u + 2]);
}

pair<int, int> get(int u, int tl, int tr, int l, int r){
//    cout << u << " " << tl << " " << tr << " " << endl;
    if(l <= tl && tr <= r)
        return t[u];
    push(u);
    int tm = (tl + tr) / 2;
    pair<int, int> res = {-inf, 0};
    if(l <= tm)
        res = cmp(res, get(2 * u + 1, tl, tm, l, r));
    if(r >= tm + 1)
        res = cmp(res, get(2 * u + 2, tm + 1, tr, l, r));
    return res;
}

pair<int, int> get_lr(int l, int r){
    if(l <= r)
        return get(0, 0, n1 - 1, l, r);
    else
        return cmp(get(0, 0, n1 - 1, 0, r), get(0, 0, n1 - 1, l, n1 - 1));
}

void upd_lr(int l, int r){
    if(l <= r)
        upd(0, 0, n1 - 1, l, r, 1);
    else{
        upd(0, 0, n1 - 1, 0, r, 1);
        upd(0, 0, n1 - 1, l, n1 - 1, 1);
    }
}

void init(int K, vector<int> r) {
    int k;
    k = K;
    a = r;
    n1 = a.size();
    p.resize(n1);
    for(int j = 0; j < n1; ++j){
        a[j] = k - 1 - a[j];
        upd(0, 0, n1 - 1, j, j, a[j]);
    }
    for(int i = n1 - 1; i >= 0; --i){
//        cout << i << endl;
        int pos = get_lr(0, n1 - 1).s;
//        cout << pos << endl;
//        cout << i << endl;
        pair<int, int> nxt = get_lr((pos + k) % n1, (pos - 1 + n1) % n1);
        if(nxt.f == k - 1)
            pos = nxt.s;
        p[pos] = i;
        upd(0, 0, n1 - 1, pos, pos, -inf);
        upd_lr((pos - k + 1 + n1) % n1, pos);
//        for(int i = 0; i < n; ++i)
//            cout << p[i] << " ";
//        cout << endl;
    }
}

int compare_plants(int x, int y) {
    if(p[x] > p[y])
        return 1;
    else
        return -1;
}
/*
4 3 2
0 1 1 2
0 2
1 2

1
-1

5 3 3
2 2 0 0 0
0 2
1 2
2 4
*/

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 1 ms 204 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 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 87 ms 3356 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 4 ms 332 KB Output is correct
10 Correct 70 ms 3308 KB Output is correct
11 Correct 64 ms 3316 KB Output is correct
12 Correct 64 ms 3444 KB Output is correct
13 Correct 68 ms 3316 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 332 KB Output is correct
7 Correct 87 ms 3356 KB Output is correct
8 Correct 2 ms 332 KB Output is correct
9 Correct 4 ms 332 KB Output is correct
10 Correct 70 ms 3308 KB Output is correct
11 Correct 64 ms 3316 KB Output is correct
12 Correct 64 ms 3444 KB Output is correct
13 Correct 68 ms 3316 KB Output is correct
14 Correct 115 ms 4144 KB Output is correct
15 Correct 631 ms 11952 KB Output is correct
16 Correct 105 ms 4200 KB Output is correct
17 Correct 637 ms 11844 KB Output is correct
18 Correct 421 ms 11956 KB Output is correct
19 Correct 427 ms 11948 KB Output is correct
20 Correct 593 ms 11872 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 64 ms 3560 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 0 ms 204 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 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 0 ms 204 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 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Halted 0 ms 0 KB -