제출 #827116

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
827116		tomruk	식물 비교 (IOI20_plants)	C++17	32 / 100	274 ms	22884 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
#define N 200005
using namespace std;
struct SegTree{
	vector<pair<int,int>> t;
	vector<int> lazy;
	int n;
	SegTree(int sz,vector<int> a){
		n = sz;
		t.assign(4*n,{0,0});
		lazy.assign(4*n,0);
		build(1,0,n-1,a);
	}
	void build(int v,int tl,int tr,vector<int> &a){
		if(tl == tr){
			t[v] = {a[tl],tl};
			return;
		}
		int tm = (tl + tr)/2;
		build(v*2,tl,tm,a);
		build(v*2 + 1,tm+1,tr,a);
		t[v] = t[v*2];
		if(t[v*2 + 1].first < t[v].first)
			t[v] = t[v*2+1];
	}
	void push(int v){
		t[v*2].first += lazy[v];
		lazy[v*2] += lazy[v];
		t[v*2 + 1].first += lazy[v];
		lazy[v*2 + 1] += lazy[v];
		lazy[v] = 0;
	}
	void upd(int v,int tl,int tr,int l,int r,int val){
		if(tr < l || r < tl)
			return;
		if(l <= tl && tr <= r){
			t[v].first += val;
			lazy[v] += val;
			return;
		}
		push(v);
		int tm = (tl + tr)/2;
		upd(v*2,tl,tm,l,r,val);
		upd(v * 2 + 1,tm+1,tr,l,r,val);
		t[v] = t[v*2];
		if(t[v*2 + 1].first < t[v].first)
			t[v] = t[v*2+1];
	}
	pair<int,int> get(int v,int tl,int tr,int l,int r){
		if(tr < l || r < tl)
			return {1e9,0};
		if(l <= tl && tr <= r){
			return t[v];
		}
		push(v);
		int tm = (tl + tr)/2;
		auto a = get(v*2,tl,tm,l,r);
		auto b = get(v*2+1,tm+1,tr,l,r);
		if(b.first < a.first)
			return b;
		return a;
	}
	void upd(int l,int r,int val){
		upd(1,0,n-1,l,r,val);
	}
	pair<int,int> get(int l,int r){
		return get(1,0,n-1,l,r);
	}
};
int k;
int a[N];
vector<int> adj[N];
int group[N];
bool ok[N];
int cnt = 1;
void dfs(int v){
	cout << v << endl;
	for(auto u:adj[v]){
		group[u] = group[v];
		dfs(u);
	}
	a[v] = cnt++;
}
int pre[N];
int n;
void init(int _k, vector<int> r) {
	k = _k;
	n  = r.size();
	if(k == 2){
		for(int i = 0;i<n;i++){
			pre[i] = r[i] + (i?pre[i-1]:0);
		}
		return;
	}
	SegTree t(n,r);
	vector<int> x;
	for(int i = n-1;i>=0;i--){
		auto p1 = t.get(0,n-1);
		auto p2 = t.get(p1.second + k,n-1);
		if(p2.first == 0)
			p1 = p2;
		assert(p1.first == 0);
		a[p1.second] = i;
		if(p1.second)
			t.upd(max(0,p1.second-k + 1),p1.second - 1,-1);
		if(p1.second - k + 1 < 0){
			t.upd(p1.second-k + 1 + n,n-1,-1);
		}
		t.upd(p1.second,p1.second,1e9);
		// for(int j = 0;j<=n-1;j++){
		// 	cout << t.get(j,j).first << ' ';
		// }
		// cout << endl;
		// cout << i << ' ' << p1.second << endl;
	}
	// for(int i = n-1;i>=0;){
	// 	vector<int> p;
	// 	for(int j = 0;j<n;j++){
	// 		if(t.get(j,j).first == 0)
	// 			p.push_back(j);
	// 	}
	// 	vector<int> tmp;
	// 	int maxi = -1e9;
	// 	for(auto u:p){
	// 		if(maxi + k - 1 < u)
	// 			tmp.push_back(u);
	// 		maxi = u;
	// 	}
	// 	int x = tmp.back() + k-1 - n;
	// 	p.clear();
	// 	for(auto u:tmp){
	// 		if(u <= x)
	// 			continue;
	// 		p.push_back(u);
	// 	}
	// 	assert(p.size());
	// 	for(auto u:p){
	// 		if(u)
	// 			t.upd(max(0,u-k + 1),u - 1,-1);
	// 		if(u - k + 1 < 0){
	// 			t.upd(u-k + 1 + n,n-1,-1);
	// 		}
	// 		t.upd(u,u,1e9);
	// 		a[u] = i;
	// 	}
	// 	i -= p.size();
	// }
}

int compare_plants(int x, int y) {
	if(k == 2){
		if(pre[y-1] - (x?pre[x-1]:0) == 0){
			return 1;
		}
		if(pre[y-1] - (x?pre[x-1]:0) == y-x){
			return -1;
		}
		if(pre[n-1] - (pre[y-1] - (x?pre[x-1]:0)) == 0){
			return -1;
		}
		if(pre[n-1] - (pre[y-1] - (x?pre[x-1]:0)) == n - (y-x)){
			return 1;
		}
		return 0;
	}
	if(a[x] > a[y])
		return 1;
	if(a[x] < a[y])
		return -1;
	return 0;
}

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