#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
#define N 200100
int pos[N], cnt=1;
int mval[4*N], mpos[4*N], l[4*N],r[4*N], sub[4*N];
void pd(int n) {
if(sub[n]) {
mval[n]-=sub[n];
if(l[n]!=r[n])
sub[n*2]+=sub[n],
sub[n*2+1]+=sub[n];
sub[n] = 0;
}
}
deque<int> R;
void upd(int n) {
if(mval[2*n]!=mval[2*n+1])
if(mval[2*n]>mval[2*n+1])
mval[n] = mval[2*n+1],
mpos[n] = mpos[2*n+1];
else mval[n] = mval[2*n],
mpos[n] = mpos[2*n];
else {
int dist = mpos[2*n+1]-mpos[2*n];
int dist2 = R.size() - dist;
if(dist>dist2)
mval[n] = mval[2*n+1],
mpos[n] = mpos[2*n+1];
else mval[n] = mval[2*n],
mpos[n] = mpos[2*n];
}
}
void build(int i, int lp, int rp) {
l[i] = lp, r[i] = rp;
if(lp==rp)
mval[i] = R[lp-1],
mpos[i] = lp;
else build(i*2,lp,lp+rp>>1),
build(i*2+1,lp+rp+2>>1,rp),
upd(i);
}
#define n R.size()
void update(int i, int rl, int rr, int v) {
pd(i);
if(rl<=l[i]&&r[i]<=rr)
return (void)(sub[i]-=v,pd(i));
if(rl<=r[i*2])
update(i*2,rl,rr,v);
if(r[i*2]<rr)
update(i*2+1,rl,rr,v);
pd(i*2);
pd(i*2+1);
upd(i);
}
int info[200100][3];
void init2(int k, vector<int> r) {
R.resize(r.size());
iota(R.begin(), R.end(), 0);
for(int i = 0; i < n; i++)
if(r[R[0]] == r[R[n-1]])
R.push_back(R[0]),R.pop_front(), info[i][2] = 1;
else
break;
info[R[0]][0] = 1;
info[R[0]][1] = r[R[0]];
for(int i = 1; i < n; i++) {
info[R[i]][1] = r[R[i]];
if(r[R[i]]!=r[R[i-1]]) {
info[R[i]][0] = ++cnt;
} else {
info[R[i]][0] = info[R[i-1]][0];
}
}
return;
}
void init(int k, vector<int> r) {
init2(k,r);
}
int compare_plants(int x, int y) {
if(abs(x-y)==1)
return (x<y?1:-1)*(info[min(x,y)][1]?1:-1);
if(abs(y-x)==n-1)
return (x<y^info[n][1])?1:-1;
if(info[x][0] != info[y][0])
return 0;
return (info[x][1]^info[x][2]^x>y)?1:-1;
}
Compilation message
plants.cpp: In function 'void build(int, int, int)':
plants.cpp:39:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
39 | else build(i*2,lp,lp+rp>>1),
| ~~^~~
plants.cpp:40:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
40 | build(i*2+1,lp+rp+2>>1,rp),
| ~~~~~^~
plants.cpp: In function 'void init2(int, std::vector<int>)':
plants.cpp:60:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
60 | for(int i = 0; i < n; i++)
| ^
plants.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(int i = 1; i < n; i++) {
| ^
plants.cpp: In function 'int compare_plants(int, int)':
plants.cpp:84:18: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
84 | return (x<y^info[n][1])?1:-1;
| ~^~
plants.cpp:83:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
83 | if(abs(y-x)==n-1)
| ^~
plants.cpp:85:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
85 | if(info[x][0] != info[y][0])
| ^~
plants.cpp:87:36: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
87 | return (info[x][1]^info[x][2]^x>y)?1:-1;
| ~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
