Submission #1179067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179067		Pacybwoah	Comparing Plants (IOI20_plants)	C++20	27 / 100	168 ms	17600 KiB

plants

#include "plants.h"
#include<iostream>
#include<vector>
#include<algorithm>
#include<cassert>
#include<utility>
using namespace std;
typedef long long ll;
namespace{
	const int inf = 1e9;
	struct node{
		int val, tag, fs, sc;
		node(int a, int b, int d, int e){
			val = a, tag = b, fs = d, sc = e;
		}
	};
	int n;
	struct st{
		vector<node> seg;
		node pull(node a, node b){
			node res(0, 0, 0, 0);
			if(a.val == b.val){
				res.val = a.val;
				res.fs = a.fs;
				res.sc = b.sc;
			}
			else if(a.val < b.val){
				res = a;
			}
			else{
				res = b;
			}
			res.tag = 0;
			/*cout << a.val << " " << a.tag << " " << a.fs << " " << a.sc << endl;
			cout << b.val << ' ' << b.tag << " " << b.fs << " " << b.sc << endl;
			cout << res.val << " " << res.tag << " " << res.fs << " " << res.sc << endl;
			cout << "done" << endl;*/
			return res;
		}
		void build(int l, int r, int ind, vector<int>& vec){
			if(l == r){
				seg[ind] = node(vec[l - 1], 0, l, l);
				return;
			}
			int mid = (l + r) >> 1;
			build(l, mid, ind * 2, vec);
			build(mid + 1, r, ind * 2 + 1, vec);
			seg[ind] = pull(seg[ind * 2], seg[ind * 2 + 1]);
		}
		st(vector<int>& vec){
			seg.resize(4 * n + 4, node(0, 0, 0, 0));
			build(1, n, 1, vec);
		}
		void push(int l, int r, int ind){
			if(l == r) return;
			seg[ind * 2].val += seg[ind].tag;
			seg[ind * 2 + 1].val += seg[ind].tag;
			seg[ind * 2].tag += seg[ind].tag;
			seg[ind * 2 + 1].tag += seg[ind].tag;
			seg[ind].tag = 0;
		}
		void modify(int l, int r, int start, int end, int num, int ind){
			if(r < start || end < l) return;
			//cout << l << " " << r << " " << num << " " << ind << endl;
			if(start <= l && r <= end){
				seg[ind].val += num;
				seg[ind].tag += num;
				return;
			}
			int mid = (l + r) >> 1;
			push(l, r, ind);
			modify(l, mid, start, end, num, ind * 2);
			modify(mid + 1, r, start, end, num, ind * 2 + 1);
			seg[ind] = pull(seg[ind * 2], seg[ind * 2 + 1]);
		}
	};
	vector<int> pos;
}

void init(int k, std::vector<int> r) {
	n = (int)r.size();
	pos.resize(n + 1);
	st seg(r);
	for(int times = 1; times <= n; times++){
		seg.push(1, n, 1);
		vector<int> poss;
		if(seg.seg[2].val == 0){
			poss.push_back(seg.seg[2].fs);
			if(seg.seg[2].fs < seg.seg[2].sc) poss.push_back(seg.seg[2].sc);
			//cout << seg.seg[2].val << " " << seg.seg[2].tag << " " << seg.seg[2].fs << " " << seg.seg[2].sc << endl;
		}
		if(seg.seg[3].val == 0){
			poss.push_back(seg.seg[3].fs);
			if(seg.seg[3].fs < seg.seg[3].sc) poss.push_back(seg.seg[3].sc);
		}
		//cout << seg.seg[3].val << " " << seg.seg[3].tag << " " << seg.seg[3].fs << " " << seg.seg[3].sc << endl;
		int now = -1, sz = (int)poss.size();
		for(int i = 0; i < sz; i++){
			int lst, cur;
			if(i == 0) lst = poss[sz - 1];
			else lst = poss[i - 1];
			cur = poss[i];
			if(lst >= cur) cur += n;
			if(cur - lst >= k){
				now = poss[i];
			}
		}
		assert(now != -1);
		//cout << now << endl;
		pos[now] = times; // 1 = max, n = min
		if(now < k){
			if(now > 1) seg.modify(1, n, 1, now - 1, -1, 1);
			seg.modify(1, n, n - k + now + 1, n, -1, 1);
		}
		else{
			seg.modify(1, n, now - k + 1, now - 1, -1, 1);
		}
		seg.modify(1, n, now, now, inf, 1);
	}
	return;
}

int compare_plants(int x, int y) {
	x++;
	y++;
	if(pos[x] < pos[y]) return 1;
	else return -1;
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run -g grader.cpp plants.cpp

• 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