Submission #335194

#	Time	Username	Problem	Language	Result	Execution time	Memory
335194		rocks03	Comparing Plants (IOI20_plants)	C++14	55 / 100	537 ms	17196 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<vector<bool>> vis[2];

void bfs(int s){
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(auto u : g[v]){
            if(vis[0][s][u] == false){
                vis[0][s][u] = true;
                q.push(u);
            }
        }
    }
    q.push(s);
    while(!q.empty()){
        int v = q.front();
        q.pop();
        for(auto u : g2[v]){
            if(vis[1][s][u] == false){
                vis[1][s][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();
    if(N <= 300){
        g.resize(N);
        g2.resize(N);
        vis[0].resize(N);
        vis[1].resize(N);
        for(int i = 0; i < N; i++){
            vis[0][i].resize(N, false);
            vis[1][i].resize(N, false);
            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);
                }
            }
        }
        for(int i = 0; i < N; i++){
            bfs(i);
        }
    }
}

int compare_plants(int x, int y){
	if(N <= 300){
	    if(vis[0][x][y] || vis[1][y][x])
	        return 1;
	    if(vis[1][x][y] || vis[0][y][x])
	        return -1;
	    return 0;
	}
	if(P[x] > P[y])
	    return 1;
	if(P[x] < P[y])
	    return -1;
    return 0;
}

/*

static int n, k, q;
static std::vector<int> r;
static std:: vector<int> x;
static std:: vector<int> y;
static std:: vector<int> answer;
int main() {
	assert(scanf("%d%d%d", &n, &k, &q) == 3);
	r.resize(n);
	answer.resize(q);
	for (int i = 0; i < n; i++) {
		int value;
		assert(scanf("%d", &value) == 1);
		r[i] = value;
	}
	x.resize(q);
	y.resize(q);
	for (int i = 0; i < q; i++) {
		assert(scanf("%d%d", &x[i], &y[i]) == 2);
	}
	fclose(stdin);

	init(k, r);
	for (int i = 0; i < q; i++) {
		answer[i] = compare_plants(x[i], y[i]);
	}

	for (int i = 0; i < q; i++) {
		printf("%d\n", answer[i]);
	}

	fclose(stdout);

	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: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 11 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25