oj.uz

Submission #357774

# Submission time Handle Problem Language Result Execution time Memory
357774 2021-01-24T16:41:17 Z doowey Comparing Plants (IOI20_plants) C++14
100 / 100
 2787 ms 94136 KB 
#include <bits/stdc++.h>
#include "plants.h"

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

#define fi first
#define se second
#define mp make_pair

const int N = (int)2e5 + 100;
int A[N];
int vl[N];

struct Node{
    pii valid; // = r + vl
    pii zero; // = r
    int rlazy;
    int vllazy;
};

Node T[N * 4 + 512];

void push(int node, int cl, int cr){
    T[node].valid.fi += T[node].rlazy + T[node].vllazy;
    T[node].zero.fi += T[node].rlazy;
    if(cl != cr){
        T[node*2].rlazy += T[node].rlazy;
        T[node*2+1].rlazy += T[node].rlazy;
        T[node*2].vllazy += T[node].vllazy;
        T[node*2+1].vllazy += T[node].vllazy;
    }
    T[node].rlazy = 0;
    T[node].vllazy = 0;
}

void upd(int node, int cl, int cr, int tl, int tr, int typ, int v){
    push(node, cl, cr);
    if(cr < tl || cl > tr)
        return;
    if(cl >= tl && cr <= tr){
        if(typ == 0) T[node].rlazy = v;
        else T[node].vllazy = v;
        push(node, cl, cr);
        return;
    }
    int mid = (cl + cr) / 2;
    upd(node * 2, cl, mid, tl, tr, typ, v);
    upd(node * 2 + 1, mid + 1, cr, tl, tr, typ, v);
    T[node].valid = min(T[node*2].valid, T[node*2+1].valid);
    T[node].zero = min(T[node*2].zero, T[node*2+1].zero);
}

pii get(int node, int cl, int cr, int tl, int tr, int ta){
    push(node, cl, cr);
    if(cr < tl || cl > tr)
        return mp((int)1e9, (int)1e9);
    if(cl >= tl && cr <= tr){
        if(ta == 0)
            return T[node].zero;
        else
            return T[node].valid;
    }
    int mid = (cl + cr) / 2;
    return min(get(node * 2, cl, mid, tl, tr, ta), get(node * 2 + 1, mid + 1, cr, tl, tr, ta));
}

vector<int> r;

void build(int node, int cl, int cr){
    if(cl == cr){
        T[node].valid = mp(r[cl], cl);
        T[node].zero = mp(r[cl], cl);
        return;
    }
    int mid = (cl + cr) / 2;
    build(node * 2, cl, mid);
    build(node * 2 + 1, mid + 1, cr);
    T[node].valid = min(T[node * 2].valid, T[node * 2 + 1].valid);
    T[node].zero = min(T[node * 2].zero, T[node * 2 + 1].zero);
}

int n, k;

void upd_zero(int ii, int sign){
    int nx = (ii + k - 1) % n;
    if(nx > ii){
        upd(1, 0, n - 1, ii + 1, nx, 1, sign);
    }
    else{
        upd(1, 0, n - 1, ii + 1, n - 1, 1, sign);
        upd(1, 0, n - 1, 0, nx, 1, sign);
    }
}

vector<int> getz(int li, int ri){
    vector<int> soln;
    pii cc;
    while(li <= ri){
        cc = get(1, 0, n - 1, li, ri, 0);
        if(cc.fi != 0) return soln;
        soln.push_back(cc.se);
        li = cc.se + 1;
    }
    return soln;
}

const int LOG = 18;
int lef[LOG][N];
int rig[LOG][N];
int cl[LOG][N];
int cr[LOG][N];

void init(int k_, vector<int> r_) {
    r = r_;
    k = k_;
    n = r.size();
    build(1, 0, n - 1);
    for(int i = 0 ; i < n; i ++ ){
        if(r[i] == 0){
            upd_zero(i,+1);
        }
    }

    int st;
    int pv;
    int nx;
    for(int id = n - 1; id >= 0 ; id -- ){
        st = T[1].valid.se;
        A[st] = id;
        pv = (st - (k - 1) + n) % n;
        upd(1, 0, n - 1, st, st, 0, (int)1e9);
        upd_zero(st,-1);
        vector<int> nwz, cc;
        if(pv < st){
            upd(1, 0, n - 1, pv, st - 1, 0, -1);
            cc = getz(pv, st - 1);
            for(auto q : cc) nwz.push_back(q);
        }
        else{
            upd(1, 0, n - 1, 0, st - 1, 0, -1);
            upd(1, 0, n - 1, pv, n - 1, 0, -1);
            cc = getz(0, st - 1);
            for(auto q : cc) nwz.push_back(q);
            cc = getz(pv, n - 1);
            for(auto q : cc) nwz.push_back(q);
        }
        for(auto x : nwz){
            upd_zero(x,+1);
        }
    }
    multiset<pii> alx;
    for(int i = n - 1; i >= n - (k - 1); i -- ){
        alx.insert(mp(A[i], i));
    }
    for(int i = 0 ; i < n; i ++ ){
        auto it = alx.lower_bound(mp(A[i],-1));
        if(it == alx.begin()){
            lef[0][i] = -1;
        }
        else{
            it -- ;
            cl[0][i] = (it->se > i);
            lef[0][i] = it->se;
        }
        pv = (i - (k - 1) + n) % n;
        alx.erase(mp(A[pv], pv));
        alx.insert(mp(A[i],i));
    }
    alx.clear();
    for(int i = 1; i < k ; i ++ ){
        alx.insert(mp(A[i],i));
    }
    for(int i = 0; i < n; i ++ ){
        auto it = alx.lower_bound(mp(A[i],-1));
        if(it == alx.begin()){
            rig[0][i] = -1;
        }
        else{
            it -- ;
            cr[0][i] = (it->se < i);
            rig[0][i] = it->se;
        }
        if(i < n){
            alx.erase(mp(A[i + 1], i + 1));
            alx.insert(mp(A[(i + k) % n], (i + k) % n));
        }
    }
    for(int lg = 1; lg < LOG; lg ++ ){
        for(int i = 0 ; i < n; i ++ ){
            lef[lg][i]=rig[lg][i]=-1;
            if(lef[lg-1][i] != -1){
                lef[lg][i]=lef[lg-1][lef[lg-1][i]];
                cl[lg][i] = (cl[lg-1][i] | cl[lg-1][lef[lg-1][i]]);
            }
            if(rig[lg-1][i] != -1){
                rig[lg][i]=rig[lg-1][rig[lg-1][i]];
                cr[lg][i] = (cr[lg-1][i] | cr[lg-1][rig[lg-1][i]]);
            }
        }
    }
}

int compare_plants(int x, int y) {
    int go = x;
    for(int i = LOG - 1; i >= 0 ; i -- ){
        if(lef[i][go] != -1 && cl[i][go] != 1)
            go = lef[i][go];
    }
    if(lef[0][go] != -1){
        if(lef[0][go] > y){
            go = lef[0][go];
            for(int i = LOG - 1; i >= 0 ; i -- ){
                if(lef[i][go] != -1 && cl[i][go] != 1 && lef[i][go] > y)
                    go = lef[i][go];
            }
            if((go - y + n) % n < k){
                if(A[go] > A[y]) return +1;
            }
        }
        else{
            if(A[go] > A[y]) return +1;
        }
    }
    go = x;
    for(int i = LOG - 1; i >= 0 ; i -- ){
        if(rig[i][go] != -1 && cr[i][go] != 1 && rig[i][go] < y){
            go = rig[i][go];
        }
    }
    if(y - go < k){
        if(A[go] > A[y]) return +1;
    }
    //
    go = y;
    for(int i = LOG - 1; i >= 0 ; i -- ){
        if(lef[i][go] != -1 && cl[i][go] != 1 && lef[i][go] > x){
            go = lef[i][go];
        }
    }
    if(go - x < k){
        if(A[go] > A[x]) return -1;
    }
    //
    go = y;
    for(int i = LOG - 1; i >= 0 ; i -- ){
        if(rig[i][go] != -1 && cr[i][go] != 1)
            go = rig[i][go];
    }
    if(rig[0][go] != -1){
        if(rig[0][go] < x){
            for(int i = LOG - 1; i >= 0 ; i -- ){
                if(rig[i][go] != -1 && cr[i][go] != 1 && cr[i][go] < x){
                    go = rig[i][go];
                }
            }
            if(x - go < k){
                if(A[go] > A[x]) return -1;
            }
        }
        else{
            if(A[go] > A[x]) return -1;
        }
    }
    return 0;
}

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:129:9: warning: unused variable 'nx' [-Wunused-variable]
  129 |     int nx;
      |         ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19308 KB Output is correct
2 Correct 12 ms 19308 KB Output is correct
3 Correct 12 ms 19308 KB Output is correct
4 Correct 12 ms 19308 KB Output is correct
5 Correct 12 ms 19436 KB Output is correct
6 Correct 92 ms 23148 KB Output is correct
7 Correct 214 ms 29164 KB Output is correct
8 Correct 935 ms 66736 KB Output is correct
9 Correct 978 ms 70380 KB Output is correct
10 Correct 1042 ms 70124 KB Output is correct
11 Correct 1065 ms 67632 KB Output is correct
12 Correct 1072 ms 68716 KB Output is correct
13 Correct 1116 ms 69356 KB Output is correct
14 Correct 1175 ms 69356 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19308 KB Output is correct
2 Correct 14 ms 19308 KB Output is correct
3 Correct 12 ms 19436 KB Output is correct
4 Correct 12 ms 19436 KB Output is correct
5 Correct 13 ms 19436 KB Output is correct
6 Correct 19 ms 19820 KB Output is correct
7 Correct 141 ms 24684 KB Output is correct
8 Correct 15 ms 19564 KB Output is correct
9 Correct 19 ms 19820 KB Output is correct
10 Correct 144 ms 24956 KB Output is correct
11 Correct 137 ms 24044 KB Output is correct
12 Correct 164 ms 24516 KB Output is correct
13 Correct 142 ms 24908 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19308 KB Output is correct
2 Correct 14 ms 19308 KB Output is correct
3 Correct 12 ms 19436 KB Output is correct
4 Correct 12 ms 19436 KB Output is correct
5 Correct 13 ms 19436 KB Output is correct
6 Correct 19 ms 19820 KB Output is correct
7 Correct 141 ms 24684 KB Output is correct
8 Correct 15 ms 19564 KB Output is correct
9 Correct 19 ms 19820 KB Output is correct
10 Correct 144 ms 24956 KB Output is correct
11 Correct 137 ms 24044 KB Output is correct
12 Correct 164 ms 24516 KB Output is correct
13 Correct 142 ms 24908 KB Output is correct
14 Correct 291 ms 29140 KB Output is correct
15 Correct 2688 ms 88684 KB Output is correct
16 Correct 355 ms 29548 KB Output is correct
17 Correct 2689 ms 89452 KB Output is correct
18 Correct 1705 ms 75352 KB Output is correct
19 Correct 1912 ms 75692 KB Output is correct
20 Correct 2787 ms 94136 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19308 KB Output is correct
2 Correct 12 ms 19436 KB Output is correct
3 Correct 140 ms 24428 KB Output is correct
4 Correct 1660 ms 79632 KB Output is correct
5 Correct 1936 ms 78664 KB Output is correct
6 Correct 2056 ms 81164 KB Output is correct
7 Correct 2206 ms 83328 KB Output is correct
8 Correct 2519 ms 88924 KB Output is correct
9 Correct 1421 ms 71916 KB Output is correct
10 Correct 1569 ms 78572 KB Output is correct
11 Correct 1101 ms 69356 KB Output is correct
12 Correct 1347 ms 69648 KB Output is correct
13 Correct 1690 ms 73196 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19308 KB Output is correct
2 Correct 12 ms 19308 KB Output is correct
3 Correct 12 ms 19308 KB Output is correct
4 Correct 12 ms 19436 KB Output is correct
5 Correct 12 ms 19436 KB Output is correct
6 Correct 14 ms 19564 KB Output is correct
7 Correct 35 ms 20460 KB Output is correct
8 Correct 34 ms 20460 KB Output is correct
9 Correct 38 ms 20460 KB Output is correct
10 Correct 33 ms 20460 KB Output is correct
11 Correct 35 ms 20460 KB Output is correct
12 Correct 35 ms 20460 KB Output is correct
13 Correct 34 ms 20460 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19328 KB Output is correct
2 Correct 14 ms 19308 KB Output is correct
3 Correct 12 ms 19308 KB Output is correct
4 Correct 12 ms 19436 KB Output is correct
5 Correct 18 ms 19692 KB Output is correct
6 Correct 1429 ms 67564 KB Output is correct
7 Correct 1659 ms 72680 KB Output is correct
8 Correct 1849 ms 79404 KB Output is correct
9 Correct 2405 ms 88044 KB Output is correct
10 Correct 1259 ms 70648 KB Output is correct
11 Correct 1667 ms 80456 KB Output is correct
12 Correct 1270 ms 80212 KB Output is correct
13 Correct 1670 ms 78624 KB Output is correct
14 Correct 1642 ms 80372 KB Output is correct
15 Correct 1986 ms 82608 KB Output is correct
16 Correct 1156 ms 78456 KB Output is correct
17 Correct 1331 ms 73620 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19308 KB Output is correct
2 Correct 12 ms 19308 KB Output is correct
3 Correct 12 ms 19308 KB Output is correct
4 Correct 12 ms 19308 KB Output is correct
5 Correct 12 ms 19436 KB Output is correct
6 Correct 92 ms 23148 KB Output is correct
7 Correct 214 ms 29164 KB Output is correct
8 Correct 935 ms 66736 KB Output is correct
9 Correct 978 ms 70380 KB Output is correct
10 Correct 1042 ms 70124 KB Output is correct
11 Correct 1065 ms 67632 KB Output is correct
12 Correct 1072 ms 68716 KB Output is correct
13 Correct 1116 ms 69356 KB Output is correct
14 Correct 1175 ms 69356 KB Output is correct
15 Correct 12 ms 19308 KB Output is correct
16 Correct 14 ms 19308 KB Output is correct
17 Correct 12 ms 19436 KB Output is correct
18 Correct 12 ms 19436 KB Output is correct
19 Correct 13 ms 19436 KB Output is correct
20 Correct 19 ms 19820 KB Output is correct
21 Correct 141 ms 24684 KB Output is correct
22 Correct 15 ms 19564 KB Output is correct
23 Correct 19 ms 19820 KB Output is correct
24 Correct 144 ms 24956 KB Output is correct
25 Correct 137 ms 24044 KB Output is correct
26 Correct 164 ms 24516 KB Output is correct
27 Correct 142 ms 24908 KB Output is correct
28 Correct 291 ms 29140 KB Output is correct
29 Correct 2688 ms 88684 KB Output is correct
30 Correct 355 ms 29548 KB Output is correct
31 Correct 2689 ms 89452 KB Output is correct
32 Correct 1705 ms 75352 KB Output is correct
33 Correct 1912 ms 75692 KB Output is correct
34 Correct 2787 ms 94136 KB Output is correct
35 Correct 12 ms 19308 KB Output is correct
36 Correct 12 ms 19436 KB Output is correct
37 Correct 140 ms 24428 KB Output is correct
38 Correct 1660 ms 79632 KB Output is correct
39 Correct 1936 ms 78664 KB Output is correct
40 Correct 2056 ms 81164 KB Output is correct
41 Correct 2206 ms 83328 KB Output is correct
42 Correct 2519 ms 88924 KB Output is correct
43 Correct 1421 ms 71916 KB Output is correct
44 Correct 1569 ms 78572 KB Output is correct
45 Correct 1101 ms 69356 KB Output is correct
46 Correct 1347 ms 69648 KB Output is correct
47 Correct 1690 ms 73196 KB Output is correct
48 Correct 12 ms 19308 KB Output is correct
49 Correct 12 ms 19308 KB Output is correct
50 Correct 12 ms 19308 KB Output is correct
51 Correct 12 ms 19436 KB Output is correct
52 Correct 12 ms 19436 KB Output is correct
53 Correct 14 ms 19564 KB Output is correct
54 Correct 35 ms 20460 KB Output is correct
55 Correct 34 ms 20460 KB Output is correct
56 Correct 38 ms 20460 KB Output is correct
57 Correct 33 ms 20460 KB Output is correct
58 Correct 35 ms 20460 KB Output is correct
59 Correct 35 ms 20460 KB Output is correct
60 Correct 34 ms 20460 KB Output is correct
61 Correct 142 ms 24428 KB Output is correct
62 Correct 226 ms 28396 KB Output is correct
63 Correct 1276 ms 64980 KB Output is correct
64 Correct 1623 ms 68716 KB Output is correct
65 Correct 2052 ms 73964 KB Output is correct
66 Correct 2213 ms 80268 KB Output is correct
67 Correct 2535 ms 89024 KB Output is correct
68 Correct 1444 ms 71788 KB Output is correct
69 Correct 1968 ms 81308 KB Output is correct
70 Correct 1390 ms 80884 KB Output is correct
71 Correct 1849 ms 79988 KB Output is correct
72 Correct 2024 ms 81260 KB Output is correct
73 Correct 2211 ms 83436 KB Output is correct
74 Correct 1320 ms 65388 KB Output is correct
75 Correct 1600 ms 75884 KB Output is correct