Submission #308341

#	Time	Username	Problem	Language	Result	Execution time	Memory
308341		bruce_test	Comparing Plants (IOI20_plants)	C++11	25 / 100	173 ms	25960 KiB

plants

#include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define lc (rt<<1)
#define rc (rt<<1|1)
#define pb push_back
#define cl(a, b) memset(a, b, sizeof(a))
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vii;
typedef vector<pii> viii;
const int inf = 0x3F3F3F3F;
const ll infl = 0x3F3F3F3F3F3F3F3FLL;
const int mod = 1e9 + 7, MM = 2e5+5;
int N, K, lz[4*MM], mi[4*MM]; vi ord1, ord2;
void pushdn(int rt){
    mi[lc]+=lz[rt]; mi[rc]+=lz[rt];
    lz[lc]+=lz[rt]; lz[rc]+=lz[rt]; lz[rt]=0;
}
void upd(int L, int R, int l, int r, int val, int rt){
    if(r < L || l > R) return;
    if(l <= L && R <= r){ mi[rt]+=val; lz[rt]+=val; return; }
    if(lz[rt]) pushdn(rt);
    int mid = (L+R)/2;
    if(l <= mid) upd(L, mid, l, r, val, lc);
    if(r > mid) upd(mid+1, R, l, r, val, rc);
    mi[rt] = min(mi[lc], mi[rc]);
}
int qry(int L, int R, int rt){
    if(mi[rt] > 0) return -1;
    if(L==R) return L;
    if(lz[rt]) pushdn(rt);
    int mid = (L+R)/2;
    if(mi[lc] > 0) return qry(mid+1, R, rc);
    return qry(L, mid, lc);
}
vi solve(vi& r){
    vi ret(N); cl(lz, 0); cl(mi, 0);
    for(int i=0; i<N; i++)
        upd(0, N-1, i, i, r[i], 1);
    for(int i=0; i<N; i++){
        int pos = qry(0, N-1, 1);
        ret[pos] = i;
        upd(0, N-1, pos, pos, inf, 1);
        upd(0, N-1, pos-K+1, pos-1, -1, 1);
        if(pos-K+1<0) upd(0, N-1, pos+N-K, N-1, -1, 1);
    }
//    for(int x: ret) cout << x << " ";
//    cout << endl;
    return ret;
}
void init(int k, vi r){
    r.insert(r.end(), r.begin(), r.end());
    N = r.size(); K = k;
    ord1 = solve(r);
    for(int &x: r) x = k-1-x;
    ord2 = solve(r);
}
int compare_plants(int x, int y){
    if(x > y) return -compare_plants(y, x);
    if(ord1[x] > ord1[y] || ord2[x+N/2] < ord2[y]) return -1;
    if(ord2[x] > ord2[y] || ord1[x+N/2] < ord1[y]) return 1;
    return 0;
}
//int main(){
//    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//    int k=3; vi a={0, 1, 1, 2};
//    init(k, a);
//    for(int i=0; i<a.size(); i++)
//        for(int j=i+1; j<a.size(); j++)
//            cout << i << " vs " << j << " = " << compare_plants(i, j) << endl;
//}

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