This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (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;
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |