#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)
{
vector <int> gr; gr.clear();
while (t[1][0] == 0)
{
gr.PB(t[1][2]);
upd(1, 0, n - 1, t[1][2]);
}
sort(all(gr));
vector <int> val(sz(gr));
vector <pair <int, int> > nxt(sz(gr));
set <pair <int, int> > se; se.clear();
for (int i = 0; i < sz(gr); i++)
{
if (i == 0) {nxt[i].F = sz(gr) - 1; val[i] = gr[i] + n - gr.back();}
else {nxt[i].F = i - 1; val[i] = gr[i] - gr[i - 1];}
if (i + 1 == sz(gr)) nxt[i].S = 0;
else nxt[i].S = i + 1;
se.insert({val[i], i});
}
while (sz(se) > 0)
{
int ps = (*se.rbegin()).S;
se.erase(*se.rbegin());
int pos = gr[ps];
h[pos] = cur--;
if (sz(se) != 0)
{
nxt[nxt[ps].F].S = nxt[ps].S;
nxt[nxt[ps].S].F = nxt[ps].F;
int l = nxt[ps].F, r = nxt[ps].S;
se.erase({val[r], r});
if (gr[l] < gr[r]) val[r] = gr[r] - gr[l];
else val[r] = n - gr[l] + gr[r];
se.insert({val[r], r});
}
upd(1, 0, n - 1, 0, n - 1, pos);
upd(1, 0, n - 1, max(0, pos - k + 1), pos - 1);
if (pos - k + 1 < 0) upd(1, 0, n - 1, n - abs(pos - k + 1), n - 1);
}
}
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 |
11 ms |
14464 KB |
Output is correct |
2 |
Correct |
11 ms |
14464 KB |
Output is correct |
3 |
Correct |
11 ms |
14464 KB |
Output is correct |
4 |
Correct |
11 ms |
14464 KB |
Output is correct |
5 |
Correct |
11 ms |
14464 KB |
Output is correct |
6 |
Correct |
81 ms |
17252 KB |
Output is correct |
7 |
Correct |
105 ms |
19080 KB |
Output is correct |
8 |
Correct |
235 ms |
34428 KB |
Output is correct |
9 |
Correct |
224 ms |
34040 KB |
Output is correct |
10 |
Correct |
224 ms |
34168 KB |
Output is correct |
11 |
Correct |
222 ms |
35576 KB |
Output is correct |
12 |
Correct |
221 ms |
38904 KB |
Output is correct |
13 |
Correct |
222 ms |
43512 KB |
Output is correct |
14 |
Correct |
235 ms |
43384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
14464 KB |
Output is correct |
2 |
Correct |
10 ms |
14464 KB |
Output is correct |
3 |
Correct |
11 ms |
14464 KB |
Output is correct |
4 |
Correct |
11 ms |
14464 KB |
Output is correct |
5 |
Correct |
11 ms |
14464 KB |
Output is correct |
6 |
Correct |
15 ms |
14592 KB |
Output is correct |
7 |
Correct |
96 ms |
17656 KB |
Output is correct |
8 |
Incorrect |
13 ms |
14464 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
14464 KB |
Output is correct |
2 |
Correct |
10 ms |
14464 KB |
Output is correct |
3 |
Correct |
11 ms |
14464 KB |
Output is correct |
4 |
Correct |
11 ms |
14464 KB |
Output is correct |
5 |
Correct |
11 ms |
14464 KB |
Output is correct |
6 |
Correct |
15 ms |
14592 KB |
Output is correct |
7 |
Correct |
96 ms |
17656 KB |
Output is correct |
8 |
Incorrect |
13 ms |
14464 KB |
Output isn't correct |
9 |
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 |
88 ms |
17528 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 |
11 ms |
14464 KB |
Output is correct |
3 |
Correct |
11 ms |
14464 KB |
Output is correct |
4 |
Correct |
12 ms |
14464 KB |
Output is correct |
5 |
Incorrect |
11 ms |
14464 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
11 ms |
14464 KB |
Output is correct |
2 |
Correct |
10 ms |
14464 KB |
Output is correct |
3 |
Correct |
12 ms |
14464 KB |
Output is correct |
4 |
Incorrect |
10 ms |
14464 KB |
Output isn't correct |
5 |
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 |
Correct |
11 ms |
14464 KB |
Output is correct |
4 |
Correct |
11 ms |
14464 KB |
Output is correct |
5 |
Correct |
11 ms |
14464 KB |
Output is correct |
6 |
Correct |
81 ms |
17252 KB |
Output is correct |
7 |
Correct |
105 ms |
19080 KB |
Output is correct |
8 |
Correct |
235 ms |
34428 KB |
Output is correct |
9 |
Correct |
224 ms |
34040 KB |
Output is correct |
10 |
Correct |
224 ms |
34168 KB |
Output is correct |
11 |
Correct |
222 ms |
35576 KB |
Output is correct |
12 |
Correct |
221 ms |
38904 KB |
Output is correct |
13 |
Correct |
222 ms |
43512 KB |
Output is correct |
14 |
Correct |
235 ms |
43384 KB |
Output is correct |
15 |
Correct |
11 ms |
14464 KB |
Output is correct |
16 |
Correct |
10 ms |
14464 KB |
Output is correct |
17 |
Correct |
11 ms |
14464 KB |
Output is correct |
18 |
Correct |
11 ms |
14464 KB |
Output is correct |
19 |
Correct |
11 ms |
14464 KB |
Output is correct |
20 |
Correct |
15 ms |
14592 KB |
Output is correct |
21 |
Correct |
96 ms |
17656 KB |
Output is correct |
22 |
Incorrect |
13 ms |
14464 KB |
Output isn't correct |
23 |
Halted |
0 ms |
0 KB |
- |