oj.uz

Submission #363996

# Submission time Handle Problem Language Result Execution time Memory
363996 2021-02-07T21:43:10 Z rocks03 Comparing Plants (IOI20_plants) C++14
0 / 100
 1714 ms 2097156 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;
    }
}

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 - y + x);
}
int jumpL(int x, int y){
    if(x <= y){
        return (x + N - y);
    }
    return (x - 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:205:1: warning: control reaches end of non-void function [-Wreturn-type]
  205 | }
      | ^

Subtask #1
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 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 122 ms 4076 KB Output is correct
7 Incorrect 302 ms 15444 KB Output isn't correct
8 Halted 0 ms 0 KB -

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 Runtime error 1714 ms 2097156 KB Execution killed with signal 9
4 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 Runtime error 1714 ms 2097156 KB Execution killed with signal 9
4 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 Runtime error 1123 ms 2097156 KB Execution killed with signal 9
3 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 Incorrect 1 ms 384 KB Output isn't correct
4 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 Runtime error 1116 ms 2097156 KB Execution killed with signal 9
5 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 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 122 ms 4076 KB Output is correct
7 Incorrect 302 ms 15444 KB Output isn't correct
8 Halted 0 ms 0 KB -