oj.uz

Submission #823327

# Submission time Handle Problem Language Result Execution time Memory
823327 2023-08-12T10:45:32 Z fatemetmhr Comparing Plants (IOI20_plants) C++17
15 / 100
 869 ms 67528 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 maxn3 = 310;
const int mod   = 1e9 + 10;

int n, ind[maxn5];
vector <int> av, adj[maxn5], jda[maxn5];
bool mark[maxn5], mark1[maxn5], mark2[maxn5];
set <pair<int, int>> q;
set <int> ver;

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++){
		ver.insert(i);
		ind[av[i]] = i;
		//cout << av[i] << ' ';
	}
	//cout << endl;
	q.insert({-ind[0], 0});
	int pt = n - 1;
	while(q.size()){
		int v = q.begin()->se;
		mark[v] = true;
		q.erase(q.begin());
		//cout << "ok " << v << endl;
		while(pt >= ind[v]){
			ver.erase(av[pt]);
			pt--;
		}
		for(auto it = ver.lower_bound(v); it != ver.end() && ((*it) - v + n) % n < k;){
			auto itt = it;
			it++;
			q.insert({-ind[*itt], *itt});
			ver.erase(itt);
		}
		for(auto it = ver.begin(); it != ver.end() && ((*it) - v + n) % n < k;){
			auto itt = it;
			it++;
			q.insert({-ind[*itt], *itt});
			ver.erase(itt);
		}
		if(v - k + 1 < 0){
			for(auto it = ver.lower_bound(v - k + 1 + n); it != ver.end() && (v - (*it) + n) % n < k;){
				auto itt = it;
				it++;
				//cout << "here is " << (*itt) << endl;
				q.insert({-ind[*itt], *itt});
				ver.erase(itt);
			}
		}
		else{
			for(auto it = ver.lower_bound(v - k + 1); it != ver.end() && (v - (*it) + n) % n < k;){
				auto itt = it;
				it++;
				q.insert({-ind[*itt], *itt});
				ver.erase(itt);
			}
		}
		for(auto it = ver.begin(); it != ver.end() && (v - (*it) + n) % n < k;){
			auto itt = it;
			it++;
			q.insert({-ind[*itt], *itt});
			ver.erase(itt);
		}
	}
	for(int i = 0; i < n; i++)
		mark1[i] = mark[i];
	ver.clear();
	q.clear();
	for(int i = 0; i < n; i++)
		ver.insert(i);
	pt = 0;
	q.insert({ind[0], 0});
	memset(mark, false, sizeof mark);
	while(q.size()){
		int v = q.begin()->se;
		mark[v] = true;
		q.erase(q.begin());
		while(pt <= ind[v]){
			ver.erase(av[pt]);
			pt++;
		}
		for(auto it = ver.lower_bound(v); it != ver.end() && ((*it) - v + n) % n < k;){
			auto itt = it;
			it++;
			q.insert({ind[*itt], *itt});
			ver.erase(itt);
		}
		for(auto it = ver.begin(); it != ver.end() && ((*it) - v + n) % n < k;){
			auto itt = it;
			it++;
			q.insert({ind[*itt], *itt});
			ver.erase(itt);
		}
		if(v - k + 1 < 0){
			for(auto it = ver.lower_bound(v - k + 1 + n); it != ver.end() && (v - (*it) + n) % n < k;){
				auto itt = it;
				it++;
				//cout << "here is " << (*itt) << endl;
				q.insert({ind[*itt], *itt});
				ver.erase(itt);
			}
		}
		else{
			for(auto it = ver.lower_bound(v - k + 1); it != ver.end() && (v - (*it) + n) % n < k;){
				auto itt = it;
				it++;
				q.insert({ind[*itt], *itt});
				ver.erase(itt);
			}
		}
		for(auto it = ver.begin(); it != ver.end() && (v - (*it) + n) % n < k;){
			auto itt = it;
			it++;
			q.insert({ind[*itt], *itt});
			ver.erase(itt);
		}
	}
	for(int i = 0; i < n; i++)
		mark2[i] = mark[i];
	return;
}

int compare_plants(int x, int y) {
	if(mark1[y])
		return 1;
	if(mark2[y])
		return -1;
	return 0;

}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 41172 KB Output is correct
2 Correct 15 ms 41112 KB Output is correct
3 Incorrect 15 ms 41140 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 41172 KB Output is correct
2 Correct 14 ms 41164 KB Output is correct
3 Incorrect 14 ms 41180 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 41172 KB Output is correct
2 Correct 14 ms 41164 KB Output is correct
3 Incorrect 14 ms 41180 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 41240 KB Output is correct
2 Correct 14 ms 41228 KB Output is correct
3 Incorrect 15 ms 41176 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 41172 KB Output is correct
2 Correct 14 ms 41196 KB Output is correct
3 Correct 14 ms 41196 KB Output is correct
4 Correct 14 ms 41160 KB Output is correct
5 Correct 17 ms 41236 KB Output is correct
6 Correct 506 ms 64552 KB Output is correct
7 Correct 691 ms 64696 KB Output is correct
8 Correct 780 ms 67248 KB Output is correct
9 Correct 869 ms 67528 KB Output is correct
10 Correct 423 ms 66724 KB Output is correct
11 Correct 590 ms 67400 KB Output is correct
12 Correct 395 ms 66232 KB Output is correct
13 Correct 511 ms 66824 KB Output is correct
14 Correct 704 ms 67044 KB Output is correct
15 Correct 814 ms 67276 KB Output is correct
16 Correct 443 ms 66480 KB Output is correct
17 Correct 469 ms 66896 KB Output is correct

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 41172 KB Output is correct
2 Correct 15 ms 41112 KB Output is correct
3 Incorrect 15 ms 41140 KB Output isn't correct
4 Halted 0 ms 0 KB -