Submission #629840

#	Time	Username	Problem	Language	Result	Execution time	Memory
629840		MilosMilutinovic	Comparing Plants (IOI20_plants)	C++14	100 / 100	1256 ms	133644 KiB

plants

#include "plants.h"
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i ++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i ++)
#define MP make_pair

using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int INF = 1e9;

int n, k, h[400005];
int jumpL[400005][25];
int jumpR[400005][25];
struct segt
{
	PII dat[4000005]; int tag[4000005];
	segt() { rep(i, 4000005) dat[i] = MP(1e9, 1e9); }
	void pull(int cv) { dat[cv] = min(dat[cv << 1], dat[cv << 1 | 1]); }
	void upd(int cv, int v) { dat[cv].first -= v; tag[cv] += v; pushtag(cv); }
	void pushtag(int cv) {
		if(tag[cv] == 0) return;
		dat[cv << 1 | 0].first -= tag[cv];
		dat[cv << 1 | 1].first -= tag[cv];
		tag[cv << 1 | 0] += tag[cv];
		tag[cv << 1 | 1] += tag[cv];
		tag[cv] = 0;
	}
	void build(int cv = 1, int cl = 0, int cr = n - 1) {
		if(cl == cr) { dat[cv] = MP(h[cl], cl); return; }
		int mid = cl + cr >> 1;
		build(cv << 1 | 0, cl, mid);
		build(cv << 1 | 1, mid + 1, cr);
		pull(cv);
	}
	void modify(int ql, int qr, int v, int cv = 1, int cl = 0, int cr = n - 1) {
		if(cr < ql || cl > qr || cl > cr) return;
		if(ql <= cl && cr <= qr) { upd(cv, v); return; }
		int mid = cl + cr >> 1;
		pushtag(cv);
		modify(ql, qr, v, cv << 1 | 0, cl, mid);
		modify(ql, qr, v, cv << 1 | 1, mid + 1, cr);
		pull(cv);
	}
	PII query(int ql, int qr, int cv = 1, int cl = 0, int cr = n - 1) {
		pushtag(cv);
		if(cl > cr || cl > qr || cr < ql) return MP(1e9, 1e9);
		if(ql <= cl && cr <= qr) return dat[cv];
		int mid = cl + cr >> 1;
		PII L = query(ql, qr, cv << 1 | 0, cl, mid);
		PII R = query(ql, qr, cv << 1 | 1, mid + 1, cr);
		pull(cv);
		return min(L, R);
	}
	void update(int l, int r, int v) {
		l %= n; l = (l + n) % n;
		r %= n; r = (r + n) % n;
		if(l <= r) modify(l, r, v);
		else modify(0, r, v), modify(l, n - 1, v);
	}
	PII get(int l, int r) {
		l %= n; l = (l + n) % n;
		r %= n; r = (r + n) % n;
		if(l <= r) return query(l, r);
		else return min(query(0, r), query(l, n - 1));
	}
} tre;
struct segt1
{
	PII dat[4000005];
	void build(int cv = 1, int cl = 1, int cr = n) {
		dat[cv] = MP(-1, -1);
		if(cl == cr) return;
		int mid = cl + cr >> 1;
		build(cv << 1, cl, mid);
		build(cv << 1 | 1, mid + 1, cr);
	}
	void modify(int idx, PII v, int cv = 1, int cl = 1, int cr = n) {
		if(cl == cr) { dat[cv] = v; return; }
		int mid = cl + cr >> 1;
		if(idx <= mid) modify(idx, v, cv << 1, cl, mid);
		else modify(idx, v, cv << 1 | 1, mid + 1, cr);
		dat[cv] = max(dat[cv << 1], dat[cv << 1 | 1]);
	}
	PII query(int ql, int qr, int cv = 1, int cl = 1, int cr = n) {
		if(cl > cr || cl > qr || cr < ql) return MP(-1, -1);
		if(ql <= cl && cr <= qr) return dat[cv];
		int mid = cl + cr >> 1;
		return max(query(ql, qr, cv << 1, cl, mid), query(ql, qr, cv << 1 | 1, mid + 1, cr));
	}
} tre1;
vector<int> ord;
void go(int x)
{
	while(tre.get(x - (k - 1), x - 1).first == 0) go(tre.get(x - (k - 1), x - 1).second);
	tre.update(x - (k - 1), x, 1);
	tre.update(x, x, -1e9);
	ord.push_back(x);
}
int dis(int i, int j) { return i > j ? n - i + j : j - i; }
void init(int k, vector<int> r)
{
	n = (int) r.size(); ::k = k;
	rep(i, n) h[i] = r[i];
	tre.build();
	while(ord.size() < n) go(tre.dat[1].second);
	rep(i, n) h[ord[i]] = n - i;
	rep(i, n) h[i + n] = h[i]; n *= 2;
	tre1.build();
	rep(i, n) {
		if(i - k >= 0) tre1.modify(h[i - k], MP(-1, -1));
		jumpL[i][0] = tre1.query(1, h[i] - 1).second;
		tre1.modify(h[i], MP(h[i], i));
	}
	tre1.build();
	for(int i = n - 1; i >= 0; i --) {
		if(i + k < n) tre1.modify(h[i + k], MP(-1, -1));
		jumpR[i][0] = tre1.query(1, h[i] - 1).second;
		tre1.modify(h[i], MP(h[i], i));
	}
	rep1(j, 24) rep(i, n) jumpL[i][j] = (jumpL[i][j - 1] == -1 ? -1 : jumpL[jumpL[i][j - 1]][j - 1]);
	rep1(j, 24) rep(i, n) jumpR[i][j] = (jumpR[i][j - 1] == -1 ? -1 : jumpR[jumpR[i][j - 1]][j - 1]);
}
/*bool cmp(int i, int j)
{
	if(jump[i][0] == -1) return false;
	int L = ;
	for(int k = 24; k >= 0; k--) {
		if(jump[i][k] != -1 && )
	}
	if(dis(i, j) >= k && jump[i][0] != -1) i = jump[i][0];
	return (dis(i, j) < k && h[i] > h[j]);
}*/
bool cmpR(int i, int j)
{
	for(int k = 24; k >= 0; k --) if(jumpR[i][k] != -1 && jumpR[i][k] < j) i = jumpR[i][k];
	return (j - i < k && h[i] > h[j]);
}
bool cmpL(int i, int j)
{
	for(int k = 24; k >= 0; k --) if(jumpL[i][k] != -1 && jumpL[i][k] > j) i = jumpL[i][k];
	return (i - j < k && h[i] > h[j]);
}
int compare_plants(int x, int y)
{
	if(x > y) return -compare_plants(x, y);
	if(cmpR(x, y)) return 1;
	if(cmpR(y, x + n / 2)) return -1;
	if(cmpL(y, x)) return -1;
	if(cmpL(x + n / 2, y)) return 1;
	return 0;
}

/*
4 3 2
0 1 1 2
0 2
1 2

4 2 2
0 1 0 1
0 3
1 3

*/

Compilation message (stderr)

plants.cpp: In member function 'void segt::build(int, int, int)':
plants.cpp:31:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |   int mid = cl + cr >> 1;
      |             ~~~^~~~
plants.cpp: In member function 'void segt::modify(int, int, int, int, int, int)':
plants.cpp:39:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   39 |   int mid = cl + cr >> 1;
      |             ~~~^~~~
plants.cpp: In member function 'PII segt::query(int, int, int, int, int)':
plants.cpp:49:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |   int mid = cl + cr >> 1;
      |             ~~~^~~~
plants.cpp: In member function 'void segt1::build(int, int, int)':
plants.cpp:74:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |   int mid = cl + cr >> 1;
      |             ~~~^~~~
plants.cpp: In member function 'void segt1::modify(int, PII, int, int, int)':
plants.cpp:80:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |   int mid = cl + cr >> 1;
      |             ~~~^~~~
plants.cpp: In member function 'PII segt1::query(int, int, int, int, int)':
plants.cpp:88:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   88 |   int mid = cl + cr >> 1;
      |             ~~~^~~~
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:106:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  106 |  while(ord.size() < n) go(tre.dat[1].second);
      |        ~~~~~~~~~~~^~~
plants.cpp:3:19: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    3 | #define rep(i, n) for(int i = 0; i < (int)(n); i ++)
      |                   ^~~
plants.cpp:108:2: note: in expansion of macro 'rep'
  108 |  rep(i, n) h[i + n] = h[i]; n *= 2;
      |  ^~~
plants.cpp:108:29: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  108 |  rep(i, n) h[i + n] = h[i]; n *= 2;
      |                             ^

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 17 / 17
• Subtask 5: 11 / 11
• Subtask 6: 15 / 15
• Subtask 7: 25 / 25