제출 #800258

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
800258		becaido	식물 비교 (IOI20_plants)	C++17	15 / 100	583 ms	42768 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);
        mn[pos] += INF;
        return;
    }
    int mid = (l + r) / 2;
    dfs(lpos, l, mid);
    dfs(rpos, mid + 1, r);
    pull(pos, l, r);
}

int mnp[SIZE * 4];
bool vs[SIZE];
int cmp(int l, int r) {
    int mnl = p[l], mnr = p[r];
    return (!vs[l] && (vs[r] || mnl < mnr)) ? l : r;
}
void build2(int pos, int l, int r) {
    if (l == r) {
        mnp[pos] = l;
        return;
    }
    int mid = (l + r) / 2;
    build2(lpos, l, mid);
    build2(rpos, mid + 1, r);
    mnp[pos] = cmp(mnp[lpos], mnp[rpos]);
}
void upd2(int pos, int l, int r, int p) {
    if (l == r) {
        vs[l] = 1;
        return;
    }
    int mid = (l + r) / 2;
    if (p <= mid) upd2(lpos, l, mid, p);
    else upd2(rpos, mid + 1, r, p);
    mnp[pos] = cmp(mnp[lpos], mnp[rpos]);
}
int que(int pos, int l, int r, int L, int R) {
    if (l == L && r == R) return mnp[pos];
    int mid = (L + R) / 2;
    if (r <= mid) return que(lpos, l, r, L, mid);
    if (l > mid) return que(rpos, l, r, mid + 1, R);
    return cmp(que(lpos, l, mid, L, mid), que(rpos, mid + 1, r, mid + 1, R));
}
int que(int l, int r) {
    int re = l <= r ? que(1, l, r, 0, n - 1) : cmp(que(1, l, n - 1, 0, n - 1), que(1, 0, r, 0, n - 1));
    if (vs[re]) re = -1;
    //debug(l, r, re);
    return re;
}

int id[SIZE];
bool big[SIZE], sml[SIZE];
vector<int> rev[SIZE];
void init(int _k, vector<int> r) {
    n = r.size();
    k = _k;
    FOR (i, 0, n - 1) a[i] = r[i], p[i] = -1;
    build(1, 0, n - 1);
    int sz = n;
    FOR (i, 0, n - 1) {
        if (sz == 0) break;
        dfs(1, 0, n - 1);
        vector<int> all;
        assert(d.size() > 0);
        for (auto it = d.rbegin(); it != d.rend(); it++) {
            auto [ld, j] = *it;
            if (ld < k) break;
            all.pb(j);
        }
        assert(all.size() > 0);
        sz -= all.size();
        for (int j : all) {
            del(j);
            p[j] = i;
            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);
            }
        }
    }
    iota(id, id + n, 0);
    sort(id, id + n, [](int l, int r) {
        return p[l] < p[r];
    });
    build2(1, 0, n - 1);
    FOR (i, 0, n - 1) {
        int cur = id[i];
        //debug(cur);
        int l = cur - k + 1, r = cur - 1;
        if (l < 0) l += n;
        if (r < 0) r += n;
        int to = que(l, r);
        if (to != -1) adj[cur].pb(to);
        l = cur + 1, r = cur + k - 1;
        if (l >= n) l -= n;
        if (r >= n) r -= n;
        to = que(l, r);
        if (to != -1) adj[cur].pb(to);
        upd2(1, 0, n - 1, cur);
    }
    FOR (i, 0, n - 1) for (int j : adj[i]) rev[j].pb(i);
    queue<int> q;
    q.push(0);
    while (q.size()) {
        int pos = q.front();
        q.pop();
        for (int np : adj[pos]) if (!big[np]) {
            big[np] = 1;
            q.push(np);
        }
    }
    q.push(0);
    while (q.size()) {
        int pos = q.front();
        q.pop();
        for (int np : rev[pos]) if (!sml[np]) {
            sml[np] = 1;
            q.push(np);
        }
    }
}

int compare_plants(int x, int y) {
    return big[y] ? -1 : sml[y] ? 1 : 0;
}

/*
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

ex1(4 1 2 5 3 0)
6 4 5
1 3 2 0 1 3
0 1
3 4
2 0
1 3
5 2
*/

/*

    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;
    }
*/

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