Submission #624961

#	Time	Username	Problem	Language	Result	Execution time	Memory
624961		Tigryonochekk	Comparing Plants (IOI20_plants)	C++17	0 / 100	45 ms	3140 KiB

plants

#include <iostream>
#include "plants.h"
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
#define cum cout << "cum\n";
#define pii pair<int, int>
const int N = 2e5 + 2;

int n;
int k;
vector<int> r;

pii t[4 * N];
int d[4 * N];
vector<int> srt;
int rs[N];

void push(int v, int tl, int tr) {
	t[v].first += d[v];
	if (tl != tr) {
		d[2 * v] += d[v];
		d[2 * v + 1] += d[v];
	}
	d[v] = 0;
}

void build(int v, int tl, int tr) {
	push(v, tl, tr);
	if (tl == tr) {
		t[v] = pii(r[tl], tl);
		return;
	}
	int tm = (tl + tr) / 2;
	build(2 * v, tl, tm);
	build(2 * v + 1, tm + 1, tr);
	t[v] = min(t[2 * v], t[2 * v + 1]);
}

pii query(int v, int tl, int tr, int l, int r) {
	push(v, tl, tr);
	if (tl == l && tr == r) {
		return t[v];
	}
	int tm = (tl + tr) / 2;
	if (r <= tm) {
		return query(2 * v, tl, tm, l, r);
	}
	else if (l > tm) {
		return query(2 * v + 1, tm + 1, tr, l, r);
	}
	else {
		return min(query(2 * v, tl, tm, l, tm),
			query(2 * v + 1, tm + 1, tr, tm + 1, r));
	}
}

void update(int v, int tl, int tr, int l, int r, int x) {
	push(v, tl, tr);
	if (tl == l && tr == r) {
		d[v] += x;
		push(v, tl, tr);
		return;
	}
	int tm = (tl + tr) / 2;
	if (r <= tm) {
		update(2 * v, tl, tm, l, r, x);
	}
	else if (l > tm) {
		update(2 * v + 1, tm + 1, tr, l, r, x);
	}
	else {
		update(2 * v, tl, tm, l, tm, x);
		update(2 * v + 1, tm + 1, tr, tm + 1, r, x);
	}
	t[v] = min(t[2 * v], t[2 * v + 1]);
}

void init(int krip, vector<int> rab) {
	k = krip;
	r.push_back(-1);
	for (int x : rab)
		r.push_back(x);
	n = r.size() - 1;
	build(1, 1, n);
	//cout << t[1].first << " " << t[1].second << endl;
	for (int i = 0; i < n; i++) {
		int mn = t[1].first, mni = t[1].second;
		if (n - (k - i - 1) <= n) { // inq@ misht amenaarajin minimaln a veradardznum, aysinqn iraninc dzax petq chi nayel
			pii cur = query(1, 1, n, n - (k - i - 1), n);
			if (cur.first == mn) {
				mn = cur.first;
				mni = cur.second;
			}
		}
		srt.push_back(mni);
		if (mni - k + 1 >= 1) {
			update(1, 1, n, mni - k + 1, mni - 1, -1);
		}
		else {
			if (mni - 1 >= 1) {
				update(1, 1, n, 1, mni - 1, -1);
			}
			if (n - (k - mni) + 1 <= n) {
				update(1, 1, n, n - (k - mni) + 1, n, -1);
			}
		}
		update(1, 1, n, mni, mni, N);
	}
	reverse(srt.begin(), srt.end());
	for (int i = 0; i < srt.size(); i++) {
		rs[srt[i]] = i;
		//cout << srt[i] << " ";;
	}
	return;
}

int compare_plants(int x, int y) {
	x++;
	y++;
	if (rs[x] < rs[y])
		return -1;
	else
		return 1;
	
}
/*
4 3 2 
0 1 1 2 
0 2 
1 2 


4 2 2 
0 1 0 1 
0 3 
1 3 
*/

Compilation message (stderr)

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:112:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |  for (int i = 0; i < srt.size(); i++) {
      |                  ~~^~~~~~~~~~~~

• 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