제출 #1192319

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1192319		ildar1	Comparing Plants (IOI20_plants)	C++20	0 / 100	2 ms	3400 KiB

plants

#include <iostream>
#include <vector>

#define MAXN 200001

using namespace std;

int ans[MAXN];  //ans[x] = rank of h[x]
int myr[MAXN];
int n;

int h = 31 - __builtin_clz(n);

struct Seg{

	pair<int,int> tree[2*MAXN];
	int lazy[MAXN];

	void make() {
		for (int i=0; i<n; i++) {
			tree[i+n].first = myr[i];
			tree[i+n].second = i;
		}
		for (int i=n-1; i>0; i--) {
			tree[i] = min(tree[i<<1], tree[i<<1|1]);
		}
	}

	void apply(int p, int val) {
		tree[p].first += val;
		if (p<n) lazy[p] += val;
	} 

	void build(int p) {
		while (p>1) {
			p>>=1;
			tree[p].first = min(tree[p<<1].first, tree[p<<1|1].first) + lazy[p];
		}
	}

	void push(int p) {
		for (int i=h+1; i>0; i--) {
			int j = p>>i;
			if (lazy[j] != 0) {
				apply(j<<1, lazy[j]);
				apply(j<<1|1, lazy[j]);
				lazy[j] = 0;
			}
		}
	}

	void increm(int l, int r, int val) {
		l+=n;
		r+=n;
		int l0 = l;
		int r0 = r;
		for (; l<r; l>>=1, r>>=1) {
			if (l&1) apply(l++, val);
			if (r&1) apply(--r, val);
		}
		build(l0);
		build(r0-1);
	}

	pair<int, int> query(int l, int r) {
		l+=n;
		r+=n;
		push(l);
		push(r-1);
		pair<int,int> res = {2e9, -1};
		for (; l<r; l>>=1, r>>=1) {
			if (l&1) res = min(res, tree[l++]);
			if (r&1) res = min(res, tree[--r]);
		}
		return res;
	}

} seg;

void init(int k, vector<int> r) {
	n = r.size();

	for (int i=0; i<n; i++) myr[i] = r[i];

	//if (n==4) for (int i=0; i<4; i++) cerr << seg.tree[4+i].first << endl;

	seg.make();

	for (int m=0; m<n; m++) {
	

		pair<int, int> first = seg.query(0, n);
		int ind = first.second;
		if (ind<k-1) {
			pair<int, int> sec = seg.query(n-k+ind+1, n);
			if (sec.first==0) {
				ind = sec.second;
			} 
		}

		//at this point we have found the correct index ind;
		ans[ind] = n-m;
		if (ind >= k-1) {
			seg.increm(ind-k+1, ind, -1);
		} else {
			seg.increm(0, ind, -1);
			seg.increm(n-k+ind+1, n, -1);
		}
		seg.increm(ind, ind+1, n);//this is safe;
		if (m==3){
			for (int j=0; j<4; j++) cerr << seg.query(j,j+1).first << " ";
			cout << endl;
		} 
		
		//if (n==3) for (int i=1; i<8; i++) cerr << seg.tree[i].first << " ";
		//cout << endl;
		//if (n==3) cerr << seg.query(3,4).first << endl;


	}
}

int compare_plants(int x, int y) {
	//return 1 if h[x] > h[y]
	//return -1 if h[y] < h[x];
	//else return 0;

	if (ans[x] > ans[y]) {
		return 1;
	} else return -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