oj.uz

Submission #364000

# Submission time Handle Problem Language Result Execution time Memory
364000 2021-02-07T22:10:19 Z rocks03 Comparing Plants (IOI20_plants) C++14
44 / 100
 444 ms 15340 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(P[x] < P[y]) return -1;
    return 1;
    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 0 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -

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 3 ms 492 KB Output is correct
7 Correct 70 ms 3456 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 3 ms 492 KB Output is correct
10 Correct 68 ms 5360 KB Output is correct
11 Correct 66 ms 5228 KB Output is correct
12 Correct 67 ms 5484 KB Output is correct
13 Correct 70 ms 5356 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 3 ms 492 KB Output is correct
7 Correct 70 ms 3456 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 3 ms 492 KB Output is correct
10 Correct 68 ms 5360 KB Output is correct
11 Correct 66 ms 5228 KB Output is correct
12 Correct 67 ms 5484 KB Output is correct
13 Correct 70 ms 5356 KB Output is correct
14 Correct 94 ms 6272 KB Output is correct
15 Correct 444 ms 15232 KB Output is correct
16 Correct 91 ms 6380 KB Output is correct
17 Correct 427 ms 15084 KB Output is correct
18 Correct 276 ms 14596 KB Output is correct
19 Correct 275 ms 15340 KB Output is correct
20 Correct 409 ms 15084 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 65 ms 3308 KB Output is correct
4 Correct 241 ms 15224 KB Output is correct
5 Correct 268 ms 14444 KB Output is correct
6 Correct 344 ms 14700 KB Output is correct
7 Correct 412 ms 14956 KB Output is correct
8 Correct 407 ms 14956 KB Output is correct
9 Correct 291 ms 14348 KB Output is correct
10 Correct 246 ms 14316 KB Output is correct
11 Correct 217 ms 14316 KB Output is correct
12 Correct 235 ms 14444 KB Output is correct
13 Correct 266 ms 14444 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Incorrect 1 ms 364 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 0 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 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 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 0 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -