oj.uz

Submission #629837

# Submission time Handle Problem Language Result Execution time Memory
629837 2022-08-15T08:49:29 Z MilosMilutinovic Comparing Plants (IOI20_plants) C++14
30 / 100
 1224 ms 143124 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[1600005];
	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 8 ms 12756 KB Output is correct
2 Correct 8 ms 12756 KB Output is correct
3 Correct 7 ms 12756 KB Output is correct
4 Correct 8 ms 12756 KB Output is correct
5 Correct 9 ms 12756 KB Output is correct
6 Correct 100 ms 15676 KB Output is correct
7 Correct 174 ms 25424 KB Output is correct
8 Correct 777 ms 109320 KB Output is correct
9 Correct 860 ms 109336 KB Output is correct
10 Correct 828 ms 109248 KB Output is correct
11 Correct 830 ms 109248 KB Output is correct
12 Correct 867 ms 109220 KB Output is correct
13 Correct 785 ms 109404 KB Output is correct
14 Correct 856 ms 109408 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 12884 KB Output is correct
3 Correct 8 ms 12756 KB Output is correct
4 Correct 7 ms 12824 KB Output is correct
5 Correct 8 ms 12884 KB Output is correct
6 Correct 11 ms 13304 KB Output is correct
7 Correct 97 ms 18184 KB Output is correct
8 Correct 9 ms 12884 KB Output is correct
9 Correct 12 ms 13340 KB Output is correct
10 Correct 99 ms 18064 KB Output is correct
11 Correct 100 ms 18068 KB Output is correct
12 Correct 126 ms 18196 KB Output is correct
13 Correct 118 ms 18104 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 12884 KB Output is correct
3 Correct 8 ms 12756 KB Output is correct
4 Correct 7 ms 12824 KB Output is correct
5 Correct 8 ms 12884 KB Output is correct
6 Correct 11 ms 13304 KB Output is correct
7 Correct 97 ms 18184 KB Output is correct
8 Correct 9 ms 12884 KB Output is correct
9 Correct 12 ms 13340 KB Output is correct
10 Correct 99 ms 18064 KB Output is correct
11 Correct 100 ms 18068 KB Output is correct
12 Correct 126 ms 18196 KB Output is correct
13 Correct 118 ms 18104 KB Output is correct
14 Correct 163 ms 25416 KB Output is correct
15 Runtime error 745 ms 143092 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 8 ms 12756 KB Output is correct
2 Correct 9 ms 12828 KB Output is correct
3 Correct 104 ms 16612 KB Output is correct
4 Correct 965 ms 111580 KB Output is correct
5 Correct 1113 ms 109916 KB Output is correct
6 Correct 1224 ms 109776 KB Output is correct
7 Runtime error 832 ms 143124 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 7 ms 12756 KB Output is correct
3 Correct 7 ms 12828 KB Output is correct
4 Correct 8 ms 12756 KB Output is correct
5 Correct 7 ms 12884 KB Output is correct
6 Correct 9 ms 12968 KB Output is correct
7 Correct 31 ms 13524 KB Output is correct
8 Correct 29 ms 13600 KB Output is correct
9 Correct 29 ms 13652 KB Output is correct
10 Correct 26 ms 13632 KB Output is correct
11 Correct 29 ms 13524 KB Output is correct
12 Correct 32 ms 13616 KB Output is correct
13 Correct 24 ms 13536 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 12856 KB Output is correct
2 Correct 8 ms 12756 KB Output is correct
3 Correct 10 ms 12756 KB Output is correct
4 Correct 7 ms 12824 KB Output is correct
5 Correct 11 ms 13268 KB Output is correct
6 Correct 980 ms 109968 KB Output is correct
7 Correct 1185 ms 110040 KB Output is correct
8 Runtime error 845 ms 143116 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 8 ms 12756 KB Output is correct
2 Correct 8 ms 12756 KB Output is correct
3 Correct 7 ms 12756 KB Output is correct
4 Correct 8 ms 12756 KB Output is correct
5 Correct 9 ms 12756 KB Output is correct
6 Correct 100 ms 15676 KB Output is correct
7 Correct 174 ms 25424 KB Output is correct
8 Correct 777 ms 109320 KB Output is correct
9 Correct 860 ms 109336 KB Output is correct
10 Correct 828 ms 109248 KB Output is correct
11 Correct 830 ms 109248 KB Output is correct
12 Correct 867 ms 109220 KB Output is correct
13 Correct 785 ms 109404 KB Output is correct
14 Correct 856 ms 109408 KB Output is correct
15 Correct 7 ms 12756 KB Output is correct
16 Correct 7 ms 12884 KB Output is correct
17 Correct 8 ms 12756 KB Output is correct
18 Correct 7 ms 12824 KB Output is correct
19 Correct 8 ms 12884 KB Output is correct
20 Correct 11 ms 13304 KB Output is correct
21 Correct 97 ms 18184 KB Output is correct
22 Correct 9 ms 12884 KB Output is correct
23 Correct 12 ms 13340 KB Output is correct
24 Correct 99 ms 18064 KB Output is correct
25 Correct 100 ms 18068 KB Output is correct
26 Correct 126 ms 18196 KB Output is correct
27 Correct 118 ms 18104 KB Output is correct
28 Correct 163 ms 25416 KB Output is correct
29 Runtime error 745 ms 143092 KB Execution killed with signal 11
30 Halted 0 ms 0 KB -