#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, 2> t[N * 4];
int psh[N * 4], n;
vector <pair <int, int> > gt[N];
vector <int> a;
set <int> g[N];
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;
}
void com(int v)
{
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)
{
if (tl == tr) t[v] = {a[tl], 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), 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 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);
int cur = n;
while (cur > 0)
{
vector <int> gr; gr.clear();
while (t[1][0] == 0)
{
gr.PB(t[1][1]);
upd(1, 0, n - 1, t[1][1]);
}
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, 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] << " ";
//}
# |
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 |
13 ms |
14464 KB |
Output is correct |
4 |
Correct |
12 ms |
14464 KB |
Output is correct |
5 |
Correct |
11 ms |
14464 KB |
Output is correct |
6 |
Correct |
75 ms |
17272 KB |
Output is correct |
7 |
Correct |
122 ms |
18936 KB |
Output is correct |
8 |
Correct |
269 ms |
34552 KB |
Output is correct |
9 |
Correct |
265 ms |
34168 KB |
Output is correct |
10 |
Correct |
262 ms |
34296 KB |
Output is correct |
11 |
Correct |
225 ms |
35576 KB |
Output is correct |
12 |
Correct |
227 ms |
38904 KB |
Output is correct |
13 |
Correct |
256 ms |
43384 KB |
Output is correct |
14 |
Correct |
236 ms |
43344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 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 |
Correct |
11 ms |
14464 KB |
Output is correct |
5 |
Correct |
11 ms |
14464 KB |
Output is correct |
6 |
Correct |
15 ms |
14464 KB |
Output is correct |
7 |
Correct |
103 ms |
17656 KB |
Output is correct |
8 |
Incorrect |
14 ms |
14464 KB |
Output isn't correct |
9 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 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 |
Correct |
11 ms |
14464 KB |
Output is correct |
5 |
Correct |
11 ms |
14464 KB |
Output is correct |
6 |
Correct |
15 ms |
14464 KB |
Output is correct |
7 |
Correct |
103 ms |
17656 KB |
Output is correct |
8 |
Incorrect |
14 ms |
14464 KB |
Output isn't correct |
9 |
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 |
Incorrect |
82 ms |
17400 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 |
12 ms |
14464 KB |
Output is correct |
3 |
Correct |
13 ms |
14464 KB |
Output is correct |
4 |
Correct |
11 ms |
14464 KB |
Output is correct |
5 |
Incorrect |
13 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 |
11 ms |
14464 KB |
Output is correct |
3 |
Correct |
10 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 |
13 ms |
14464 KB |
Output is correct |
4 |
Correct |
12 ms |
14464 KB |
Output is correct |
5 |
Correct |
11 ms |
14464 KB |
Output is correct |
6 |
Correct |
75 ms |
17272 KB |
Output is correct |
7 |
Correct |
122 ms |
18936 KB |
Output is correct |
8 |
Correct |
269 ms |
34552 KB |
Output is correct |
9 |
Correct |
265 ms |
34168 KB |
Output is correct |
10 |
Correct |
262 ms |
34296 KB |
Output is correct |
11 |
Correct |
225 ms |
35576 KB |
Output is correct |
12 |
Correct |
227 ms |
38904 KB |
Output is correct |
13 |
Correct |
256 ms |
43384 KB |
Output is correct |
14 |
Correct |
236 ms |
43344 KB |
Output is correct |
15 |
Correct |
10 ms |
14464 KB |
Output is correct |
16 |
Correct |
11 ms |
14464 KB |
Output is correct |
17 |
Correct |
12 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 |
14464 KB |
Output is correct |
21 |
Correct |
103 ms |
17656 KB |
Output is correct |
22 |
Incorrect |
14 ms |
14464 KB |
Output isn't correct |
23 |
Halted |
0 ms |
0 KB |
- |