oj.uz

Submission #303981

# Submission time Handle Problem Language Result Execution time Memory
303981 2020-09-20T22:36:46 Z myungwoo Comparing Plants (IOI20_plants) C++17
44 / 100
 769 ms 20076 KB 
#include <bits/stdc++.h>
#include "plants.h"
using namespace std;

#define MAXN 200005
#define debug(...) fprintf(stderr, __VA_ARGS__); fflush(stderr);

const int TS = 1<<19, ST = TS/2-1;
int N, K, R[MAXN];
int A[MAXN], B[MAXN];

template <typename T>
struct SegTree{
	struct Value{
		T value, lazysum;
	};
	vector<Value> tree;
	SegTree(int arr[]){
		tree.resize(TS, {0, 0});
		for (int i=ST+1;i<TS;i++) tree[i].value = i-ST <= N ? arr[i-ST] : 1e9;
		for (int i=ST;i;i--) tree[i].value = min(tree[i*2].value, tree[i*2+1].value);
	}
	void propagate(int n){
		if (n <= ST){
			tree[n*2].value += tree[n].lazysum, tree[n*2+1].value += tree[n].lazysum;
			tree[n*2].lazysum += tree[n].lazysum, tree[n*2+1].lazysum += tree[n].lazysum;
		}
		tree[n].lazysum = 0;
	}
	void update(int n, int s, int e, int l, int r, const int &v){
		if (l > r || e < l || r < s) return;
		if (l <= s && e <= r){
			tree[n].value += v, tree[n].lazysum += v;
			return;
		}
		propagate(n);
		int m = s+e >> 1;
		update(n*2, s, m, l, r, v);
		update(n*2+1, m+1, e, l, r, v);
		tree[n].value = min(tree[n*2].value, tree[n*2+1].value);
	}
	int findzero(int n){
		if (tree[n].value != 0) return 0;
		propagate(n);
		if (n > ST) return n-ST;
		if (!tree[n*2].value) return findzero(n*2);
		else if (!tree[n*2+1].value) return findzero(n*2+1);
		else assert(0);
	}
};

struct ZeroContainer{
	set<int> pos, non_covered;
	set<int>::iterator left(set<int>::iterator it){
		auto ret = it;
		if (ret == pos.begin()) ret = pos.end();
		return --ret;
	}
	set<int>::iterator right(set<int>::iterator it){
		auto ret = it; ret++;
		if (ret == pos.end()) return pos.begin();
		return ret;
	}
	void insert(int p){
		auto it = pos.insert(p).first;
		auto l = left(it), r = right(it);
		if (l == it || (*it-*l+N)%N >= K) non_covered.insert(p);
		if (r != it && (*r-*it+N)%N < K) non_covered.erase(*r);
	}
	void remove(int p){
		auto it = pos.find(p);
		auto l = left(it), r = right(it);
		if (l != it && r != it && (l == r || (*r-*l+N)%N >= K)) non_covered.insert(*r);
		pos.erase(it);
	}
	int pop_smallest(){
		int ret = *non_covered.begin(); non_covered.erase(ret);
		remove(ret);
		return ret;
	}
};

void get(int pos[])
{
	SegTree<int> segtree(R);
	ZeroContainer zc;
	for (int ord=1;ord<=N;ord++){
		for (;;){
			int p = segtree.findzero(1);
			if (!p) break;
			zc.insert(p);
			segtree.update(1, 1, TS/2, p, p, 1e9);
		}
		int x = zc.pop_smallest();
		pos[x] = ord; // perm[ord] = x
		segtree.update(1, 1, TS/2, max(1, x-K+1), x-1, -1);
		if (x-K+1 < 1) segtree.update(1, 1, TS/2, N-(1-(x-K+1))+1, N, -1);
	}
}

void init(int K, vector<int> r)
{
	::K = K;
	N = r.size();
	for (int i=1;i<=N;i++) R[i] = r[i-1];
	get(A);
	for (int i=1;i<=N;i++) R[i] = K-R[i]-1;
	get(B);
}

int compare_plants(int x, int y)
{
	if (A[x+1] > A[y+1]) return -compare_plants(y, x);
	x++; y++;
	if ((A[x] < A[y]) != (B[x] < B[y])) return 1;
	return 0;
}

Compilation message

plants.cpp: In instantiation of 'void SegTree<T>::update(int, int, int, int, int, const int&) [with T = int]':
plants.cpp:92:40:   required from here
plants.cpp:37:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |   int m = s+e >> 1;
      |           ~^~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4480 KB Output is correct
2 Correct 6 ms 4480 KB Output is correct
3 Correct 6 ms 4480 KB Output is correct
4 Incorrect 6 ms 4480 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 7 ms 4480 KB Output is correct
2 Correct 6 ms 4480 KB Output is correct
3 Correct 6 ms 4480 KB Output is correct
4 Correct 6 ms 4480 KB Output is correct
5 Correct 9 ms 4480 KB Output is correct
6 Correct 12 ms 4604 KB Output is correct
7 Correct 91 ms 7408 KB Output is correct
8 Correct 8 ms 4480 KB Output is correct
9 Correct 10 ms 4480 KB Output is correct
10 Correct 94 ms 7516 KB Output is correct
11 Correct 88 ms 7284 KB Output is correct
12 Correct 88 ms 7660 KB Output is correct
13 Correct 92 ms 7404 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4480 KB Output is correct
2 Correct 6 ms 4480 KB Output is correct
3 Correct 6 ms 4480 KB Output is correct
4 Correct 6 ms 4480 KB Output is correct
5 Correct 9 ms 4480 KB Output is correct
6 Correct 12 ms 4604 KB Output is correct
7 Correct 91 ms 7408 KB Output is correct
8 Correct 8 ms 4480 KB Output is correct
9 Correct 10 ms 4480 KB Output is correct
10 Correct 94 ms 7516 KB Output is correct
11 Correct 88 ms 7284 KB Output is correct
12 Correct 88 ms 7660 KB Output is correct
13 Correct 92 ms 7404 KB Output is correct
14 Correct 141 ms 7660 KB Output is correct
15 Correct 769 ms 10860 KB Output is correct
16 Correct 136 ms 7660 KB Output is correct
17 Correct 748 ms 10988 KB Output is correct
18 Correct 620 ms 14584 KB Output is correct
19 Correct 622 ms 15340 KB Output is correct
20 Correct 735 ms 10740 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4480 KB Output is correct
2 Correct 6 ms 4480 KB Output is correct
3 Correct 83 ms 7404 KB Output is correct
4 Correct 512 ms 13804 KB Output is correct
5 Correct 552 ms 11372 KB Output is correct
6 Correct 650 ms 10868 KB Output is correct
7 Correct 721 ms 10760 KB Output is correct
8 Correct 734 ms 10860 KB Output is correct
9 Correct 524 ms 12280 KB Output is correct
10 Correct 566 ms 11808 KB Output is correct
11 Correct 499 ms 19448 KB Output is correct
12 Correct 528 ms 20076 KB Output is correct
13 Correct 591 ms 16504 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4508 KB Output is correct
2 Correct 6 ms 4660 KB Output is correct
3 Incorrect 6 ms 4480 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4480 KB Output is correct
2 Correct 6 ms 4480 KB Output is correct
3 Correct 6 ms 4480 KB Output is correct
4 Incorrect 6 ms 4480 KB Output isn't correct
5 Halted 0 ms 0 KB -