제출 #1142838

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1142838		PagodePaiva	식물 비교 (IOI20_plants)	C++20	0 / 100	34 ms	9540 KiB

plants

#include<bits/stdc++.h>
#include "plants.h"
#define fr first
#define sc second

using namespace std;

const int N = 200010;
const int inf = 1e8;
int k;
int v[N];

struct Segtree{
	pair <int, int> tree[4*N];
	int lazy[4*N];
	void unlazy(int node, int l, int r){
		tree[node].first += lazy[node];
		if(l != r){
			lazy[2*node] += lazy[node];
			lazy[2*node+1] += lazy[node];
		}
		lazy[node] = 0;
		return;
	}
	pair <int, int> join(pair <int, int> a,pair <int, int> b){
		if(a.fr > b.fr) return a;
		if(a.fr < b.fr) return b;
		if(a.sc < b.sc) return a;
		return b;
	}
	void build(int node, int l, int r){
		if(l == r){
			tree[node] = {v[l], l};
			lazy[node] = 0;
			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 update(int node, int l, int r, int tl, int tr, int val){
		unlazy(node, tl, tr);
		if(l <= tl and tr <= r){
			lazy[node] += val;
			unlazy(node, tl, tr);
			return;
		}
		if(l > tr or tl > r) 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;
	}
	pair <int, int> query(int node, int l, int r, int tl, int tr){
		unlazy(node, tl, tr);
		if(l > tr or tl > r) return {-inf, 0};
		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));
	}
} seg;

int res[N];

void init(int K, std::vector<int> r){
	k = K;
	for(int i = 0;i < r.size();i++){
		v[i+1] = k-r[i]-1;
	}
	int n = r.size();
	seg.build(1,1, n);
	int tam = r.size();
	while(tam > 0){
		pair <int, int> big = seg.query(1, 1, n, 1, n);
		pair <int, int> big2 = seg.query(1, big.second+1, n, 1,n);
		if(big2.first < big.first){
			res[big.second] = tam;
			seg.update(1,big.second, big.second, 1, n, -inf);
			int r = big.second;
			int l = big.second-k+1;
			if(l > 0){
				seg.update(1, l, r, 1, n, 1);
			}
			else{
				seg.update(1, 1, r, 1, n, 1);
				l += n;
				seg.update(1, l, n, 1, n, 1);
			}
		}
		else{
			if(big.second <= big2.second and big2.second <= big.second+k-1){
				res[big.second] = tam;
				seg.update(1,big.second, big.second, 1, n, -inf);
				int r = big.second;
				int l = big.second-k+1;
				if(l > 0){
					seg.update(1, l, r, 1, n, 1);
				}
				else{
					seg.update(1, 1, r, 1, n, 1);
					l += n;
					seg.update(1, l, n, 1, n, 1);
				}
			}
			else{
				res[big2.second] = tam;
				seg.update(1,big2.second, big2.second, 1, n, -inf);
				int r = big2.second;
				int l = big2.second-k+1;
				if(l > 0){
					seg.update(1, l, r, 1, n, 1);
				}
				else{
					seg.update(1, 1, r, 1, n, 1);
					l += n;
					seg.update(1, l, n, 1, n, 1);
				}
			}
		}
		tam--;
	}
	return;
}

int compare_plants(int x, int y) {
	if(res[x+1] < res[y+1]) return -1;
	else return 1;
	return 0;
}

• 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