제출 #302999

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
302999		8e7	식물 비교 (IOI20_plants)	C++14	5 / 100	115 ms	9452 KiB

plants

#include "plants.h"
#include <iostream>
#include <algorithm>
#include <queue>
#define ll long long
#define maxn 200005
using namespace std;
vector<int> v, one, zero, ind1, ind0, arr;
int k;
int n;
int seg[4 * maxn], tag[4 * maxn];
vector<int> ze;
void ini(int cur, int l, int r) {
	if (r <= l) return;
	if (r - l == 1) {
		seg[cur] = v[l];
		return;
	}
	int mid = (l + r) / 2;
	ini(cur * 2, l, mid);
	ini(cur * 2 + 1, mid, r);
	seg[cur] = min(seg[cur * 2], seg[cur * 2 + 1]);
}
void modify(int cur, int l, int r, int ql, int qr) {
	if (r <= l || ql >= r || qr <= l) return;
	if (ql <= l && qr >= r) {
		tag[cur]++;
		return;
	}
	int mid = (l + r) / 2;
	modify(cur * 2, l, mid, ql, qr);
	modify(cur * 2 + 1, mid, r, ql, qr);
	seg[cur] = min(seg[cur * 2] - tag[cur * 2], seg[cur * 2 + 1] - tag[cur * 2 + 1]);
}
void sz(int cur, int l, int r, int x) {
	if (r <= l) return;
	//cout << l << " " << r << " " << seg[cur] - tag[cur] - x << endl;
	if (r - l == 1) {
		if (seg[cur] - tag[cur] - x == 0) {
			ze.push_back(l);
			tag[cur] = -1000000;
		}
		return;
	}
	int mid = (l + r) / 2;
	if (seg[cur * 2] - tag[cur * 2] - x - tag[cur] == 0) {
		sz(cur * 2, l, mid, x + tag[cur]);
	}
	if (seg[cur * 2 + 1] - tag[cur * 2 + 1] - x - tag[cur] == 0) {
		sz(cur * 2 + 1, mid, r, x + tag[cur]);
	}
	seg[cur] = min(seg[cur * 2] - tag[cur * 2], seg[cur * 2 + 1] - tag[cur * 2 + 1]);
}
bool cmp(int a, int b) {
	if (a < b) {
		return a + k < b;
	} else {
		return (a + k) < b + n;
	}
}
void init(int K, vector<int> r) {
	v = r;
	n = r.size();
	arr.resize(n);
	k = K;
	if (K == 2) {
		int cnt = 0, cur = 0;
		one.push_back(cnt);
		for (int i = 0;i < n;i++) {
			if (r[i] == 0) {
				ind1.push_back(cur);
				cur = i + 1;
				cnt++;
			}
			one.push_back(cnt);
		}
		if (r[n - 1] == 1) {
			for (int i = n - 1;i >= 0;i--) {
				if (one[i] == cnt) ind1[0] = i;
				one[i] %= cnt;
			}
		}
		cnt = 0, cur = 0;
		zero.push_back(cnt);
		for (int i = 0;i < n;i++) {
			if (r[i] == 1) {
				ind0.push_back(cur);
				cur = i + 1;
				cnt++;
			}
			zero.push_back(cnt);
		}
		if (r[n - 1] == 0) {
			for (int i = n - 1;i >= 0;i--) {
				if (zero[i] == cnt) ind0[0] = i;
				zero[i] %= cnt;
			}
		}
	} else {
		ini(1, 0, n);
		priority_queue<int, vector<int>, bool(*) (int, int) > pq(cmp);
		for (int i = n;i >= 1;i--) {
			sz(1, 0, n, 0);
			//cout << endl;
			for (int j:ze) {
				//cout << j << ' ';
				pq.push(j);
			}
			//cout << endl;
			ze.clear();
			int ind = pq.top();
			pq.pop();
			arr[ind] = i;
			if (ind - k + 1 < 0) {
				modify(1, 0, n, 0, ind + 1);
				modify(1, 0, n, n - k + ind + 1, n);
			} else {
				modify(1, 0, n, ind - k + 1, ind + 1);
			}
		}
		//for (int i = 0;i < n;i++) cout << arr[i] << " ";
		//cout << endl;
	}
	return;
}

int compare_plants(int x, int y) {
	if (k == 2) {
		if (one[x] != one[y] && zero[x] != zero[y]) {
			return 0;
		} else {
			if (one[x] == one[y]) {
				//cout <<(x - ind1[one[x]] + n) % n << " " << (y - ind1[one[y]] + n) % n << endl;
				if ((x - ind1[one[x]] + n) % n < (y - ind1[one[y]] + n) % n) return -1;
				else return 1;
			} else {
				if ((x - ind0[zero[x]] + n) % n < (y - ind0[zero[y]] + n) % n) return 1;
				else return -1;
			}
		}
	} else {
		return arr[x] > arr[y] ? 1 : -1;
	}
}
/*
5 1 3
1 1 0 0 1
0 1
0 3
2 4


7 4 5
3 1 2 2 0 1 2
0 3
2 4
3 6
1 5
2 5
 */

• 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