Submission #300638

#	Time	Username	Problem	Language	Result	Execution time	Memory
300638		imeimi2000	Comparing Plants (IOI20_plants)	C++17	100 / 100	921 ms	47864 KiB

plants

#ifdef imeimi

#include <vector>

void init(int k, std::vector<int> r);
int compare_plants(int x, int y);

#include <cstdio>
#include <cassert>
#include <vector>
#define n N
#define k K

static int n, k, q;
static std::vector<int> r;
static std:: vector<int> x;
static std:: vector<int> y;
static std:: vector<int> answer;
int main() {
	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;
}

#undef n
#undef k
#else

#include "plants.h"

#endif

#include <bits/stdc++.h>

using namespace std;

namespace S {
    int seg[1 << 19], add[1 << 19];
    void update(int i, int s, int e, int x, int y, int v) {
        if (e < x || y < s) return;
        if (x <= s && e <= y) {
            seg[i] += v;
            add[i] += v;
            return;
        }
        int m = (s + e) / 2;
        update(i + i, s, m, x, y, v);
        update(i + i + 1, m + 1, e, x, y, v);
        seg[i] = min(seg[i + i], seg[i + i + 1]) + add[i];
    }
    int find(int i, int s, int e, int a = 0) {
        if (seg[i] + a) return 0;
        if (s == e) return s;
        a += add[i];
        int m = (s + e) / 2;
        int ret = find(i + i, s, m, a);
        if (ret) return ret;
        return find(i + i + 1, m + 1, e, a);
    }
}

static int n, k;
static int val[200001], rev[200001];
static int fen[200001], L[200001][18], R[200001][18];

static void update(int i, int x) {
    while (i <= n) {
        fen[i] += x;
        i += i & -i;
    }
}

static int query(int i) {
    int ret = 0;
    while (i) {
        ret += fen[i];
        i -= i & -i;
    }
    return ret;
}

static int find(int v) {
    int x = 0;
    for (int i = 18; i--; ) {
        int y = x + (1 << i);
        if (y <= n && fen[y] <= v) v -= fen[x = y];
    }
    return x + 1;
}

void init(int k, vector<int> r) {
    ::k = k;
    n = r.size();
    set<int> can, one;
    auto add = [&](int x) {
        S::update(1, 1, n, x, x, 1e8);
        auto it = can.insert(x).first;
        if (int(can.size()) == 1) {
            one.insert(x);
            return;
        }
        auto it1 = it;
        if (it1 == can.begin()) it1 = prev(can.end());
        else --it1;
        int d1 = (x - *it1 + n) % n;
        auto it2 = next(it);
        if (it2 == can.end()) it2 = can.begin();
        int d2 = (*it2 - x + n) % n;
        if (it1 == it2) {
            one.erase(*it2);
            if (d1 >= k) one.insert(x);
            if (d2 >= k) one.insert(*it2);
            return;
        }
        if (d1 + d2 >= k) one.erase(*it2);
        if (d1 >= k) one.insert(x);
        if (d2 >= k) one.insert(*it2);
    };
    auto del = [&](int x) {
        S::update(1, 1, n, x - k + 1, x, -1);
        S::update(1, 1, n, n + x - k + 1, n + x, -1);
        auto it1 = can.upper_bound(x);
        auto it2 = it1;
        can.erase(x);
        if (one.count(x)) one.erase(x);
        if (can.empty()) return;
        if (it1 == can.begin()) it1 = prev(can.end());
        else --it1;
        int d1 = (x - *it1 + n) % n;
        if (it2 == can.end()) it2 = can.begin();
        int d2 = (*it2 - x + n) % n;
        if (it1 == it2) {
            one.insert(*it2);
            return;
        }
        if (d2 >= k) one.erase(*it2);
        if (d1 + d2 >= k) one.insert(*it2);
    };
    for (int i = 1; i <= n; ++i) {
        S::update(1, 1, n, i, i, r[i - 1]);
    }
    for (int v = n; v > 0; --v) {
        int x;
        while (x = S::find(1, 1, n)) add(x);
        x = *one.begin();
        del(x);
        val[x] = v;
        rev[v] = x;
    }
    for (int i = n - k + 1; i <= n; ++i) update(val[i], 1);
    for (int i = 1; i <= n; ++i) {
        update(val[(i - k + n - 1) % n + 1], -1);
        int x = find(query(val[i]));
        L[i][0] = x <= n ? (i - rev[x] + n) % n : n;
        update(val[i], 1);
    }
    memset(fen, 0, sizeof(fen));
    for (int i = 1; i <= k; ++i) update(val[i], 1);
    for (int i = n; i > 0; --i) {
        update(val[(i + k + n - 1) % n + 1], -1);
        int x = find(query(val[i]));
        R[i][0] = x <= n ? (rev[x] - i + n) % n : n;
        update(val[i], 1);
    }
    for (int l = 1; l < 18; ++l) {
        for (int i = 1; i <= n; ++i) {
            int x = L[i][l - 1];
            L[i][l] = min(x + L[(i - x + n - 1) % n + 1][l - 1], n);
            x = R[i][l - 1];
            R[i][l] = min(x + R[(i + x - 1) % n + 1][l - 1], n);
        }
    }
}

bool goL(int x, int y) {
    int d = (x - y + n) % n;
    for (int i = 18; i--; ) {
        if (L[x][i] <= d) {
            d -= L[x][i];
            x = (x - L[x][i] + n - 1) % n + 1;
        }
    }
    return d < k && val[x] <= val[y];
}

bool goR(int x, int y) {
    int d = (y - x + n) % n;
    for (int i = 18; i--; ) {
        if (R[x][i] <= d) {
            d -= R[x][i];
            x = (x + R[x][i] - 1) % n + 1;
        }
    }
    return d < k && val[x] <= val[y];
}

bool go(int x, int y) {
    return goL(x, y) || goR(x, y);
}

int compare_plants(int x, int y) {
    if (go(x + 1, y + 1)) return -1;
    if (go(y + 1, x + 1)) return 1;
    return 0;
}

Compilation message (stderr)

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:168:18: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  168 |         while (x = S::find(1, 1, n)) add(x);
      |                ~~^~~~~~~~~~~~~~~~~~

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