oj.uz

Submission #821667

# Submission time Handle Problem Language Result Execution time Memory
821667 2023-08-11T12:49:39 Z Abrar_Al_Samit Comparing Plants (IOI20_plants) C++17
0 / 100
 1 ms 312 KB 
#include <bits/stdc++.h>
#include "plants.h"
using namespace std;

const int nax = 2e5 + 2;
const int inf = 2e9;


int val[nax], n, k;
struct plant {
	int id;

	plant(int _id = 0) {
		id = _id;
	}

	bool operator<(plant b) const {
		if(id + k - 1 < n) {
			return b.id > id && b.id <= id + k - 1;
		} else {
			if(b.id < id) return (id + k - 1) % n >= b.id;
			else return b.id > id;
		}
	}
};

int stree[nax * 4], at[nax * 4], lztree[nax * 4], del;

void propagate(int v) {
	stree[v << 1] += lztree[v];
	stree[v << 1 | 1] += lztree[v];
	lztree[v << 1] += lztree[v];
	lztree[v << 1 | 1] += lztree[v];
	lztree[v] = 0;
}
void update(int L, int R, int l = 0, int r = n-1, int v = 1) {
	if(l >= L && r <= R) {
		lztree[v] += del;
		stree[v] += del;
		return;
	}
	if(l > R || r < L) return;
	propagate(v);

	int mid = (l + r) >> 1;
	update(L, R, l, mid, v << 1);
	update(L, R, mid+1, r, v << 1 | 1);

	stree[v] = min(stree[v << 1], stree[v << 1 | 1]);
	at[v] = (stree[v << 1] < stree[v << 1 | 1]) ? at[v << 1] : at[v << 1 | 1];
}
void upd(int L, int R) {
	if(L < 0) {
		update(0, R);
		L += n;
		update(L, n-1);
	} else {
		update(L, R);
	}
}
vector<int>R;
void build(int l = 0, int r = n-1, int v = 1) {
	if(l == r) {
		stree[v] = R[l];
		at[v] = l;
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, v << 1);
	build(mid+1, r, v << 1 | 1);
	at[v] = (stree[v << 1] < stree[v << 1 | 1]) ? at[v << 1] : at[v << 1 | 1];	
}

void init(int K, vector<int> r) {
	k = K;
	n = r.size();
	R = r;

	build();

	set<plant>cand;
	for(int tg=1; tg<=n; ++tg) {
		while(stree[1]==0) {
			int mat = at[1];
			cand.insert(plant(mat));

			del = inf;
			upd(mat, mat);
		}

		plant mx = *cand.begin();
		cand.erase(mx);

		val[mx.id] = tg;
		del = -1;
		upd(mx.id - k + 1, mx.id);
	}
}

int compare_plants(int x, int y) {
	if(val[x]>val[y]) return 1;
	return -1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -