Submission #335274

#	Time	Username	Problem	Language	Result	Execution time	Memory
335274		rocks03	Comparing Plants (IOI20_plants)	C++14	44 / 100	464 ms	17664 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));
    }
}

void init(int k, vector<int> r){
    N = SZ(r), K = k, R = r;
    P.resize(N);
    build_plants();
}

int compare_plants(int x, int y){
	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: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25