제출 #541828

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
541828		LucaDantas	식물 비교 (IOI20_plants)	C++17	0 / 100	47 ms	3444 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

constexpr int maxn = 1<<17;

int n, k;

struct SegmentTree {
	int tree[maxn<<1], lazy[maxn<<1];
	void flush(int node, int i, int j) {
		if(!lazy[node]) return;
		if(i != j) {
			lazy[node<<1] += lazy[node];
			lazy[node<<1|1] += lazy[node];
		}
		tree[node] += lazy[node];
		lazy[node] = 0;
	}
	void build(int node, int i, int j, const vector<int>& r) {
		if(i == j) return (void)(tree[node] = r[i]);
		int m = (i+j) >> 1;
		build(node<<1, i, m, r);
		build(node<<1|1, m+1, j, r);
		tree[node] = min(tree[node<<1], tree[node<<1|1]);
	}
	int find(int l, int r) {
		if(l <= r) return find(1, 0, n-1, l, r);
		int p1 = find(1, 0, n-1, l, n-1);
		if(p1 != -1) return p1;
		return find(1, 0, n-1, 0, r);
	}
	int find(int node, int i, int j, int l, int r) {
		flush(node, i, j);
		if(tree[node] > 0) return -1;
		if(i == j) return i;
		int m = (i+j) >> 1;
		int p1 = find(node<<1, i, m, l, r);
		if(p1 != -1) return p1;
		return find(node<<1|1, m+1, j, l, r);
	}
	void upd(int l, int r) {
		if(l <= r) upd(1, 0, n-1, l, r);
		else upd(1, 0, n-1, l, n-1), upd(1, 0, n-1, 0, r);
	}
	void upd(int node, int i, int j, int l, int r) {
		flush(node, i, j);
		if(i > r || j < l) return;
		if(i >= l && j <= r) {
			lazy[node] = -1;
			flush(node, i, j);
			return;
		}
		int m = (i+j) >> 1;
		upd(node<<1, i, m, l, r);
		upd(node<<1|1, m+1, j, l, r);
		tree[node] = min(tree[node<<1], tree[node<<1|1]);
	}
	void point(int node, int i, int j, int pos) {
		flush(node, i, j);
		if(i == j) return (void)(tree[node] = 0x3f3f3f3f);
		int m = (i+j) >> 1;
		if(pos <= m) point(node<<1, i, m, pos);
		else point(node<<1|1, m+1, j, pos);
		tree[node] = min(tree[node<<1], tree[node<<1|1]);
	}
} seg;

int ordem[maxn];

void init(int K, std::vector<int> r) {
	n = (int)(r.size());
	k = K;
	seg.build(1, 0, n-1, r);
	for(int i = 0; i < n; i++) {
		int mn = seg.find(0, n-1);
		int val = seg.find((mn - k + 1 + n) % n, mn);
		while(val != mn && val != -1)
			mn = val, val = seg.find((mn - k + 1 + n) % n, mn);

		ordem[mn] = i;

		seg.upd((mn - k + 1 + n) % n, mn); // removo 1 de todo mundo
		seg.point(1, 0, n-1, mn);
	}
}

int compare_plants(int x, int y) {
	return ordem[x] < ordem[y] ? 1 : -1;
}

• Subtask 1: 0 / 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