Submission #1142841

#	Time	Username	Problem	Language	Result	Execution time	Memory
1142841		PagodePaiva	Comparing Plants (IOI20_plants)	C++20	0 / 100	33 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 tam;
int res[N];
int n;

void erase(int pos){
	seg.update(1,pos, pos, 1, n, -inf);
	int r = pos;
	int l = pos-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);
	}
}

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;
	}
	n = r.size();
	seg.build(1,1, n);
	tam = r.size();
	while(tam > 0){
		vector <int> maximos;
		pair <int, int> st = seg.query(1, 1, n, 1, n);
		maximos.push_back(st.second);
		while(true){
			pair <int, int> nx = seg.query(1, maximos.back()+1, n, 1, n);
			if(nx.first != st.first) break;
			maximos.push_back(nx.second);
		}
		reverse(maximos.begin(), maximos.end());
		set <int> s;
		for(auto x : maximos) s.insert(x);
		int best;
		for(auto x : maximos){
			best = x;
			int l = max(1, x-k+1);
			auto it = s.lower_bound(l);
			int t = *it;
			if(t == x) break;
		}
		for(auto x : maximos){
			//cout << x << ' ';
			if(x >= best){
				res[x] = tam;
				tam--;
				erase(x);
			}
		}
		for(auto x : maximos){
			if(x < best){
				res[x] = tam;
				tam--;
				erase(x);
			}
		}
	}
	/*vector <int> debug;
	for(int i = 1;i <= n;i++){
		debug.push_back(res[i]);
	}
	d(debug);*/
	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