oj.uz

Submission #364001

# Submission time Handle Problem Language Result Execution time Memory
364001 2021-02-07T22:10:40 Z rocks03 Comparing Plants (IOI20_plants) C++14
5 / 100
 1522 ms 105308 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 rep(i, a, b) for(int i = (a); i < (b); i++)
#define Re(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);
    }
}

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] = gethigher(i + 1, i + K - 1, P[i]).ss;
        lt[0][i] = 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 jumpR(int x, int y){
    if(x <= y){
        return (y - x);
    }
    return (N - x + y);
}
int jumpL(int x, int y){
    if(y <= x){
        return (x - y);
    }
    return (x + N - y);
}
int Dist(int x, int y){
    return min(jumpL(x, y), jumpR(x, y));
}

int compare_plants(int x, int y){
    if(x < y){
        int p = x;
        Re(k, MAXK - 1, 0){
            if(jumpR(p, y) > jumpR(rt[k][p], y)){
                p = rt[k][p];
            }
        }
        if(Dist(p, y) < K && P[p] >= P[y]){
            return 1;
        }
        p = x;
        Re(k, MAXK - 1, 0){
            if(jumpL(p, y) > jumpL(lt[k][p], y)){
                p = lt[k][p];
            }
        }
        if(Dist(p, y) < K && P[p] >= P[y]){
            return 1;
        }
        p = y;
        Re(k, MAXK - 1, 0){
            if(jumpL(p, x) > jumpL(lt[k][p], x)){
                p = lt[k][p];
            }
        }
        if(Dist(p, x) < K && P[p] >= P[x]){
            return -1;
        }
        p = y;
        Re(k, MAXK - 1, 0){
            if(jumpR(p, x) > jumpR(rt[k][p], x)){
                p = rt[k][p];
            }
        }
        if(Dist(p, x) < K && P[p] >= P[x]){
            return -1;
        }
    } else{
        swap(x, y);
        int p = x;
        Re(k, MAXK - 1, 0){
            if(jumpR(p, y) > jumpR(rt[k][p], y)){
                p = rt[k][p];
            }
        }
        if(Dist(p, y) < K && P[p] >= P[y]){
            return -1;
        }
        p = x;
        Re(k, MAXK - 1, 0){
            if(jumpL(p, y) > jumpL(lt[k][p], y)){
                p = lt[k][p];
            }
        }
        if(Dist(p, y) < K && P[p] >= P[y]){
            return -1;
        }
        p = y;
        Re(k, MAXK - 1, 0){
            if(jumpL(p, x) > jumpL(lt[k][p], x)){
                p = lt[k][p];
            }
        }
        if(Dist(p, x) < K && P[p] >= P[x]){
            return 1;
        }
        p = y;
        Re(k, MAXK - 1, 0){
            if(jumpR(p, x) > jumpR(rt[k][p], x)){
                p = rt[k][p];
            }
        }
        if(Dist(p, x) < K && P[p] >= P[x]){
            return 1;
        }
    }
    return 0;
}

Compilation message

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

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 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 125 ms 3180 KB Output is correct
7 Correct 341 ms 13304 KB Output is correct
8 Correct 1430 ms 105308 KB Output is correct
9 Correct 1522 ms 105256 KB Output is correct
10 Correct 1458 ms 105180 KB Output is correct
11 Correct 1336 ms 105180 KB Output is correct
12 Correct 1347 ms 105120 KB Output is correct
13 Correct 872 ms 105180 KB Output is correct
14 Correct 1428 ms 105180 KB Output is correct

Subtask #2
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 0 ms 364 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
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 0 ms 364 KB Output is correct
4 Incorrect 1 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 268 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Incorrect 126 ms 3996 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 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 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 4 ms 492 KB Output is correct
7 Correct 42 ms 1444 KB Output is correct
8 Incorrect 35 ms 1408 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
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 Incorrect 4 ms 748 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
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 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 125 ms 3180 KB Output is correct
7 Correct 341 ms 13304 KB Output is correct
8 Correct 1430 ms 105308 KB Output is correct
9 Correct 1522 ms 105256 KB Output is correct
10 Correct 1458 ms 105180 KB Output is correct
11 Correct 1336 ms 105180 KB Output is correct
12 Correct 1347 ms 105120 KB Output is correct
13 Correct 872 ms 105180 KB Output is correct
14 Correct 1428 ms 105180 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 0 ms 364 KB Output is correct
18 Incorrect 1 ms 364 KB Output isn't correct
19 Halted 0 ms 0 KB -