oj.uz

Submission #823255

# Submission time Handle Problem Language Result Execution time Memory
823255 2023-08-12T10:06:01 Z fatemetmhr Comparing Plants (IOI20_plants) C++17
44 / 100
 688 ms 45528 KB 
// vaghan ide i nadaram chi benevisam dige :/


#include "plants.h"
#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define fi     first
#define se     second
#define mp     make_pair
#define pb     push_back

typedef long long ll;

const int maxn5 = 2e5 + 10;
const int maxnt = 1e6 + 10;
const int mod   = 1e9 + 10;

int n, ind[maxn5];
vector <int> av;

struct seg{

	ll lazy[maxnt];
	pair <ll, int> mn[maxnt];

	void upd(int l, int r, int id, int val, int v){
		if(r - l == 1){
			lazy[v] = 0;
			mn[v] = {val, l};
			return;
		}
		int mid = (l + r) >> 1;
		if(id < mid)
			upd(l, mid, id, val, v * 2);
		else
			upd(mid, r, id, val, v * 2 + 1);
		mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
		mn[v].fi += lazy[v];
	}

	void add(int l, int r, int lq, int rq, int val, int v){
		if(rq <= l || r <= lq)
			return;
		if(lq <= l && r <= rq){
			lazy[v] += val;
			mn[v].fi += val;
			return;
		}
		int mid = (l + r) >> 1;
		add(l, mid, lq, rq, val, v * 2);
		add(mid, r, lq, rq, val, v * 2 + 1);
		mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
		mn[v].fi += lazy[v];
	}
} seg1, seg2;

void init(int k, vector<int> r) {
	n = r.size();
	for(int i = 0; i < n; i++){
		seg1.upd(0, n, i, r[i], 1);
		seg2.upd(0, n, i, r[i], 1);
	}
	bool con = true;
	while(con){
		con = false;
		while(seg1.mn[1].fi == 0){
			con = true;
			int v = seg1.mn[1].se;
			//cout << "ok seg1 " << v << endl;
			seg1.upd(0, n, v, mod / 2, 1);
			if(v < n - 1)
				seg2.add(0, n, v + 1, min(n, v + k), 1, 1);
			if(v + k > n)
				seg2.add(0, n, 0, v + k - n, 1, 1);
		}
		if(seg2.mn[1].fi == 0){
			con = true;
			int v = seg2.mn[1].se;
			//cout << "ok seg2 " << v << ' ' << k << ' ' << (v - (k - 1)) << endl;
			av.pb(v);
			seg2.upd(0, n, v, mod / 2, 1);
			if(v < n - 1)
				seg2.add(0, n, v + 1, min(n, v + k), -1, 1);
			if(v + k > n)
				seg2.add(0, n, 0, v + k - n, -1, 1);
			if(v){
				seg1.add(0, n, max(0, v - (k - 1)), v, -1, 1);
				seg2.add(0, n, max(0, v - (k - 1)), v, -1, 1);
			}
			if(v - (k - 1) < 0){
				seg1.add(0, n, v - (k - 1) + n, n, -1, 1);
				seg2.add(0, n, v - (k - 1) + n, n, -1, 1);
			}
		}

	}
	//cout << av.size() << endl;
	reverse(all(av));
	for(int i = 0; i < n; i++)
		ind[av[i]] = i;
	return;
}

int compare_plants(int x, int y) {
	return (ind[x] < ind[y] ? -1 : 1);
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 31572 KB Output is correct
2 Correct 11 ms 31572 KB Output is correct
3 Correct 10 ms 31608 KB Output is correct
4 Incorrect 10 ms 31616 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 31528 KB Output is correct
2 Correct 10 ms 31600 KB Output is correct
3 Correct 10 ms 31572 KB Output is correct
4 Correct 10 ms 31524 KB Output is correct
5 Correct 10 ms 31572 KB Output is correct
6 Correct 13 ms 31736 KB Output is correct
7 Correct 58 ms 34764 KB Output is correct
8 Correct 13 ms 31668 KB Output is correct
9 Correct 14 ms 31700 KB Output is correct
10 Correct 62 ms 34764 KB Output is correct
11 Correct 64 ms 34640 KB Output is correct
12 Correct 55 ms 34924 KB Output is correct
13 Correct 59 ms 34756 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 31528 KB Output is correct
2 Correct 10 ms 31600 KB Output is correct
3 Correct 10 ms 31572 KB Output is correct
4 Correct 10 ms 31524 KB Output is correct
5 Correct 10 ms 31572 KB Output is correct
6 Correct 13 ms 31736 KB Output is correct
7 Correct 58 ms 34764 KB Output is correct
8 Correct 13 ms 31668 KB Output is correct
9 Correct 14 ms 31700 KB Output is correct
10 Correct 62 ms 34764 KB Output is correct
11 Correct 64 ms 34640 KB Output is correct
12 Correct 55 ms 34924 KB Output is correct
13 Correct 59 ms 34756 KB Output is correct
14 Correct 93 ms 35776 KB Output is correct
15 Correct 682 ms 45360 KB Output is correct
16 Correct 92 ms 35844 KB Output is correct
17 Correct 688 ms 45372 KB Output is correct
18 Correct 357 ms 45396 KB Output is correct
19 Correct 349 ms 45352 KB Output is correct
20 Correct 581 ms 45468 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 31572 KB Output is correct
2 Correct 10 ms 31572 KB Output is correct
3 Correct 50 ms 34512 KB Output is correct
4 Correct 305 ms 44976 KB Output is correct
5 Correct 394 ms 45528 KB Output is correct
6 Correct 540 ms 45380 KB Output is correct
7 Correct 628 ms 45376 KB Output is correct
8 Correct 675 ms 45376 KB Output is correct
9 Correct 356 ms 45316 KB Output is correct
10 Correct 343 ms 45308 KB Output is correct
11 Correct 257 ms 43340 KB Output is correct
12 Correct 286 ms 45360 KB Output is correct
13 Correct 360 ms 45348 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 31572 KB Output is correct
2 Correct 10 ms 31556 KB Output is correct
3 Incorrect 10 ms 31572 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 31568 KB Output is correct
2 Correct 10 ms 31572 KB Output is correct
3 Incorrect 11 ms 31560 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 31572 KB Output is correct
2 Correct 11 ms 31572 KB Output is correct
3 Correct 10 ms 31608 KB Output is correct
4 Incorrect 10 ms 31616 KB Output isn't correct
5 Halted 0 ms 0 KB -