Submission #1179113

#	Time	Username	Problem	Language	Result	Execution time	Memory
1179113		Pacybwoah	Comparing Plants (IOI20_plants)	C++20	49 / 100	295 ms	27720 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, fsd = inf, scd = inf, conf = -1;
		node(int a, int b, int d, int e){
			val = a, tag = b, fs = d, sc = e;
		}
	};
	int n, k;
	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;
				if(a.conf > -1 || b.conf > -1){
					res.conf = max(a.conf, b.conf);
				}
				else{
					if(a.scd >= k && a.fs < a.sc){
						res.conf = a.sc;
					}
					else if(b.fs - a.sc >= k && b.fs < b.sc){
						res.conf = b.fs;
					}
				}
				if(a.fs == a.sc) res.fsd = b.fs - a.fs;
				else res.fsd = a.fsd;
				if(b.fs == b.sc) res.scd = b.sc - a.sc;
				else res.scd = b.scd;
			}
			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, pre;
}

void init(int K, std::vector<int> r) {
	k = K;
	n = (int)r.size();
	pos.resize(n + 1);
	pre.resize(n + 1);
	for(int i = 1; i <= n; i++) pre[i] = pre[i - 1] + r[i - 1];
	st seg(r);
	for(int times = 1; times <= n; times++){
		int now = -1;
		if(seg.seg[1].conf > 0) now = seg.seg[1].conf;
		else{
			if(seg.seg[1].scd >= k) now = seg.seg[1].sc;
			else if(seg.seg[1].fs + n - seg.seg[1].sc >= k) now = seg.seg[1].fs;
		}
		//cout << now << endl;
		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(k == 2){
		int res = pre[y - 1] - pre[x - 1];
		//cout << res << "pus" << endl;
		if(res == 0) return 1;
		if(res == y - x) return -1;
		res = pre[x - 1] + pre[n] - pre[y - 1];
		//cout << res << "pus" << endl;
		if(res == 0) return -1;
		if(res == n - (y - x)) return 1;
		return 0;
	}
	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: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25