Submission #800193

#	Time	Username	Problem	Language	Result	Execution time	Memory
800193		becaido	Comparing Plants (IOI20_plants)	C++17	5 / 100	96 ms	27704 KiB

plants

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "plants.h"
#endif

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

#define lpos pos*2
#define rpos pos*2+1

const int INF = 1e9;
const int SIZE = 2e5 + 5;

int n, k;
int a[SIZE], p[SIZE];
vector<int> adj[SIZE];
vector<pair<int, int>> g[SIZE];

set<int> s;
set<pair<int, int>> d;
int dis(int l, int r) {
    return l < r ? r - l : r + n - l;
}
void add(int i) {
    if (s.size() == 0) {
        s.insert(i);
        d.emplace(n, i);
        return;
    }
    auto it = s.lower_bound(i);
    int L = (it == s.begin() ? *s.rbegin() : *prev(it));
    int R = (it == s.end() ? *s.begin() : *it);
    d.erase({dis(L, R), R});
    d.emplace(dis(L, i), i);
    d.emplace(dis(i, R), R);
    s.insert(i);
}
void del(int i) {
    if (s.size() == 1) {
        s.clear();
        d.clear();
        return;
    }
    auto it = s.lower_bound(i);
    int L = (it == s.begin() ? *s.rbegin() : *prev(it));
    int R = (next(it) == s.end() ? *s.begin() : *next(it));
    s.erase(it);
    d.erase({dis(L, i), i});
    d.erase({dis(i, R), R});
    d.emplace(dis(L, R), R);
}

int mn[SIZE * 4], lazy[SIZE * 4];
void push(int pos, int l, int r) {
    mn[pos] += lazy[pos];
    if (l < r) {
        lazy[lpos] += lazy[pos];
        lazy[rpos] += lazy[pos];
    }
    lazy[pos] = 0;
}
void pull(int pos, int l, int r) {
    int mid = (l + r) / 2;
    push(lpos, l, mid);
    push(rpos, mid + 1, r);
    mn[pos] = min(mn[lpos], mn[rpos]);
}
void build(int pos, int l, int r) {
    if (l == r) {
        mn[pos] = k - 1 - a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(lpos, l, mid);
    build(rpos, mid + 1, r);
    mn[pos] = min(mn[lpos], mn[rpos]);
}
void upd(int pos, int l, int r, int L, int R, int x) {
    if (l == L && r == R) {
        lazy[pos] += x;
        return;
    }
    push(pos, L, R);
    int mid = (L + R) / 2;
    if (r <= mid) upd(lpos, l, r, L, mid, x);
    else if (l > mid) upd(rpos, l, r, mid + 1, R, x);
    else {
        upd(lpos, l, mid, L, mid, x);
        upd(rpos, mid + 1, r, mid + 1, R, x);
    }
    pull(pos, L, R);
}
void dfs(int pos, int l, int r) {
    push(pos, l, r);
    if (mn[pos] != 0) return;
    if (l == r) {
        add(l);
        return;
    }
    int mid = (l + r) / 2;
    dfs(lpos, l, mid);
    dfs(rpos, mid + 1, r);
}

void init(int _k, vector<int> r) {
    n = r.size();
    k = _k;
    FOR (i, 0, n - 1) a[i] = r[i], p[i] = -1;
    if (k == 2) {
        FOR (i, 0, n - 1) {
            if (a[i] == 1) adj[i].pb((i + 1) % n);
            else adj[(i + 1) % n].pb(i);
        }
        int sz = 0;
        FOR (i, 0, n - 1) if (adj[i].size() == 2) {
            for (int x : adj[i]) {
                int cnt = 0;
                g[i].pb(sz, cnt++);
                while (adj[x].size()) {
                    g[x].pb(sz, cnt++);
                    x = adj[x][0];
                }
                g[x].pb(sz, cnt++);
                sz++;
            }
        }
        return;
    }
    build(1, 0, n - 1);
    FOR (i, 0, n - 1) {
        dfs(1, 0, n - 1);
        if (!d.size()) return;
        auto [ld, j] = *d.rbegin();
        //assert(ld >= k);
        del(j);
        p[j] = i;
        upd(1, j, j, 0, n - 1, INF);
        int l = j - k + 1, r = j - 1;
        if (l < 0) l += n;
        if (r < 0) r += n;
        if (l <= r) upd(1, l, r, 0, n - 1, -1);
        else {
            upd(1, l, n - 1, 0, n - 1, -1);
            upd(1, 0, r, 0, n - 1, -1);
        }
    }
}

int compare_plants(int x, int y) {
    if (k == 2) {
        for (auto [gx, px] : g[x]) for (auto [gy, py] : g[y]) if (gx == gy) {
            return px < py ? -1 : 1;
        }
        return 0;
	}
    return p[x] < p[y] ? -1 : 1;
}

/*
in1
4 3 2
0 1 1 2
0 2
1 2
out1
1
-1

in2
4 2 2
0 1 0 1
0 3
1 3
out2
1
0
*/

#ifdef WAIMAI
int main() {
    int n, k, q;
    vector<int> r;
    vector<int> x;
    vector<int> y;
    vector<int> answer;
	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;
}
#endif

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