Submission #302758

#	Time	Username	Problem	Language	Result	Execution time	Memory
302758		MarcoMeijer	Comparing Plants (IOI20_plants)	C++14	44 / 100	1409 ms	45980 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>

using namespace std;

#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define RE(a,b) REP(a,0,b)
#define FOR(a,b) for(auto& a:b)
#define pb push_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

const int INF=1e9;
const int MX=4e5+100;

int n, k;
vi r;
int h[MX];

struct Seg {
    ii SEG[MX*4]; int LAZY[MX*4];
    void build(const vi& f, int p=0, int l=0, int r=n-1) {
        LAZY[p] = 0;
        if(l == r) {
            SEG[p] = {f[l], l};
            return;
        }
        int m=(l+r)/2;
        build(f,p*2+1,l,m);
        build(f,p*2+2,m+1,r);
        SEG[p] = max(SEG[p*2+1], SEG[p*2+2]);
    }
    void add(int i, int j, int v, int lazy=0, int p=0, int l=0, int r=n-1) {
        LAZY[p] += lazy;
        SEG[p].fi += lazy;
        if(j < l || i > r) return;
        if(i <= l && j >= r) {
            SEG[p].fi += v;
            LAZY[p] += v;
            return;
        }
        int m=(l+r)/2;
        add(i,j,v,LAZY[p],p*2+1,l,m);
        add(i,j,v,LAZY[p],p*2+2,m+1,r);
        LAZY[p] = 0;
        SEG[p] = max(SEG[p*2+1], SEG[p*2+2]);
    }
    void addRound(int i, int j, int v) {
        if(i >= n) i-=n, j-=n;
        if(j < n) {
            add(i,j,v);
        } else {
            add(i,n-1,v);
            add(0,j-n,v);
        }
    }
} seg1, seg2;

int ans0[MX];

void fill0() {
    int x=0, y=n-1;
    RE(i,n) ans0[i] = 0;
    set<int> s; s.insert(h[x]);
    REP(i,x+1,y+1) {
        if(s.empty()) break;
        int p = *s.begin();
        if(p < h[i]) {
            s.insert(h[i]);
            ans0[i] = -1;
        }
        if(i >= k-1) s.erase(h[i-k+1]);
    }
    s.clear(); s.insert(h[x]);
    REP(i,x+1,y+1) {
        if(s.empty()) break;
        int p = *(--s.end());
        if(p > h[i]) {
            s.insert(h[i]);
            ans0[i] = 1;
        }
        if(i >= k-1) s.erase(h[i-k+1]);
    }
    s.clear(); s.insert(h[x]);
    REV(i,x+1,y+1) {
        if(s.empty()) break;
        int p = *s.begin();
        if(p < h[i]) {
            s.insert(h[i]);
            ans0[i] = -1;
        }
        if(i >= k-1) s.erase(h[i-k+1]);
    }
    s.clear(); s.insert(h[x]);
    REV(i,x+1,y+1) {
        if(s.empty()) break;
        int p = *(--s.end());
        if(p > h[i]) {
            s.insert(h[i]);
            ans0[i] = 1;
        }
        if(i >= k-1) s.erase(h[i-k+1]);
    }
}
void init(int _k, vi _r) {
    k = _k; r = _r;
    n = r.size();

    seg1.build(r);
    seg2.build(vi(n,0));

    RE(i,n) {
        while(seg1.SEG[0].fi == k-1) {
            int x = seg1.SEG[0].se;
            seg1.add(x,x,-INF);
            seg2.add(x,x,1);
            seg2.addRound(x+1,x+k-1,-1);
        }

        int x = seg2.SEG[0].se;
        seg2.add(x,x,-INF);
        seg2.addRound(x+1,x+k-1,1);
        seg1.addRound(x+n-k+1,x+n-1,1);
        h[x] = h[x+n] = i;
    }
    fill0();
	return;
}

int comp(int x, int y) {
    if(y < x) y += n;
    if(h[x] < h[y]) {
        set<int> s; s.insert(h[x]);
        REP(i,x+1,y+1) {
            if(s.empty()) break;
            int p = *s.begin();
            if(p < h[i]) {
                s.insert(h[i]);
            }
            if(i >= k-1) s.erase(h[i-k+1]);
        }
        if(s.count(h[y])) return -1;
        return 0;
    } else {
        set<int> s; s.insert(h[x]);
        REP(i,x+1,y+1) {
            if(s.empty()) break;
            int p = *(--s.end());
            if(p > h[i]) {
                s.insert(h[i]);
            }
            if(i >= k-1) s.erase(h[i-k+1]);
        }
        if(s.count(h[y])) return 1;
        return 0;
    }
}
int compare_plants(int x, int y) {
    if(x == 0) {
        return ans0[y];
    } else if(n <= 300) {
        int res = comp(x,y);
        if(res != 0) return res;
        res = comp(y,x);
        return -res;
    } else {
        if(h[x] < h[y]) return -1;
        else return 1;
    }
}

• 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