#include "plants.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <utility>
#define pii pair<int, int>
#define piii pair<int, pii>
#define pll pair<long long, long long>
#define plll pair<long long, pll>
#define ff first
#define ss second
#define ee ss.ff
#define rr ss.ss
using namespace std;
struct Node
{
pii mn, lazy;
}seg[808080];
void prop(int ind)
{
Node &x = seg[ind << 1], &y = seg[ind << 1 | 1], &nd = seg[ind];
if(nd.lazy.ff)
{
x.mn.ff += nd.lazy.ff;
y.mn.ff += nd.lazy.ff;
x.lazy.ff += nd.lazy.ff;
y.lazy.ff += nd.lazy.ff;
nd.lazy.ff = 0;
}
if(nd.lazy.ss)
{
x.mn.ss += nd.lazy.ss;
y.mn.ss += nd.lazy.ss;
x.lazy.ss += nd.lazy.ss;
y.lazy.ss += nd.lazy.ss;
nd.lazy.ss = 0;
}
}
void mrge(int ind)
{
seg[ind].mn = min(seg[ind << 1].mn, seg[ind << 1 | 1].mn);
}
void init_seg(vector<int> &r, int ind, int s, int e)
{
if(s + 1 == e)
{
seg[ind].mn = {r[s], 0};
seg[ind].lazy = {0, 0};
return;
}
int mid = s + e >> 1;
init_seg(r, ind << 1, s, mid);
init_seg(r, ind << 1 | 1, mid, e);
mrge(ind);
}
void upd1(int ind, int s, int e, int l, int r, int x)
{
if(e <= l || r <= s) return;
if(l <= s && e <= r)
{
seg[ind].mn.ff += x;
seg[ind].lazy.ff += x;
return;
}
prop(ind);
int mid = s + e >> 1;
upd1(ind << 1, s, mid, l, r, x);
upd1(ind << 1 | 1, mid, e, l, r, x);
mrge(ind);
}
void upd2(int ind, int s, int e, int l, int r)
{
if(e <= l || r <= s) return;
if(l <= s && e <= r)
{
++seg[ind].mn.ss;
++seg[ind].lazy.ss;
return;
}
prop(ind);
int mid = s + e >> 1;
upd2(ind << 1, s, mid, l, r);
upd2(ind << 1 | 1, mid, e, l, r);
mrge(ind);
}
void qr1(vector<int> &ret, int ind, int s, int e, int l, int r)
{
if(e <= l || r <= s || seg[ind].mn.ff) return;
if(s + 1 == e)
{
ret.push_back(s);
return;
}
prop(ind);
int mid = s + e >> 1;
qr1(ret, ind << 1, s, mid, l, r);
qr1(ret, ind << 1 | 1, mid, e, l, r);
}
int qr2(int ind, int s, int e)
{
if(s + 1 == e) return s;
prop(ind);
int mid = s + e >> 1;
if(seg[ind << 1].mn == pii{0, 0}) return qr2(ind << 1, s, mid);
else return qr2(ind << 1 | 1, mid, e);
}
int N, K;
int ord[202020];
void init(int k, vector<int> r)
{
N = r.size(); K = k;
init_seg(r, 1, 0, N);
for(int i = 0; i < N; ++i)
{
int t = qr2(1, 0, N);
ord[t] = i;
vector<int> ls;
if(t >= K - 1)
{
upd1(1, 0, N, t - K + 1, t, -1);
upd1(1, 0, N, t, t + 1, N);
qr1(ls, 1, 0, N, t - K + 1, t);
}
else
{
upd1(1, 0, N, 0, t, -1);
upd1(1, 0, N, N - K + t + 1, N, -1);
upd1(1, 0, N, t, t + 1, N);
qr1(ls, 1, 0, N, 0, t);
qr1(ls, 1, 0, N, N - K + t + 1, N);
}
for(int j : ls)
{
if(j <= N - K) upd2(1, 0, N, j + 1, j + K);
else
{
upd2(1, 0, N, j + 1, N);
upd2(1, 0, N, 0, K - N + j);
}
}
}
// for(int i = 0; i < N; ++i)
// {
// for(int j = 0; j < N; ++j)
// {
// for(int k = 0; k < N; ++k)
// {
// if(arr[j][i] && arr[i][k]) arr[j][k] = true;
// }
// }
// }
// for(int i = 0; i < N; ++i)
// {
// for(int j = 0; j < N; ++j)
// {
// cout << arr[i][j];
// }
// cout << endl;
// }
}
int compare_plants(int x, int y)
{
if(ord[x] < ord[y]) return 1;
else return -1;
}
Compilation message
plants.cpp: In function 'void init_seg(std::vector<int>&, int, int, int)':
plants.cpp:58:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
58 | int mid = s + e >> 1;
| ~~^~~
plants.cpp: In function 'void upd1(int, int, int, int, int, int)':
plants.cpp:75:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
75 | int mid = s + e >> 1;
| ~~^~~
plants.cpp: In function 'void upd2(int, int, int, int, int)':
plants.cpp:92:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
92 | int mid = s + e >> 1;
| ~~^~~
plants.cpp: In function 'void qr1(std::vector<int>&, int, int, int, int, int)':
plants.cpp:108:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
108 | int mid = s + e >> 1;
| ~~^~~
plants.cpp: In function 'int qr2(int, int, int)':
plants.cpp:118:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
118 | int mid = s + e >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
256 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
256 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
256 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
256 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Incorrect |
73 ms |
3320 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
256 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
256 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
256 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
256 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
256 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
