oj.uz

Submission #364002

# Submission time Handle Problem Language Result Execution time Memory
364002 2021-02-07T22:30:22 Z rocks03 Comparing Plants (IOI20_plants) C++14
70 / 100
 1723 ms 129116 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;

vector<vector<int>> g, g2;
void build_G(){
    g.resize(N);
    g2.resize(N);
    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;
        if(lt[0][i] != i){
            g[i].pb(lt[0][i]);
            g2[lt[0][i]].pb(i);
        }
        if(rt[0][i] != i){
            g[i].pb(rt[0][i]);
            g2[rt[0][i]].pb(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]];
        }
    }
    */
}

vector<vector<bool>> vis;
void bfs(int s){
    vis[s].resize(N, false);
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(auto u : g[v]){
            if(!vis[s][u]){
                vis[s][u] = true;
                q.push(u);
            }
        }
    }
}

vector<bool> vis1, vis2;
void bfs_zero(int s){
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(auto u : g[v]){
            if(!vis1[u]){
                vis1[u] = true;
                q.push(u);
            }
        }
    }
    q.push(s);
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(auto u : g2[v]){
            if(!vis2[u]){
                vis2[u] = true;
                q.push(u);
            }
        }
    }
}

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();
    if(N <= 300){
        vis.resize(N);
        for(int i = 0; i < N; i++){
            bfs(i);
        }
    }
    vis1.resize(N, false);
    vis2.resize(N, false);
    bfs_zero(0);
}

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(N <= 300){
        if(vis[x][y]){
            return 1;
        } else if(vis[y][x]){
            return -1;
        } else{
            return 0;
        }
    }
	if(x == 0){
	    if(vis1[y]){
	        return 1;
	    } else if(vis2[y]){
	        return -1;
	    } else return 0;
	}
	if(P[x] > P[y]){
	    return 1;
	} else if(P[x] < P[y]){
	    return -1;
	} else{
	    return 0;
	}
    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 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 59 ms 3180 KB Output is correct
7 Incorrect 111 ms 15336 KB Output isn't correct
8 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 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 5 ms 876 KB Output is correct
7 Correct 85 ms 6124 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 5 ms 876 KB Output is correct
10 Correct 87 ms 6124 KB Output is correct
11 Correct 77 ms 6124 KB Output is correct
12 Correct 74 ms 6380 KB Output is correct
13 Correct 91 ms 6124 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 0 ms 364 KB Output is correct
3 Correct 0 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 5 ms 876 KB Output is correct
7 Correct 85 ms 6124 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 5 ms 876 KB Output is correct
10 Correct 87 ms 6124 KB Output is correct
11 Correct 77 ms 6124 KB Output is correct
12 Correct 74 ms 6380 KB Output is correct
13 Correct 91 ms 6124 KB Output is correct
14 Correct 181 ms 15464 KB Output is correct
15 Correct 1723 ms 126196 KB Output is correct
16 Correct 172 ms 15464 KB Output is correct
17 Correct 1722 ms 126284 KB Output is correct
18 Correct 847 ms 125788 KB Output is correct
19 Correct 849 ms 126044 KB Output is correct
20 Correct 1536 ms 125916 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 66 ms 4204 KB Output is correct
4 Correct 661 ms 126812 KB Output is correct
5 Correct 794 ms 126172 KB Output is correct
6 Correct 1040 ms 126044 KB Output is correct
7 Correct 1298 ms 125888 KB Output is correct
8 Correct 1696 ms 126092 KB Output is correct
9 Correct 678 ms 125916 KB Output is correct
10 Correct 717 ms 125788 KB Output is correct
11 Correct 573 ms 125788 KB Output is correct
12 Correct 612 ms 125916 KB Output is correct
13 Correct 916 ms 125916 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 2 ms 492 KB Output is correct
7 Correct 15 ms 1132 KB Output is correct
8 Correct 16 ms 1132 KB Output is correct
9 Correct 16 ms 1516 KB Output is correct
10 Correct 16 ms 1516 KB Output is correct
11 Correct 19 ms 1516 KB Output is correct
12 Correct 19 ms 1516 KB Output is correct
13 Correct 16 ms 1536 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 4 ms 876 KB Output is correct
6 Correct 805 ms 128260 KB Output is correct
7 Correct 1042 ms 128364 KB Output is correct
8 Correct 1304 ms 128632 KB Output is correct
9 Correct 1692 ms 128748 KB Output is correct
10 Correct 680 ms 128220 KB Output is correct
11 Correct 1178 ms 128860 KB Output is correct
12 Correct 651 ms 129116 KB Output is correct
13 Correct 788 ms 128248 KB Output is correct
14 Correct 1048 ms 128496 KB Output is correct
15 Correct 1362 ms 128720 KB Output is correct
16 Correct 686 ms 128000 KB Output is correct
17 Correct 774 ms 128292 KB Output is correct

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 384 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 59 ms 3180 KB Output is correct
7 Incorrect 111 ms 15336 KB Output isn't correct
8 Halted 0 ms 0 KB -