#include <bits/stdc++.h>
#include "plants.h"
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define N 200005
#define PB push_back
#define sz(x) int(x.size())
#define P 31
#define F first
#define M ll(1e9 + 7)
#define S second
#define all(x) x.begin(), x.end()
#define endl '\n'
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")
using namespace std;
//using namespace __gnu_pbds;
typedef long long ll;
//typedef tree<int, null_type, less_equal <int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
ll mlt(ll a, ll b) {return (a * b) % M;}
ll sm(ll a, ll b) {return (a + b) % M;}
int id, K, h[N];
array <int, 3> t[N * 4];
int psh[N * 4], psp[N * 4], n;
vector <pair <int, int> > gt[N];
vector <int> a;
set <int> g[N];
void updater(int v, int ps, int l, int r)
{
if (psp[v] == -1) psp[v] = ps;
else
{
int len1, len2;
int psr = t[v][2];
if (psr < psp[v]) len1 = n - psp[v] + psr;
else psr - psp[v];
if (psr < ps) len2 = n - ps + psr;
else psr - ps;
if (len2 > len1) psp[v] = ps;
}
}
void Push(int v, int tl, int tr)
{
t[v][0] += psh[v];
t[v][0] = max(t[v][0], 0);
if (tl != tr)
{
psh[v + v] += psh[v];
psh[v + v + 1] += psh[v];
}
psh[v] = 0;
if (psp[v] == -1) return;
if (tl != tr)
{
int md = (tl + tr) >> 1;
updater(v + v, psp[v], tl, md);
updater(v + v + 1, psp[v], md + 1, tr);
}
int psr = t[v][2];
t[v][1] = max(t[v][1], (psr < psp[v] ? n - psp[v] + psr : psr - psp[v]));
psp[v] = -1;
}
void com(int v)
{
if (t[v + v][0] == t[v + v + 1][0])
{
if (t[v + v][1] > t[v + v + 1][1]) t[v] = t[v + v];
else t[v] = t[v + v + 1];
}
else
{
if (t[v + v][0] < t[v + v + 1][0]) t[v] = t[v + v];
else t[v] = t[v + v + 1];
}
}
void bld(int v, int tl, int tr)
{
psp[v] = -1;
if (tl == tr) t[v] = {a[tl], 0, tl};
else
{
int md = (tl + tr) >> 1;
bld(v + v, tl, md);
bld(v + v + 1, md + 1, tr);
com(v);
}
}
void upd(int v, int tl, int tr, int ps)
{
Push(v, tl, tr);
if (tr < ps || ps < tl) return;
if (tl == tr) t[v] = {int(1e9), 0, tl};
else
{
int md = (tl + tr) >> 1;
upd(v + v, tl, md, ps);
upd(v + v + 1, md + 1, tr, ps);
com(v);
}
}
void upd(int v, int tl, int tr, int l, int r)
{
Push(v, tl, tr);
if (tr < l || r < tl || l > r || tl > tr) return;
if (l <= tl && tr <= r) {psh[v]--; Push(v, tl, tr); return;}
int md = (tl + tr) >> 1;
upd(v + v, tl, md, l, r);
upd(v + v + 1, md + 1, tr, l, r);
com(v);
}
void upd(int v, int tl, int tr, int l, int r, int ps)
{
Push(v, tl, tr);
if (tr < l || r < tl || l > r || tl > tr) return;
if (l <= tl && tr <= r) {updater(v, ps, tl, tr); Push(v, tl, tr); return;}
int md = (tl + tr) >> 1;
upd(v + v, tl, md, l, r, ps);
upd(v + v + 1, md + 1, tr, l, r, ps);
com(v);
}
void dfs(int v)
{
pair <int, int> pt;
pt.F = id++;
for (auto it : g[v])
dfs(it);
pt.S = id++;
gt[v].PB(pt);
}
void init(int k, vector<int> r)
{
K = k;
n = sz(r);
if (k == 2)
{
set <int> se; se.clear();
for (int i = 0; i < sz(r); i++) se.insert(i);
for (int i = 0; i < sz(r); i++)
{
int nxt = (i + 1) % sz(r);
if (r[i] == 1) {g[nxt].insert(i); se.erase(i);}
else {g[i].insert(nxt);se.erase(nxt);}
}
for (auto it : se) dfs(it);
return;
}
a = r;
bld(1, 0, n - 1);
for (int i = 0; i < n; i++)
if (r[i] == 0)
{
upd(1, 0, n - 1, 0, i - 1, i);
upd(1, 0, n - 1, i + 1, n - 1, i);
}
int cur = n;
while (cur > 0)
{
array <int, 3> b = t[1];
h[b[2]] = cur--;
upd(1, 0, n - 1, b[2]);
upd(1, 0, n - 1, max(0, b[2] - k + 1), b[2] - 1);
if (b[2] - k + 1 < 0) upd(1, 0, n - 1, n - abs(b[2] - k + 1), n - 1);
upd(1, 0, n - 1, 0, n - 1, b[2]);
}
return;
}
int compare_plants(int x, int y)
{
if (K == 2)
{
for (auto it : gt[x])
for (auto itr : gt[y])
if (it.F <= itr.F && itr.S <= it.S) return 1;
else if (itr.F <= it.F && it.S <= itr.S) return -1;
return 0;
}
if (h[x] > h[y]) return 1;
return -1;
}
//int main()
//{
//// freopen("help.in", "r", stdin); freopen("help.out", "w", stdout);
//
// ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//
// init(4, {2, 3, 1, 0, 3, 1, 2});
//
// for (int i = 0; i < 7; i++) cout << h[i] << " ";
//}
Compilation message
plants.cpp: In function 'void updater(int, int, int, int)':
plants.cpp:54:20: warning: statement has no effect [-Wunused-value]
54 | else psr - psp[v];
| ~~~~^~~~~~~~
plants.cpp:57:20: warning: statement has no effect [-Wunused-value]
57 | else psr - ps;
| ~~~~^~~~
plants.cpp:59:9: warning: 'len2' may be used uninitialized in this function [-Wmaybe-uninitialized]
59 | if (len2 > len1) psp[v] = ps;
| ^~
plants.cpp:59:9: warning: 'len1' may be used uninitialized in this function [-Wmaybe-uninitialized]
plants.cpp: In function 'void Push(int, int, int)':
plants.cpp:59:9: warning: 'len2' may be used uninitialized in this function [-Wmaybe-uninitialized]
59 | if (len2 > len1) psp[v] = ps;
| ^~
plants.cpp:49:19: note: 'len2' was declared here
49 | int len1, len2;
| ^~~~
plants.cpp:59:9: warning: 'len1' may be used uninitialized in this function [-Wmaybe-uninitialized]
59 | if (len2 > len1) psp[v] = ps;
| ^~
plants.cpp:49:13: note: 'len1' was declared here
49 | int len1, len2;
| ^~~~
plants.cpp:59:9: warning: 'len2' may be used uninitialized in this function [-Wmaybe-uninitialized]
59 | if (len2 > len1) psp[v] = ps;
| ^~
plants.cpp:49:19: note: 'len2' was declared here
49 | int len1, len2;
| ^~~~
plants.cpp:59:9: warning: 'len1' may be used uninitialized in this function [-Wmaybe-uninitialized]
59 | if (len2 > len1) psp[v] = ps;
| ^~
plants.cpp:49:13: note: 'len1' was declared here
49 | int len1, len2;
| ^~~~
plants.cpp: In function 'void upd(int, int, int, int, int, int)':
plants.cpp:59:9: warning: 'len2' may be used uninitialized in this function [-Wmaybe-uninitialized]
59 | if (len2 > len1) psp[v] = ps;
| ^~
plants.cpp:49:19: note: 'len2' was declared here
49 | int len1, len2;
| ^~~~
plants.cpp:59:9: warning: 'len1' may be used uninitialized in this function [-Wmaybe-uninitialized]
59 | if (len2 > len1) psp[v] = ps;
| ^~
plants.cpp:49:13: note: 'len1' was declared here
49 | int len1, len2;
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
14464 KB |
Output is correct |
2 |
Correct |
11 ms |
14464 KB |
Output is correct |
3 |
Correct |
12 ms |
14336 KB |
Output is correct |
4 |
Correct |
11 ms |
14464 KB |
Output is correct |
5 |
Correct |
11 ms |
14464 KB |
Output is correct |
6 |
Correct |
76 ms |
17272 KB |
Output is correct |
7 |
Correct |
107 ms |
18936 KB |
Output is correct |
8 |
Correct |
231 ms |
34424 KB |
Output is correct |
9 |
Correct |
221 ms |
34040 KB |
Output is correct |
10 |
Correct |
230 ms |
34296 KB |
Output is correct |
11 |
Correct |
229 ms |
35704 KB |
Output is correct |
12 |
Correct |
227 ms |
38904 KB |
Output is correct |
13 |
Correct |
224 ms |
43384 KB |
Output is correct |
14 |
Correct |
225 ms |
43384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
14464 KB |
Output is correct |
2 |
Correct |
11 ms |
14464 KB |
Output is correct |
3 |
Incorrect |
12 ms |
14464 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
14464 KB |
Output is correct |
2 |
Correct |
11 ms |
14464 KB |
Output is correct |
3 |
Incorrect |
12 ms |
14464 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
14464 KB |
Output is correct |
2 |
Correct |
12 ms |
14464 KB |
Output is correct |
3 |
Incorrect |
84 ms |
17468 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
14464 KB |
Output is correct |
2 |
Correct |
11 ms |
14464 KB |
Output is correct |
3 |
Correct |
12 ms |
14464 KB |
Output is correct |
4 |
Incorrect |
12 ms |
14464 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
14464 KB |
Output is correct |
2 |
Correct |
12 ms |
14464 KB |
Output is correct |
3 |
Correct |
12 ms |
14464 KB |
Output is correct |
4 |
Incorrect |
13 ms |
14464 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
14464 KB |
Output is correct |
2 |
Correct |
11 ms |
14464 KB |
Output is correct |
3 |
Correct |
12 ms |
14336 KB |
Output is correct |
4 |
Correct |
11 ms |
14464 KB |
Output is correct |
5 |
Correct |
11 ms |
14464 KB |
Output is correct |
6 |
Correct |
76 ms |
17272 KB |
Output is correct |
7 |
Correct |
107 ms |
18936 KB |
Output is correct |
8 |
Correct |
231 ms |
34424 KB |
Output is correct |
9 |
Correct |
221 ms |
34040 KB |
Output is correct |
10 |
Correct |
230 ms |
34296 KB |
Output is correct |
11 |
Correct |
229 ms |
35704 KB |
Output is correct |
12 |
Correct |
227 ms |
38904 KB |
Output is correct |
13 |
Correct |
224 ms |
43384 KB |
Output is correct |
14 |
Correct |
225 ms |
43384 KB |
Output is correct |
15 |
Correct |
11 ms |
14464 KB |
Output is correct |
16 |
Correct |
11 ms |
14464 KB |
Output is correct |
17 |
Incorrect |
12 ms |
14464 KB |
Output isn't correct |
18 |
Halted |
0 ms |
0 KB |
- |