Submission #335280

#	Time	Username	Problem	Language	Result	Execution time	Memory
335280		rocks03	Comparing Plants (IOI20_plants)	C++14	11 / 100	107 ms	12392 KiB

plants

#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()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

class SegmentTree{
    public:
    int sz;
    vector<int> st, lazy;
    void push(int i){
        if(lazy[i]){
            st[2 * i + 1] += lazy[i];
            lazy[2 * i + 1] += lazy[i];
            st[2 * i + 2] += lazy[i];
            lazy[2 * i + 2] += lazy[i];
        }
        lazy[i] = 0;
    }
    void merge(int i){
        st[i] = min(st[2 * i + 1], st[2 * i + 2]);
    }
    void build(int i, int l, int r, vector<int>& R){
        if(l == r){
            st[i] = R[l];
        } else{
            int m = (l + r) / 2;
            build(2*i+1, l, m, R);
            build(2*i+2, m+1, r, R);
            merge(i);
        }
    }
    void build(int n, vector<int>& R){
        sz = n;
        st.resize(4 * sz);
        lazy.resize(4 * sz);
        build(0, 0, n - 1, R);
    }
    int ask(int i, int l, int r, int ql, int qr){
        if(qr < l || ql > r || st[i] != 0){
            return -1;
        }
        if(l == r){
            return l;
        }
        push(i);
        int m = (l + r) / 2;
        int ans = ask(2 * i + 1, l, m, ql, qr);
        if(ans == -1)
            ans = ask(2 * i + 2, m + 1, r, ql, qr);
        return ans;
    }
    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> R, P;
int ask(int l, int r){
    return st.ask(0, 0, N - 1, l, r);
}
void add(int l, int r, int k){
    st.add(0, 0, N - 1, l, r, k);
}

void f(int& n, int i){
    int j = -1;
    while(1){
        int l = i - K + 1, r = i - 1;
        if(r < 0){
            l += N, r += N;
            j = ask(l, r);
        } else if(l < 0){
            l += N;
            j = max(ask(0, r), ask(l, N-1));
        } else{
            j = ask(l, r);
        }
        if(j == -1) break;
        f(n, j);
    }
    P[i] = n--;
    add(i, i, N+1);
    int l = i - K + 1, r = i - 1;
    if(r < 0){
        l += N, r += N;
        add(l, r, -1);
    } else if(l < 0){
        add(0, r, -1);
        l += N;
        add(l, N-1, -1);
    } else{
        add(l, r, -1);
    }
}

void build_plants(){
    st.build(N, R);
    int n = N;
    while(n){
        f(n, ask(0, N-1));
    }
}

class MergeSortTree{
    public:
    int sz;
    vector<vector<pii>> st;
    void combine(int i){
        for(auto x : st[2 * i + 1]){
            st[i].pb(x);
        }
        for(auto x : st[2 * i + 2]){
            st[i].pb(x);
        }
        sort(all(st[i]));
    }
    void build(int i, int l, int r, vector<int>& P){
        if(l == r){
            st[i].pb({P[l], l});
        } else{
            int m = (l + r) / 2;
            build(2 * i + 1, l, m, P);
            build(2 * i + 2, m + 1, r, P);
            combine(i);
        }
    }
    void build(int n, vector<int>& P){
        sz = n;
        st.resize(4 * n);
        build(0, 0, n - 1, P);
    }
    pii best(pii a, pii b){
        if(a.ff > b.ff) return a;
        else return b;
    }
    pii query(int i, int l, int r, int ql, int qr, int k){
        if(ql <= l && r <= qr){
            pii p = {k, -1};
            int pos = upper_bound(all(st[i]), p) - st[i].begin() - 1;
            if(pos < 0 || st[i][pos].ff >= k){
                return {-1, -1};
            }
            return st[i][pos];
        }
        if(qr < l || ql > r){
            return {-1, -1};
        }
        int m = (l + r) / 2;
        pii a = query(2 * i + 1, l, m, ql, qr, k);
        pii b = query(2 * i + 2, m + 1, r, ql, qr, k);
        return best(a, b);
    }
    pii query(int l, int r, int k){
        return query(0, 0, sz - 1, l, r, k);
    }
};
MergeSortTree mt;

pii best(pii a, pii b){
    if(a.ff > b.ff) return a;
    else return b;
}

pii query(int l, int r, int k){
    return mt.query(l, r, k);
}

vector<vector<int>> g, g2;
void build_graph(){
    g.resize(N);
    g2.resize(N);
    mt.build(N, P);
    for(int i = 0; i < N; i++){
        int l, r;
        pii u;
        l = i + 1, r = i + K - 1;
        if(l >= N){
            l %= N, r %= N;
            u = query(l, r, P[i]);
        } else if(r >= N){
            r %= N;
            u = best(query(l, N - 1, P[i]), query(0, r, P[i]));
        } else{
            u = query(l, r, P[i]);
        }
        if(u.ss != -1){
            g[i].pb(u.ss);
            g2[u.ss].pb(i);
        }
        l = i - K + 1, r = i - 1;
        if(r < 0){
            l += N, r += N;
            u = query(l, r, P[i]);
        } else if(l < 0){
            l += N;
            u = best(query(0, r, P[i]), query(l, N - 1, P[i]));
        } else{
            u = query(l, r, P[i]);
        }
        if(u.ss != -1){
            g[i].pb(u.ss);
            g2[u.ss].pb(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, R = r;
    P.resize(N);
    build_plants();
    build_graph();
    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 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[x]){
	        return 1;
	    } else if(vis2[x]){
	        return -1;
	    } else return 0;
	}
	if(P[x] > P[y]){
	    return 1;
	} else if(P[x] < P[y]){
	    return -1;
	} else{
	    return 0;
	}
}

Compilation message (stderr)

plants.cpp:2: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    2 | #pragma GCC optimization("O3")
      | 
plants.cpp:3: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    3 | #pragma GCC optimization("unroll-loops")
      |

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 11 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25