oj.uz

Submission #364357

# Submission time Handle Problem Language Result Execution time Memory
364357 2021-02-09T02:57:37 Z dennisstar Comparing Plants (IOI20_plants) C++17
27 / 100
 3389 ms 135280 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&&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;
      |       ~~~~~~~~~~~^~

Subtask #1
0 / 5.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 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Incorrect 1 ms 364 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 368 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 172 ms 6504 KB Output is correct
8 Correct 3 ms 492 KB Output is correct
9 Correct 8 ms 1004 KB Output is correct
10 Correct 170 ms 6508 KB Output is correct
11 Correct 148 ms 5356 KB Output is correct
12 Correct 145 ms 5484 KB Output is correct
13 Correct 178 ms 6636 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 368 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 172 ms 6504 KB Output is correct
8 Correct 3 ms 492 KB Output is correct
9 Correct 8 ms 1004 KB Output is correct
10 Correct 170 ms 6508 KB Output is correct
11 Correct 148 ms 5356 KB Output is correct
12 Correct 145 ms 5484 KB Output is correct
13 Correct 178 ms 6636 KB Output is correct
14 Correct 396 ms 16108 KB Output is correct
15 Correct 3049 ms 130544 KB Output is correct
16 Correct 417 ms 15980 KB Output is correct
17 Correct 3025 ms 130400 KB Output is correct
18 Correct 1719 ms 112876 KB Output is correct
19 Correct 1597 ms 112920 KB Output is correct
20 Correct 3389 ms 135280 KB Output is correct

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.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 Incorrect 0 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 1 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 #7
0 / 25.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 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Incorrect 1 ms 364 KB Output isn't correct
6 Halted 0 ms 0 KB -