Submission #335032

#	Time	Username	Problem	Language	Result	Execution time	Memory
335032		rocks03	Comparing Plants (IOI20_plants)	C++14	14 / 100	4148 ms	1034032 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 n;
    vector<int> st, lazy;
    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);
            st[i] = min(st[2*i+1], st[2*i+2]);
        }
    }
    void build(int sz, vector<int>& a){
        n = sz;
        st.resize(4 * n, n+1);
        lazy.resize(4 * n, 0);
        build(0, 0, n - 1, a);
    }
    void push(int i){
        if(lazy[i] != 0){
            lazy[2*i+1] += lazy[i];
            st[2*i+1] += lazy[i];
            lazy[2*i+2] += lazy[i];
            st[2*i+2] += lazy[i];
        }
        lazy[i] = 0;
    }
    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 res = -1;
        if(res == -1){
            res = ask(2*i+1, l, m, ql, qr);
        }
        if(res == -1){
            res = ask(2*i+2, m + 1, r, ql, qr);
        }
        st[i] = min(st[2*i+1], st[2*i+2]);
        return res;
    }
    int ask(int l, int r){
        int res = ask(0, 0, n - 1, l, r);
        return res;
    }
    void add(int i, int l, int r, int ql, int qr){
        if(qr < l || ql > r){
            return;
        }
        if(ql <= l && r <= qr){
            st[i]--;
            lazy[i]--;
            return;
        }
        push(i);
        int m = (l + r) / 2;
        add(2*i+1, l, m, ql, qr);
        add(2*i+2, m+1, r, ql, qr);
        st[i] = min(st[2*i+1], st[2*i+2]);
    }
    void add(int l, int r){
        add(0, 0, n - 1, l, r);
    }
    void pop(int i, int l, int r, int p, int k){
        if(l == r){
            st[i] = k;
            return;
        }
        push(i);
        int m = (l + r) / 2;
        if(p <= m)
            pop(2*i+1, l, m, p, k);
        else
            pop(2*i+2, m+1, r, p, k);
        st[i] = min(st[2*i+1], st[2*i+2]);
    }
    void pop(int i, int k){
        pop(0, 0, n-1, i, k);
    }
};

int N, K;
vector<int> P, R;
SegmentTree st;

int ask(int l, int r){
    return st.ask(l, r);
    /*
    for(int i = l; i <= r; i++){
        if(R[i] == 0)
            return i;
    }
    return -1;
    */
}

void pop(int i){
    st.pop(i, N);
}

void add(int l, int r){
    st.add(l, r);
    /*
    for(int i = l; i <= r; i++){
        R[i]--;
    }
    */
}

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

void genera(){
    int n = N;
    while(n >= 0){
        int pos = ask(0, N-1);
        f(n, pos);
    }
}

vector<vector<int>> g, g2;
vector<bool> vis[2];

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

void init(int k, vector<int> r){
    N = SZ(r), K = k, R = r;
    P.resize(N);
    st.build(N, r);
    genera();
    g.resize(N);
    g2.resize(N);
    for(int i = 0; i < N; i++){
        for(int j = i + 1; j <= i + K - 1; j++){
            if(P[i] > P[j % N]){
                g[i].pb(j % N);
                g2[j % N].pb(i);
            } else{
                g[j % N].pb(i);
                g2[i].pb(j % N);
            }
        }
    }
    bfs(0);
}

int compare_plants(int x, int y){
	if(x == 0){
	    if(vis[0][y])
	        return 1;
	    if(vis[1][y])
	        return -1;
	    return 0;
	}
	if(P[x] > P[y])
	    return 1;
	if(P[x] < P[y])
	    return -1;
    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: 14 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25