oj.uz

Submission #303979

# Submission time Handle Problem Language Result Execution time Memory
303979 2020-09-20T22:31:46 Z myungwoo Comparing Plants (IOI20_plants) C++17
44 / 100
 1652 ms 21448 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++) debug("%d ", A[i]); debug("\n");
	for (int i=1;i<=N;i++) R[i] = K-R[i]-1;
	get(B);
	for (int i=1;i<=N;i++) debug("%d ", B[i]); debug("\n");
}

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

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:6:20: warning: macro expands to multiple statements [-Wmultistatement-macros]
    6 | #define debug(...) fprintf(stderr, __VA_ARGS__); fflush(stderr);
      |                    ^~~~~~~
plants.cpp:107:25: note: in expansion of macro 'debug'
  107 |  for (int i=1;i<=N;i++) debug("%d ", A[i]); debug("\n");
      |                         ^~~~~
plants.cpp:107:2: note: some parts of macro expansion are not guarded by this 'for' clause
  107 |  for (int i=1;i<=N;i++) debug("%d ", A[i]); debug("\n");
      |  ^~~
plants.cpp:6:20: warning: macro expands to multiple statements [-Wmultistatement-macros]
    6 | #define debug(...) fprintf(stderr, __VA_ARGS__); fflush(stderr);
      |                    ^~~~~~~
plants.cpp:110:25: note: in expansion of macro 'debug'
  110 |  for (int i=1;i<=N;i++) debug("%d ", B[i]); debug("\n");
      |                         ^~~~~
plants.cpp:110:2: note: some parts of macro expansion are not guarded by this 'for' clause
  110 |  for (int i=1;i<=N;i++) debug("%d ", B[i]); debug("\n");
      |  ^~~
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 8 ms 4612 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 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 Correct 7 ms 4620 KB Output is correct
5 Correct 7 ms 4480 KB Output is correct
6 Correct 15 ms 4604 KB Output is correct
7 Correct 118 ms 7532 KB Output is correct
8 Correct 9 ms 4480 KB Output is correct
9 Correct 15 ms 4604 KB Output is correct
10 Correct 113 ms 7404 KB Output is correct
11 Correct 109 ms 7404 KB Output is correct
12 Correct 109 ms 7660 KB Output is correct
13 Correct 112 ms 7404 KB Output is correct

Subtask #3
13.0 / 13.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 Correct 7 ms 4620 KB Output is correct
5 Correct 7 ms 4480 KB Output is correct
6 Correct 15 ms 4604 KB Output is correct
7 Correct 118 ms 7532 KB Output is correct
8 Correct 9 ms 4480 KB Output is correct
9 Correct 15 ms 4604 KB Output is correct
10 Correct 113 ms 7404 KB Output is correct
11 Correct 109 ms 7404 KB Output is correct
12 Correct 109 ms 7660 KB Output is correct
13 Correct 112 ms 7404 KB Output is correct
14 Correct 228 ms 8044 KB Output is correct
15 Correct 1647 ms 13456 KB Output is correct
16 Correct 228 ms 8080 KB Output is correct
17 Correct 1652 ms 13520 KB Output is correct
18 Correct 1505 ms 14584 KB Output is correct
19 Correct 1521 ms 16896 KB Output is correct
20 Correct 1633 ms 13676 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4604 KB Output is correct
2 Correct 8 ms 4508 KB Output is correct
3 Correct 90 ms 7532 KB Output is correct
4 Correct 1390 ms 16620 KB Output is correct
5 Correct 1440 ms 14140 KB Output is correct
6 Correct 1551 ms 13480 KB Output is correct
7 Correct 1599 ms 13548 KB Output is correct
8 Correct 1631 ms 13676 KB Output is correct
9 Correct 1440 ms 14032 KB Output is correct
10 Correct 1443 ms 14544 KB Output is correct
11 Correct 1375 ms 19448 KB Output is correct
12 Correct 1420 ms 21448 KB Output is correct
13 Correct 1481 ms 16508 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 7 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 7 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 #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4480 KB Output is correct
2 Correct 8 ms 4612 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 -