Submission #628307

#	Time	Username	Problem	Language	Result	Execution time	Memory
628307		MilosMilutinovic	Comparing Plants (IOI20_plants)	C++14	11 / 100	4058 ms	46364 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[200005];
struct segt
{
	PII dat[1600005]; int tag[1600005];
	segt() { rep(i, 1600000) 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;
int dis[305][305];
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);
}
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) rep(j, n) dis[i][j] = INF;
	rep(i, n) rep1(j, k - 1) {
		if(h[i] > h[(i + j) % n]) dis[i][(i + j) % n] = 1;
		else dis[(i + j) % n][i] = 1;
	}
	rep(i, n) dis[i][i] = 0;
	rep(k, n) rep(i, n) rep(j, n) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}

int compare_plants(int x, int y)
{
	if(dis[x][y] != INF) return 1;
	if(dis[y][x] != INF) 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:29:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   29 |   int mid = cl + cr >> 1;
      |             ~~~^~~~
plants.cpp: In member function 'void segt::modify(int, int, int, int, int, int)':
plants.cpp:37:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |   int mid = cl + cr >> 1;
      |             ~~~^~~~
plants.cpp: In member function 'PII segt::query(int, int, int, int, int)':
plants.cpp:47:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |   int mid = cl + cr >> 1;
      |             ~~~^~~~
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:80:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |  while(ord.size() < n) go(tre.dat[1].second);
      |        ~~~~~~~~~~~^~~

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