oj.uz

Submission #364355

# Submission time Handle Problem Language Result Execution time Memory
364355 2021-02-09T02:50:11 Z dennisstar Comparing Plants (IOI20_plants) C++17
44 / 100
 3388 ms 139292 KB 
#include "plants.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int N, K;

int st[1<<19], lz[1<<19];
void spr(int i, bool b) {
	st[i]+=lz[i];
	if (!b) for (auto &j:{i*2, i*2+1}) lz[j]+=lz[i];
	lz[i]=0;
}
void init(int i, int s, int e, vector<int> &r) {
	if (s==e) { st[i]=r[s]; return ; }
	int m=(s+e)/2;
	init(i*2, s, m, r);
	init(i*2+1, m+1, e, r);
	st[i]=max(st[i*2], st[i*2+1]);
}
void upd(int i, int s, int e, int l, int r, int v) {
	spr(i, s==e);
	if (e<l||r<s||r<l) return ;
	if (l<=s&&e<=r) {
		lz[i]=v;
		spr(i, s==e);
		return ;
	}
	int m=(s+e)/2;
	upd(i*2, s, m, l, r, v);
	upd(i*2+1, m+1, e, l, r, v);
	st[i]=max(st[i*2], st[i*2+1]);
}
int get(int i, int s, int e, int l, int r) {
	spr(i, s==e);
	if (st[i]!=K-1||e<l||r<s||r<l) return -1;
	if (s==e) return s;
	int m=(s+e)/2, v=get(i*2, s, m, l, r);
	return v!=-1?v:get(i*2+1, m+1, e, l, r);
}
int get(int l, int r) {
	if (l<0) {
		int v=get(1, 0, N-1, l+N, N-1);
		return v!=-1?v:get(1, 0, N-1, 0, r);
	}
	if (r>=N) {
		int v=get(1, 0, N-1, l, N-1);
		return v!=-1?v:get(1, 0, N-1, 0, r-N);
	}
	return get(1, 0, N-1, l, r);
}
int val(int i, int s, int e, int t) {
	spr(i, s==e);
	if (s==e) return st[i];
	int m=(s+e)/2;
	if (t<=m) return val(i*2, s, m, t);
	return val(i*2+1, m+1, e, t);
}

vector<int> lv;
vector<vector<pair<ll, int>>> L, R;

void init(int K, vector<int> r) {
	auto val = [&](int x) {
		if (get(x, x)==-1||get(x-K+1, x-1)!=-1) return false;
		return true;
	};
	auto upd = [&](int l, int r, int v) {
		if (l<0) {
			::upd(1, 0, N-1, 0, r, v);
			::upd(1, 0, N-1, l+N, N-1, v);
		}
		else ::upd(1, 0, N-1, l, r, v);
	};

	::N=r.size(), ::K=K;
	for (auto &i:r) i=K-1-i;
	init(1, 0, N-1, r);

	lv.resize(N);
	int t=0;
	vector<int> lg;
	for (int i=0; i<N; i++) if (val(i)) lg.emplace_back(i);
	while (st[1]>=0) {
		++t;
		vector<int> nx;
		for (auto &i:lg) {
			if (lv[i]) continue;
			lv[i]=t;
			upd(i, i, -(1e9));
			upd(i-K+1, i-1, 1);
			int li=get(i-K+1, i-1), ri=get(i+1, i+K-1);
			if (li!=-1&&val(li)) nx.emplace_back(li);
			if (ri!=-1&&val(ri)) nx.emplace_back(ri);
		}
		swap(lg, nx);
	}

	L.resize(N);
	R.resize(N);
	set<pair<ll, int>> lr;
	for (int i=N-K+1; i<N; i++) lr.emplace(lv[i], i);
	for (int i=0; i<N; i++) {
		auto k=lr.lower_bound({lv[i], i});
		if (k!=lr.end()) L[i].emplace_back((i-(k->second)+N)%N, k->second);
		int b=(i-K+1+N)%N;
		lr.erase({lv[b], b});
		lr.emplace(lv[i], i);
	}
	lr.clear();
	for (int i=0; i<K-1; i++) lr.emplace(lv[i], i);
	for (int i=N-1; i>=0; i--) {
		auto k=lr.lower_bound({lv[i], i});
		if (k!=lr.end()) L[i].emplace_back(((k->second)-i+N)%N, k->second);
		int b=(i+K-1)%N;
		lr.erase({lv[b], b});
		lr.emplace(lv[i], i);
	}
	for (int j=0; j<20; j++) for (int i=0; i<N; i++) {
		if (L[i].size()>j&&L[L[i][j].second].size()>j) {
			int b=L[i][j].second;
			L[i].emplace_back(L[b][j].first+L[i][j].first, L[b][j].second);
		}
		if (R[i].size()>j&&R[R[i][j].second].size()>j) {
			int b=R[i][j].second;
			R[i].emplace_back(R[b][j].first+R[i][j].first, R[b][j].second);
		}
	}
}

bool cmp(int x, int y) {
	if (lv[x]>=lv[y]) return false;
	int l=x, r=x;
	ll ld=0, rd=0;
	for (int i=19; i>=0; i--) {
		if (L[l].size()>i&&lv[L[l][i].second]<lv[y]) ld+=L[l][i].first, l=L[l][i].second;
		if (R[r].size()>i&&lv[R[r][i].second]<lv[y]) rd+=R[l][i].first, r=R[r][i].second;
	}
	for (int i=-1; i<=1; i++) if (x-ld-K+1<=y+N*i<=x+rd+K-1) return true;
	return false;
}

int compare_plants(int x, int y) {
	if (cmp(x, y)) return 1;
	if (cmp(y, x)) return -1;
	return 0;
}

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:121:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  121 |   if (L[i].size()>j&&L[L[i][j].second].size()>j) {
      |       ~~~~~~~~~~~^~
plants.cpp:121:46: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  121 |   if (L[i].size()>j&&L[L[i][j].second].size()>j) {
      |                      ~~~~~~~~~~~~~~~~~~~~~~~~^~
plants.cpp:125:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  125 |   if (R[i].size()>j&&R[R[i][j].second].size()>j) {
      |       ~~~~~~~~~~~^~
plants.cpp:125:46: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  125 |   if (R[i].size()>j&&R[R[i][j].second].size()>j) {
      |                      ~~~~~~~~~~~~~~~~~~~~~~~~^~
plants.cpp: In function 'bool cmp(int, int)':
plants.cpp:137:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  137 |   if (L[l].size()>i&&lv[L[l][i].second]<lv[y]) ld+=L[l][i].first, l=L[l][i].second;
      |       ~~~~~~~~~~~^~
plants.cpp:138:18: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  138 |   if (R[r].size()>i&&lv[R[r][i].second]<lv[y]) rd+=R[l][i].first, r=R[r][i].second;
      |       ~~~~~~~~~~~^~
plants.cpp:140:40: warning: comparisons like 'X<=Y<=Z' do not have their mathematical meaning [-Wparentheses]
  140 |  for (int i=-1; i<=1; i++) if (x-ld-K+1<=y+N*i<=x+rd+K-1) return true;
      |                                ~~~~~~~~^~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 1 ms 364 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 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 7 ms 1004 KB Output is correct
7 Correct 168 ms 6508 KB Output is correct
8 Correct 3 ms 492 KB Output is correct
9 Correct 7 ms 1004 KB Output is correct
10 Correct 163 ms 8428 KB Output is correct
11 Correct 155 ms 7256 KB Output is correct
12 Correct 141 ms 7404 KB Output is correct
13 Correct 172 ms 8368 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 7 ms 1004 KB Output is correct
7 Correct 168 ms 6508 KB Output is correct
8 Correct 3 ms 492 KB Output is correct
9 Correct 7 ms 1004 KB Output is correct
10 Correct 163 ms 8428 KB Output is correct
11 Correct 155 ms 7256 KB Output is correct
12 Correct 141 ms 7404 KB Output is correct
13 Correct 172 ms 8368 KB Output is correct
14 Correct 429 ms 18156 KB Output is correct
15 Correct 3028 ms 134272 KB Output is correct
16 Correct 393 ms 18284 KB Output is correct
17 Correct 3040 ms 134248 KB Output is correct
18 Correct 1738 ms 116140 KB Output is correct
19 Correct 1582 ms 116588 KB Output is correct
20 Correct 3388 ms 139292 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 115 ms 3820 KB Output is correct
4 Correct 1436 ms 108012 KB Output is correct
5 Correct 1457 ms 121196 KB Output is correct
6 Correct 1686 ms 128876 KB Output is correct
7 Correct 2004 ms 127340 KB Output is correct
8 Correct 2783 ms 132148 KB Output is correct
9 Correct 1110 ms 70252 KB Output is correct
10 Correct 1176 ms 73796 KB Output is correct
11 Correct 1306 ms 109420 KB Output is correct
12 Correct 1276 ms 109676 KB Output is correct
13 Correct 1652 ms 113388 KB Output is correct

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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