oj.uz

Submission #629836

# Submission time Handle Problem Language Result Execution time Memory
629836 2022-08-15T08:48:33 Z MilosMilutinovic Comparing Plants (IOI20_plants) C++14
30 / 100
 1241 ms 146924 KB 
#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[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;
struct segt1
{
	PII dat[1200005];
	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 >= 0) 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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12852 KB Output is correct
2 Correct 7 ms 12756 KB Output is correct
3 Correct 8 ms 12848 KB Output is correct
4 Correct 8 ms 12848 KB Output is correct
5 Correct 9 ms 12836 KB Output is correct
6 Correct 112 ms 16600 KB Output is correct
7 Correct 167 ms 27556 KB Output is correct
8 Correct 813 ms 112280 KB Output is correct
9 Correct 822 ms 112352 KB Output is correct
10 Correct 840 ms 112320 KB Output is correct
11 Correct 843 ms 112260 KB Output is correct
12 Correct 850 ms 112256 KB Output is correct
13 Correct 784 ms 112352 KB Output is correct
14 Correct 962 ms 112336 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12756 KB Output is correct
2 Correct 7 ms 12828 KB Output is correct
3 Correct 7 ms 12756 KB Output is correct
4 Correct 7 ms 12756 KB Output is correct
5 Correct 8 ms 12884 KB Output is correct
6 Correct 12 ms 13368 KB Output is correct
7 Correct 120 ms 19968 KB Output is correct
8 Correct 9 ms 13012 KB Output is correct
9 Correct 11 ms 13396 KB Output is correct
10 Correct 100 ms 20012 KB Output is correct
11 Correct 96 ms 19948 KB Output is correct
12 Correct 126 ms 20192 KB Output is correct
13 Correct 98 ms 20056 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12756 KB Output is correct
2 Correct 7 ms 12828 KB Output is correct
3 Correct 7 ms 12756 KB Output is correct
4 Correct 7 ms 12756 KB Output is correct
5 Correct 8 ms 12884 KB Output is correct
6 Correct 12 ms 13368 KB Output is correct
7 Correct 120 ms 19968 KB Output is correct
8 Correct 9 ms 13012 KB Output is correct
9 Correct 11 ms 13396 KB Output is correct
10 Correct 100 ms 20012 KB Output is correct
11 Correct 96 ms 19948 KB Output is correct
12 Correct 126 ms 20192 KB Output is correct
13 Correct 98 ms 20056 KB Output is correct
14 Correct 159 ms 27756 KB Output is correct
15 Runtime error 773 ms 146924 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12756 KB Output is correct
2 Correct 9 ms 12828 KB Output is correct
3 Correct 108 ms 18296 KB Output is correct
4 Correct 999 ms 114600 KB Output is correct
5 Correct 1079 ms 113056 KB Output is correct
6 Correct 1241 ms 113164 KB Output is correct
7 Runtime error 805 ms 146592 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12756 KB Output is correct
2 Correct 9 ms 12756 KB Output is correct
3 Correct 7 ms 12836 KB Output is correct
4 Correct 9 ms 12792 KB Output is correct
5 Correct 8 ms 12844 KB Output is correct
6 Correct 12 ms 13012 KB Output is correct
7 Correct 30 ms 13848 KB Output is correct
8 Correct 26 ms 13876 KB Output is correct
9 Correct 28 ms 13900 KB Output is correct
10 Correct 30 ms 13936 KB Output is correct
11 Correct 30 ms 13856 KB Output is correct
12 Correct 37 ms 13868 KB Output is correct
13 Correct 25 ms 13876 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12840 KB Output is correct
2 Correct 7 ms 12756 KB Output is correct
3 Correct 8 ms 12856 KB Output is correct
4 Correct 7 ms 12840 KB Output is correct
5 Correct 11 ms 13344 KB Output is correct
6 Correct 1008 ms 111956 KB Output is correct
7 Correct 1187 ms 112272 KB Output is correct
8 Runtime error 804 ms 145648 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12852 KB Output is correct
2 Correct 7 ms 12756 KB Output is correct
3 Correct 8 ms 12848 KB Output is correct
4 Correct 8 ms 12848 KB Output is correct
5 Correct 9 ms 12836 KB Output is correct
6 Correct 112 ms 16600 KB Output is correct
7 Correct 167 ms 27556 KB Output is correct
8 Correct 813 ms 112280 KB Output is correct
9 Correct 822 ms 112352 KB Output is correct
10 Correct 840 ms 112320 KB Output is correct
11 Correct 843 ms 112260 KB Output is correct
12 Correct 850 ms 112256 KB Output is correct
13 Correct 784 ms 112352 KB Output is correct
14 Correct 962 ms 112336 KB Output is correct
15 Correct 7 ms 12756 KB Output is correct
16 Correct 7 ms 12828 KB Output is correct
17 Correct 7 ms 12756 KB Output is correct
18 Correct 7 ms 12756 KB Output is correct
19 Correct 8 ms 12884 KB Output is correct
20 Correct 12 ms 13368 KB Output is correct
21 Correct 120 ms 19968 KB Output is correct
22 Correct 9 ms 13012 KB Output is correct
23 Correct 11 ms 13396 KB Output is correct
24 Correct 100 ms 20012 KB Output is correct
25 Correct 96 ms 19948 KB Output is correct
26 Correct 126 ms 20192 KB Output is correct
27 Correct 98 ms 20056 KB Output is correct
28 Correct 159 ms 27756 KB Output is correct
29 Runtime error 773 ms 146924 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -