oj.uz

Submission #303634

# Submission time Handle Problem Language Result Execution time Memory
303634 2020-09-20T13:41:58 Z myungwoo Comparing Plants (IOI20_plants) C++17
5 / 100
 744 ms 17400 KB 
#include <bits/stdc++.h>
#include "plants.h"
using namespace std;

#define MAXN 200005

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

struct SegTree{
	template <typename T>
	struct Value{
		T value, lazysum;
	};
	Value<int> tree[TS];
	void build(int arr[]){
		for (int i=ST+1;i<TS;i++) tree[i].value = i-ST <= N+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);
		return findzero(n*2+1);
	}
} segtree;

void get(int perm[])
{
	segtree.build(R);
	stack <int> wait;
	for (int ord=1;ord<=N+N;ord++){
		int x = segtree.findzero(1);
		while (!x){
			int q = wait.top(); wait.pop();
			segtree.update(1, 1, TS/2, q, N+N, -1);
			x = segtree.findzero(1);
		}
		perm[x] = ord;
		segtree.update(1, 1, TS/2, x, x, 1e9);
		segtree.update(1, 1, TS/2, max(1, x-K+1), x-1, -1);
		if (x-K+1 < 1) wait.push(N+N-(1-(x-K+1))+1);
	}
}

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

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

Compilation message

plants.cpp: In member function 'void SegTree::update(int, int, int, int, int, const int&)':
plants.cpp:35:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |   int m = s+e >> 1;
      |           ~^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8576 KB Output is correct
2 Correct 7 ms 8576 KB Output is correct
3 Correct 7 ms 8576 KB Output is correct
4 Correct 7 ms 8576 KB Output is correct
5 Correct 8 ms 8576 KB Output is correct
6 Correct 73 ms 11428 KB Output is correct
7 Correct 147 ms 12024 KB Output is correct
8 Correct 733 ms 17400 KB Output is correct
9 Correct 721 ms 17400 KB Output is correct
10 Correct 736 ms 17144 KB Output is correct
11 Correct 744 ms 17400 KB Output is correct
12 Correct 742 ms 17400 KB Output is correct
13 Correct 719 ms 17272 KB Output is correct
14 Correct 734 ms 17136 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8576 KB Output is correct
2 Correct 7 ms 8576 KB Output is correct
3 Correct 9 ms 8576 KB Output is correct
4 Runtime error 21 ms 17152 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8576 KB Output is correct
2 Correct 7 ms 8576 KB Output is correct
3 Correct 9 ms 8576 KB Output is correct
4 Runtime error 21 ms 17152 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8576 KB Output is correct
2 Runtime error 19 ms 17184 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8576 KB Output is correct
2 Correct 8 ms 8576 KB Output is correct
3 Correct 7 ms 8576 KB Output is correct
4 Correct 8 ms 8576 KB Output is correct
5 Runtime error 19 ms 17116 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8576 KB Output is correct
2 Correct 7 ms 8576 KB Output is correct
3 Correct 7 ms 8576 KB Output is correct
4 Runtime error 21 ms 17024 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 8576 KB Output is correct
2 Correct 7 ms 8576 KB Output is correct
3 Correct 7 ms 8576 KB Output is correct
4 Correct 7 ms 8576 KB Output is correct
5 Correct 8 ms 8576 KB Output is correct
6 Correct 73 ms 11428 KB Output is correct
7 Correct 147 ms 12024 KB Output is correct
8 Correct 733 ms 17400 KB Output is correct
9 Correct 721 ms 17400 KB Output is correct
10 Correct 736 ms 17144 KB Output is correct
11 Correct 744 ms 17400 KB Output is correct
12 Correct 742 ms 17400 KB Output is correct
13 Correct 719 ms 17272 KB Output is correct
14 Correct 734 ms 17136 KB Output is correct
15 Correct 9 ms 8576 KB Output is correct
16 Correct 7 ms 8576 KB Output is correct
17 Correct 9 ms 8576 KB Output is correct
18 Runtime error 21 ms 17152 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -