oj.uz

Submission #379928

# Submission time Handle Problem Language Result Execution time Memory
379928 2021-03-19T17:45:27 Z rocks03 Comparing Plants (IOI20_plants) C++14
100 / 100
 2578 ms 207060 KB 
//#pragma GCC target("avx2")
//#pragma GCC optimization("O3")
//#pragma GCC optimization("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
#define debug(x) cout << #x << ": " << x << " "
#define nl cout << "\n"
#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

class SegmentTree{
public:
    vector<int> st, lazy;
    void merge(int i){
        int l = 2 * i + 1, r = 2 * i + 2;
        st[i] = min(st[l], st[r]);
    }
    void push(int i){
        if(lazy[i]){
            int l = 2 * i + 1, r = 2 * i + 2;
            st[l] += lazy[i];
            st[r] += lazy[i];
            lazy[l] += lazy[i];
            lazy[r] += lazy[i];
            lazy[i] = 0;
        }
    }
    void init_segtree(int n, vector<int>& a){
        st.resize(4 * n);
        lazy.resize(4 * n);
        build(0, 0, n - 1, a);
    }
    void build(int i, int l, int r, vector<int>& a){
        if(l == r){
            st[i] = a[l];
        } else{
            int m = (l + r) / 2;
            build(2 * i + 1, l, m, a);
            build(2 * i + 2, m + 1, r, a);
            merge(i);
        }
    }
    int search(int i, int l, int r, int ql, int qr){
        if(qr < l || ql > r){
            return -1;
        }
        if(l == r){
            return l;
        }
        push(i);
        int m = (l + r) / 2;
        int ans = -1;
        if(st[2 * i + 1] == 0){
            ans = search(2 * i + 1, l, m, ql, qr);
        }
        if(ans == -1 && st[2 * i + 2] == 0){
            ans = search(2 * i + 2, m + 1, r, ql, qr);
        }
        return ans;
    }
    void set(int i, int l, int r, int p, int k){
        if(l == r){
            st[i] = k;
        } else{
            push(i);
            int m = (l + r) / 2;
            if(p <= m)
                set(2 * i + 1, l, m, p, k);
            else
                set(2 * i + 2, m + 1, r, p, k);
            merge(i);
        }
    }
    void add(int i, int l, int r, int ql, int qr, int k){
        if(ql <= l && r <= qr){
            st[i] += k;
            lazy[i] += k;
            return;
        }
        if(qr < l || ql > r){
            return;
        }
        push(i);
        int m = (l + r) / 2;
        add(2 * i + 1, l, m, ql, qr, k);
        add(2 * i + 2, m + 1, r, ql, qr, k);
        merge(i);
    }
};

SegmentTree st;
int N, K;
vector<int> P;

int getpos(int l, int r){
    if(0 <= l && r <= N - 1){
        return st.search(0, 0, N - 1, l, r);
    } else if(l < 0 && r < 0){
        l += N, r += N;
        return getpos(l, r);
    } else{
        return max(getpos(0, r), getpos(l + N, N - 1));
    }
}
void decr(int l, int r){
    if(0 <= l && r <= N - 1){
        st.add(0, 0, N - 1, l, r, -1);
    } else if(l < 0 && r < 0){
        l += N, r += N;
        decr(l, r);
    } else{
        decr(0, r);
        decr(l + N, N - 1);
    }
}

void ass(int i, int& n){
    int l = i - K + 1, j = -1;
    do{
        j = getpos(l, i - 1);
        if(j != -1)
            ass(j, n);
    } while(j != -1);
    P[i] = n--;
    st.set(0, 0, N - 1, i, INT_MAX);
    decr(l, i - 1);
}

void build_P(){
    P = vector<int>(N);
    int n = N;
    while(n){
        int p = getpos(0, N - 1);
        ass(p, n);
    }
    rep(i, 0, N) P.pb(P[i]);
    N = SZ(P);
}

class MergeSortTree{
public:
    vector<vector<pii>> st;
    void init_merge_sort_tree(int n, vector<int>& a){
        st.resize(4 * n);
        build(0, 0, n - 1, a);
    }
    void build(int i, int l, int r, vector<int>& a){
        if(l == r){
            st[i].pb({a[l], l});
        } else{
            int m = (l + r) / 2;
            build(2 * i + 1, l, m, a);
            build(2 * i + 2, m + 1, r, a);
            for(auto [x, pos] : st[2 * i + 1])
                st[i].pb({x, pos});
            for(auto [x, pos] : st[2 * i + 2])
                st[i].pb({x, pos});
            sort(all(st[i]));
        }
    }
    pii search(int i, int l, int r, int ql, int qr, int x){
        if(ql <= l && r <= qr){
            int p = upper_bound(all(st[i]), make_pair(x, -1)) - st[i].begin() - 1;
            if(p < 0){
                return {-1, -1};
            }
            return st[i][p];
        }
        if(qr < l || ql > r){
            return {-1, -1};
        }
        int m = (l + r) / 2;
        pii p1 = search(2 * i + 1, l, m, ql, qr, x);
        pii p2 = search(2 * i + 2, m + 1, r, ql, qr, x);
        if(p1.ff > p2.ff){
            return p1;
        } else{
            return p2;
        }
    }
};

MergeSortTree mst;

pii gethigher(int l, int r, int x){
    if(0 <= l && r <= N - 1){
        return mst.search(0, 0, N - 1, l, r, x);
    } else if(l < 0 && r < 0){
        l += N, r += N;
        return gethigher(l, r, x);
    } else if(l >= N && r >= N){
        l -= N, r -= N;
        return gethigher(l, r, x);
    } else if(l < 0){
        pii p1 = gethigher(0, r, x);
        pii p2 = gethigher(l + N, N - 1, x);
        if(p1.ff > p2.ff)
            return p1;
        return p2;
    } else if(r >= N){
        pii p1 = gethigher(l, N - 1, x);
        pii p2 = gethigher(0, r - N, x);
        if(p1.ff > p2.ff)
            return p1;
        return p2;
    }
}

const int MAXK = 20;
vector<vector<int>> lt, rt;
void build_G(){
    lt = rt = vector<vector<int>>(MAXK, vector<int>(N));
    rep(i, 0, N){
        rt[0][i] = mst.search(0, 0, N - 1, min(N - 1, i + 1), min(N - 1, i + K - 1), P[i]).ss; //gethigher(i + 1, i + K - 1, P[i]).ss;
        lt[0][i] = mst.search(0, 0, N - 1, max(0, i - K + 1), max(0, i - 1), P[i]).ss; //gethigher(i - K + 1, i - 1, P[i]).ss;
        if(rt[0][i] < 0) rt[0][i] = i;
        if(lt[0][i] < 0) lt[0][i] = i;
    }
    rep(k, 1, MAXK){
        rep(i, 0, N){
            rt[k][i] = rt[k - 1][rt[k - 1][i]];
            lt[k][i] = lt[k - 1][lt[k - 1][i]];
        }
    }
}

void init(int k, vector<int> r){
    N = SZ(r), K = k;
    st.init_segtree(N, r);
    build_P();
    mst.init_merge_sort_tree(N, P);
    build_G();
}

int compare(int x, int y){
    if(x < y){
        int v = x;
        per(k, MAXK - 1, 0){
            if(rt[k][v] < y){
                v = rt[k][v];
            }
        }
        v = rt[0][v];
        if(v >= y){
            if(P[v] >= P[y]) return 1;
        }
        x += N / 2;
        v = x;
        per(k, MAXK - 1, 0){
            if(y < lt[k][v]){
                v = lt[k][v];
            }
        }
        v = lt[0][v];
        if(v <= y){
            if(P[v] >= P[y]) return 1;
        }
    } else if(y < x){
        int v = x;
        per(k, MAXK - 1, 0){
            if(y < lt[k][v]){
                v = lt[k][v];
            }
        }
        v = lt[0][v];
        if(v <= y){
            if(P[v] >= P[y]) return 1;
        }
        y += N / 2;
        v = x;
        per(k, MAXK - 1, 0){
            if(rt[k][v] < y){
                v = rt[k][v];
            }
        }
        v = rt[0][v];
        if(y <= v){
            if(P[v] >= P[y]) return 1;
        }
    }
    return 0;
}

int compare_plants(int x, int y){
    int ans = compare(x, y);
    if(ans) return ans;
    ans = -compare(y, x);
    return ans;
}

Compilation message

plants.cpp: In member function 'void MergeSortTree::build(int, int, int, std::vector<int>&)':
plants.cpp:163:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  163 |             for(auto [x, pos] : st[2 * i + 1])
      |                      ^
plants.cpp:165:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  165 |             for(auto [x, pos] : st[2 * i + 2])
      |                      ^
plants.cpp: In function 'std::pair<int, int> gethigher(int, int, int)':
plants.cpp:216:1: warning: control reaches end of non-void function [-Wreturn-type]
  216 | }
      | ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 85 ms 4224 KB Output is correct
7 Correct 437 ms 25188 KB Output is correct
8 Correct 1694 ms 205860 KB Output is correct
9 Correct 1651 ms 205880 KB Output is correct
10 Correct 1560 ms 206036 KB Output is correct
11 Correct 1493 ms 205908 KB Output is correct
12 Correct 1487 ms 206060 KB Output is correct
13 Correct 1071 ms 206048 KB Output is correct
14 Correct 1516 ms 205928 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 7 ms 1260 KB Output is correct
7 Correct 130 ms 9964 KB Output is correct
8 Correct 3 ms 492 KB Output is correct
9 Correct 8 ms 1260 KB Output is correct
10 Correct 160 ms 9964 KB Output is correct
11 Correct 110 ms 9836 KB Output is correct
12 Correct 168 ms 9964 KB Output is correct
13 Correct 125 ms 9964 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 7 ms 1260 KB Output is correct
7 Correct 130 ms 9964 KB Output is correct
8 Correct 3 ms 492 KB Output is correct
9 Correct 8 ms 1260 KB Output is correct
10 Correct 160 ms 9964 KB Output is correct
11 Correct 110 ms 9836 KB Output is correct
12 Correct 168 ms 9964 KB Output is correct
13 Correct 125 ms 9964 KB Output is correct
14 Correct 276 ms 25316 KB Output is correct
15 Correct 2578 ms 206692 KB Output is correct
16 Correct 280 ms 25188 KB Output is correct
17 Correct 2496 ms 206804 KB Output is correct
18 Correct 1538 ms 206292 KB Output is correct
19 Correct 1885 ms 206804 KB Output is correct
20 Correct 2452 ms 206952 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 118 ms 6636 KB Output is correct
4 Correct 1565 ms 206944 KB Output is correct
5 Correct 1720 ms 206280 KB Output is correct
6 Correct 1983 ms 206564 KB Output is correct
7 Correct 2301 ms 206476 KB Output is correct
8 Correct 2511 ms 206648 KB Output is correct
9 Correct 1519 ms 206164 KB Output is correct
10 Correct 1602 ms 206036 KB Output is correct
11 Correct 1074 ms 205836 KB Output is correct
12 Correct 1667 ms 206420 KB Output is correct
13 Correct 1567 ms 206364 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 3 ms 492 KB Output is correct
7 Correct 24 ms 1516 KB Output is correct
8 Correct 20 ms 1516 KB Output is correct
9 Correct 23 ms 1516 KB Output is correct
10 Correct 20 ms 1644 KB Output is correct
11 Correct 24 ms 1516 KB Output is correct
12 Correct 30 ms 1516 KB Output is correct
13 Correct 25 ms 1516 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 5 ms 1132 KB Output is correct
6 Correct 1540 ms 205212 KB Output is correct
7 Correct 1750 ms 205604 KB Output is correct
8 Correct 2017 ms 205708 KB Output is correct
9 Correct 2463 ms 205784 KB Output is correct
10 Correct 1543 ms 205268 KB Output is correct
11 Correct 1843 ms 205652 KB Output is correct
12 Correct 1279 ms 206368 KB Output is correct
13 Correct 1537 ms 205548 KB Output is correct
14 Correct 1654 ms 205508 KB Output is correct
15 Correct 2105 ms 205700 KB Output is correct
16 Correct 1277 ms 205140 KB Output is correct
17 Correct 1425 ms 205188 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 85 ms 4224 KB Output is correct
7 Correct 437 ms 25188 KB Output is correct
8 Correct 1694 ms 205860 KB Output is correct
9 Correct 1651 ms 205880 KB Output is correct
10 Correct 1560 ms 206036 KB Output is correct
11 Correct 1493 ms 205908 KB Output is correct
12 Correct 1487 ms 206060 KB Output is correct
13 Correct 1071 ms 206048 KB Output is correct
14 Correct 1516 ms 205928 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 7 ms 1260 KB Output is correct
21 Correct 130 ms 9964 KB Output is correct
22 Correct 3 ms 492 KB Output is correct
23 Correct 8 ms 1260 KB Output is correct
24 Correct 160 ms 9964 KB Output is correct
25 Correct 110 ms 9836 KB Output is correct
26 Correct 168 ms 9964 KB Output is correct
27 Correct 125 ms 9964 KB Output is correct
28 Correct 276 ms 25316 KB Output is correct
29 Correct 2578 ms 206692 KB Output is correct
30 Correct 280 ms 25188 KB Output is correct
31 Correct 2496 ms 206804 KB Output is correct
32 Correct 1538 ms 206292 KB Output is correct
33 Correct 1885 ms 206804 KB Output is correct
34 Correct 2452 ms 206952 KB Output is correct
35 Correct 1 ms 364 KB Output is correct
36 Correct 1 ms 364 KB Output is correct
37 Correct 118 ms 6636 KB Output is correct
38 Correct 1565 ms 206944 KB Output is correct
39 Correct 1720 ms 206280 KB Output is correct
40 Correct 1983 ms 206564 KB Output is correct
41 Correct 2301 ms 206476 KB Output is correct
42 Correct 2511 ms 206648 KB Output is correct
43 Correct 1519 ms 206164 KB Output is correct
44 Correct 1602 ms 206036 KB Output is correct
45 Correct 1074 ms 205836 KB Output is correct
46 Correct 1667 ms 206420 KB Output is correct
47 Correct 1567 ms 206364 KB Output is correct
48 Correct 1 ms 364 KB Output is correct
49 Correct 1 ms 364 KB Output is correct
50 Correct 1 ms 364 KB Output is correct
51 Correct 1 ms 364 KB Output is correct
52 Correct 1 ms 364 KB Output is correct
53 Correct 3 ms 492 KB Output is correct
54 Correct 24 ms 1516 KB Output is correct
55 Correct 20 ms 1516 KB Output is correct
56 Correct 23 ms 1516 KB Output is correct
57 Correct 20 ms 1644 KB Output is correct
58 Correct 24 ms 1516 KB Output is correct
59 Correct 30 ms 1516 KB Output is correct
60 Correct 25 ms 1516 KB Output is correct
61 Correct 170 ms 6716 KB Output is correct
62 Correct 403 ms 25060 KB Output is correct
63 Correct 2229 ms 205940 KB Output is correct
64 Correct 1780 ms 206176 KB Output is correct
65 Correct 2009 ms 206292 KB Output is correct
66 Correct 2292 ms 206580 KB Output is correct
67 Correct 2508 ms 206724 KB Output is correct
68 Correct 1876 ms 206164 KB Output is correct
69 Correct 2076 ms 206740 KB Output is correct
70 Correct 1641 ms 207060 KB Output is correct
71 Correct 2094 ms 206292 KB Output is correct
72 Correct 2037 ms 206496 KB Output is correct
73 Correct 2285 ms 206884 KB Output is correct
74 Correct 2099 ms 206292 KB Output is correct
75 Correct 1639 ms 206112 KB Output is correct