oj.uz

Submission #629838

# Submission time Handle Problem Language Result Execution time Memory
629838 2022-08-15T08:50:33 Z MilosMilutinovic Comparing Plants (IOI20_plants) C++14
30 / 100
 1262 ms 181268 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[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 >= 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 21 ms 31616 KB Output is correct
2 Correct 18 ms 31576 KB Output is correct
3 Correct 17 ms 31644 KB Output is correct
4 Correct 17 ms 31572 KB Output is correct
5 Correct 19 ms 31648 KB Output is correct
6 Correct 114 ms 34388 KB Output is correct
7 Correct 196 ms 44172 KB Output is correct
8 Correct 794 ms 128112 KB Output is correct
9 Correct 806 ms 128108 KB Output is correct
10 Correct 851 ms 128256 KB Output is correct
11 Correct 882 ms 128072 KB Output is correct
12 Correct 875 ms 128100 KB Output is correct
13 Correct 814 ms 128072 KB Output is correct
14 Correct 899 ms 128020 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 31556 KB Output is correct
2 Correct 21 ms 31572 KB Output is correct
3 Correct 18 ms 31620 KB Output is correct
4 Correct 18 ms 31620 KB Output is correct
5 Correct 18 ms 31648 KB Output is correct
6 Correct 26 ms 32096 KB Output is correct
7 Correct 110 ms 36848 KB Output is correct
8 Correct 20 ms 31744 KB Output is correct
9 Correct 22 ms 32176 KB Output is correct
10 Correct 122 ms 36888 KB Output is correct
11 Correct 110 ms 36868 KB Output is correct
12 Correct 140 ms 36980 KB Output is correct
13 Correct 109 ms 36960 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 31556 KB Output is correct
2 Correct 21 ms 31572 KB Output is correct
3 Correct 18 ms 31620 KB Output is correct
4 Correct 18 ms 31620 KB Output is correct
5 Correct 18 ms 31648 KB Output is correct
6 Correct 26 ms 32096 KB Output is correct
7 Correct 110 ms 36848 KB Output is correct
8 Correct 20 ms 31744 KB Output is correct
9 Correct 22 ms 32176 KB Output is correct
10 Correct 122 ms 36888 KB Output is correct
11 Correct 110 ms 36868 KB Output is correct
12 Correct 140 ms 36980 KB Output is correct
13 Correct 109 ms 36960 KB Output is correct
14 Correct 176 ms 44292 KB Output is correct
15 Runtime error 752 ms 181180 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 17 ms 31572 KB Output is correct
2 Correct 17 ms 31548 KB Output is correct
3 Correct 117 ms 35320 KB Output is correct
4 Correct 1025 ms 130380 KB Output is correct
5 Correct 1074 ms 128728 KB Output is correct
6 Correct 1262 ms 128796 KB Output is correct
7 Runtime error 827 ms 181268 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 19 ms 31572 KB Output is correct
2 Correct 18 ms 31608 KB Output is correct
3 Correct 20 ms 31624 KB Output is correct
4 Correct 20 ms 31608 KB Output is correct
5 Correct 18 ms 31572 KB Output is correct
6 Correct 21 ms 31668 KB Output is correct
7 Correct 40 ms 32332 KB Output is correct
8 Correct 37 ms 32416 KB Output is correct
9 Correct 40 ms 32424 KB Output is correct
10 Correct 38 ms 32320 KB Output is correct
11 Correct 46 ms 32320 KB Output is correct
12 Correct 48 ms 32332 KB Output is correct
13 Correct 36 ms 32356 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31572 KB Output is correct
2 Correct 17 ms 31572 KB Output is correct
3 Correct 18 ms 31624 KB Output is correct
4 Correct 17 ms 31572 KB Output is correct
5 Correct 24 ms 32044 KB Output is correct
6 Correct 1008 ms 128596 KB Output is correct
7 Correct 1195 ms 128656 KB Output is correct
8 Runtime error 836 ms 181260 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 21 ms 31616 KB Output is correct
2 Correct 18 ms 31576 KB Output is correct
3 Correct 17 ms 31644 KB Output is correct
4 Correct 17 ms 31572 KB Output is correct
5 Correct 19 ms 31648 KB Output is correct
6 Correct 114 ms 34388 KB Output is correct
7 Correct 196 ms 44172 KB Output is correct
8 Correct 794 ms 128112 KB Output is correct
9 Correct 806 ms 128108 KB Output is correct
10 Correct 851 ms 128256 KB Output is correct
11 Correct 882 ms 128072 KB Output is correct
12 Correct 875 ms 128100 KB Output is correct
13 Correct 814 ms 128072 KB Output is correct
14 Correct 899 ms 128020 KB Output is correct
15 Correct 20 ms 31556 KB Output is correct
16 Correct 21 ms 31572 KB Output is correct
17 Correct 18 ms 31620 KB Output is correct
18 Correct 18 ms 31620 KB Output is correct
19 Correct 18 ms 31648 KB Output is correct
20 Correct 26 ms 32096 KB Output is correct
21 Correct 110 ms 36848 KB Output is correct
22 Correct 20 ms 31744 KB Output is correct
23 Correct 22 ms 32176 KB Output is correct
24 Correct 122 ms 36888 KB Output is correct
25 Correct 110 ms 36868 KB Output is correct
26 Correct 140 ms 36980 KB Output is correct
27 Correct 109 ms 36960 KB Output is correct
28 Correct 176 ms 44292 KB Output is correct
29 Runtime error 752 ms 181180 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -