제출 #1145353

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1145353		PagodePaiva	Comparing Plants (IOI20_plants)	C++20	27 / 100	326 ms	10024 KiB

plants

#include<bits/stdc++.h>
#include "plants.h"

using namespace std;

const int N = 200010;
int v[N];
int n;
int ans[N];

struct Segtree{
	int tree[4*N], lazy[4*N];
	int join(int a, int b){
		return min(a, b);
	}
	void build(int node, int l, int r){
		lazy[node] = 0;
		if(l == r){
			tree[node] = v[l];
			return;
		}
		int mid = (l+r)/2;
		build(2*node, l, mid);
		build(2*node+1, mid+1, r);
		tree[node] = join(tree[2*node], tree[2*node+1]);
		return;
	}
	void unlazy(int node, int l, int r){
		tree[node] += lazy[node];
		if(l != r){
			lazy[2*node] += lazy[node];
			lazy[2*node+1] += lazy[node];
		}
		lazy[node] = 0;
	}
	void update(int node, int l, int r, int tl, int tr, int val){
		unlazy(node, tl, tr);
		if(l > tr or tl > r) return;
		if(l <= tl and tr <= r){
			lazy[node] += val;
			unlazy(node, tl, tr);
			return;
		}
		int mid = (tl+tr)/2;
		update(2*node, l, r, tl, mid, val);
		update(2*node+1, l, r, mid+1, tr, val);
		tree[node] = join(tree[2*node], tree[2*node+1]);
		return;
	}
	int query(int node, int l, int r, int tl, int tr){
		unlazy(node, tl, tr);
		if(l > tr or tl > r) return 1e8;
		if(l <= tl and tr <= r) return tree[node];
		int mid = (tl+tr)/2;
		return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
	}
	int busca(int node, int l, int r, int tl, int tr, int val){
		unlazy(node, tl, tr);
		if(l > tr or tl > r) return 1e8;
		if(l <= tl and tr <= r){
			if(tree[node] > val) return 1e8;
			if(tl == tr) return tl;
			int mid = (tl+tr)/2;
			unlazy(2*node, tl, mid);
			unlazy(2*node+1, mid+1, tr);
			if(tree[2*node] <= val) return busca(2*node, l, r, tl, mid, val);
			else return busca(2*node+1, l, r, mid+1, tr, val);
		}
		int mid = (tl+tr)/2;
		int d = busca(2*node, l, r, tl, mid, val);
		if(d != 1e8) return d;
		return busca(2*node+1, l, r, mid+1, tr, val);
	}
} seg;

bool incluso(int x, int l, int r){
	if(l <= r){
		if(l <= x and x <= r) return true;
		return false;
	}
	else{
		if(l <= x and x <= n-1) return true;
		if(0 <= x and x <= r) return true;
		return false;
	}
}

void init(int k, std::vector<int> r) {
	n = r.size();
	for(int i = 0; i < r.size();i++){
		v[i] = r[i];
	}
	seg.build(1, 0, n-1);
	for(int tt = 0;tt < n;tt++){
		int pos = seg.busca(1, 0, n-1, 0, n-1, 0);
		int l = ((pos-(k-1))%n+n)%n, r = pos;
		bool aux = true;
		if(l <= r){
			if(seg.query(1, l, r, 0, n-1) == 0) aux = false;
		}
		else{
			if(seg.query(1, l, n-1, 0, n-1) == 0 or seg.query(1, 0, r, 0, n-1) == 0) aux = false;
		}
		if(!aux){
			if(l <= r){
				pos = seg.busca(1, l, r, 0, n-1, 0);
			}
			else{
				pos = seg.busca(1, l, n-1, 0, n-1, 0);
				if(pos == 1e8) pos = seg.busca(1, 0, r, 0, n-1, 0);
			}		
			l = ((pos-(k-1))%n+n)%n, r = pos;
		}
		seg.update(1, pos, pos, 0, n-1, 1e8);
		if(l <= r){
			seg.update(1, l, r, 0, n-1, -1);
		}
		else{
			seg.update(1, l, n-1, 0, n-1, -1);
			seg.update(1, 0, r, 0, n-1, -1);
		}	
		ans[pos] = n-tt;
	}
	return;
}

int compare_plants(int x, int y) {
	if(ans[x] > ans[y]) return 1;
	return -1;
	return 0;
}

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