oj.uz

Submission #363998

# Submission time Handle Problem Language Result Execution time Memory
363998 2021-02-07T21:54:46 Z rocks03 Comparing Plants (IOI20_plants) C++14
5 / 100
 1567 ms 108224 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[2 * i + 1] += lazy[i];
            st[2 * i + 2] += lazy[i];
            lazy[2 * i + 1] += lazy[i];
            lazy[2 * i + 2] += 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;
    int j = getpos(l, i - 1);
    if(j != -1){
        ass(j, n);
    }
    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 SegmentTree::push(int)':
plants.cpp:27:17: warning: unused variable 'l' [-Wunused-variable]
   27 |             int l = 2 * i + 1, r = 2 * i + 2;
      |                 ^
plants.cpp:27:32: warning: unused variable 'r' [-Wunused-variable]
   27 |             int l = 2 * i + 1, r = 2 * i + 2;
      |                                ^
plants.cpp: In member function 'void MergeSortTree::build(int, int, int, std::vector<int>&)':
plants.cpp:158:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  158 |             for(auto [x, pos] : st[2 * i + 1])
      |                      ^
plants.cpp:160:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  160 |             for(auto [x, pos] : st[2 * i + 2])
      |                      ^
plants.cpp: In function 'std::pair<int, int> gethigher(int, int, int)':
plants.cpp:211:1: warning: control reaches end of non-void function [-Wreturn-type]
  211 | }
      | ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 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 125 ms 4124 KB Output is correct
7 Correct 348 ms 15464 KB Output is correct
8 Correct 1444 ms 108124 KB Output is correct
9 Correct 1567 ms 108124 KB Output is correct
10 Correct 1457 ms 108024 KB Output is correct
11 Correct 1383 ms 108224 KB Output is correct
12 Correct 1280 ms 108124 KB Output is correct
13 Correct 841 ms 108124 KB Output is correct
14 Correct 1414 ms 108124 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 1 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 1 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 364 KB Output is correct
2 Correct 1 ms 268 KB Output is correct
3 Runtime error 148 ms 5740 KB Execution killed with signal 6
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 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Runtime error 5 ms 748 KB Execution killed with signal 6
7 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 Runtime error 4 ms 1216 KB Execution killed with signal 6
6 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 0 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 125 ms 4124 KB Output is correct
7 Correct 348 ms 15464 KB Output is correct
8 Correct 1444 ms 108124 KB Output is correct
9 Correct 1567 ms 108124 KB Output is correct
10 Correct 1457 ms 108024 KB Output is correct
11 Correct 1383 ms 108224 KB Output is correct
12 Correct 1280 ms 108124 KB Output is correct
13 Correct 841 ms 108124 KB Output is correct
14 Correct 1414 ms 108124 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 Incorrect 1 ms 364 KB Output isn't correct
19 Halted 0 ms 0 KB -