#include "plants.h"
#include<bits/stdc++.h>
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)
#define st first
#define nd second
using namespace std;
const int N=(1<<18);
int lazy[2*N];
pair<int, int> maks[2*N];
void prop1(int v){
if(!lazy[v] || v>N)return;
int l=2*v, r=l+1;
lazy[l]+=lazy[v];
lazy[r]+=lazy[v];
maks[l].st+=lazy[v];
maks[r].st+=lazy[v];
lazy[v]=0;
}
void add(int v, int l, int r ,int L, int R, int c){
//if(v==1)cout<<"a"<<l<<" "<<r<<" "<<c<<"\n";
//cout<<v<<" "<<l<<" "<<r<<" "<<L<<" "<<R<<"\n";
if(l==L && r==R){
lazy[v]+=c;
maks[v].st+=c;
return;
}
prop1(v);
int M=(L+R)>>1;
if(l<=M)add(2*v, l, min(M, r), L, M, c);
if(r>M)add(2*v+1, max(M+1, l), r, M+1, R, c);
maks[v]=max(maks[2*v], maks[2*v+1]);
return;
}
pair<int, int> quer1(int v, int l, int r, int L, int R){
if(l==L && r==R){
return maks[v];
}
int M=(L+R)>>1;
prop1(v);
pair<int, int> ans=mp(0, 0);
if(l<=M)ans=max(ans, quer1(2*v, l, min(M, r), L, M));
if(r>M)ans=max(ans, quer1(2*v+1, max(M+1, l), r, M+1, R));
return ans;
}
int lazy2[2*N];
pair<int, int> ma[2*N];
void prop2(int v){
if(!lazy2[v] || v>N)return;
int l=2*v, r=l+1;
lazy2[l]+=lazy2[v];
lazy2[r]+=lazy2[v];
ma[l].st+=lazy2[v];
ma[r].st+=lazy2[v];
lazy2[v]=0;
}
void add2(int v, int l, int r ,int L, int R, int c){
//if(v==1)cout<<"b"<<l<<" "<<r<<" "<<c<<"\n";
//cout<<"c"<<"\n";
if(l==L && r==R){
lazy2[v]+=c;
ma[v].st+=c;
return;
}
prop2(v);
int M=(L+R)>>1;
if(l<=M)add2(2*v, l, min(M, r), L, M, c);
if(r>M)add2(2*v+1, max(M+1, l), r, M+1, R, c);
ma[v]=max(ma[2*v], ma[2*v+1]);
return;
}
pair<int, int> quer2(int v, int l, int r, int L, int R){
if(l==L && r==R){
return ma[v];
}
int M=(L+R)>>1;
prop2(v);
pair<int, int> ans=mp(0, 0);
if(l<=M)ans=max(ans, quer2(2*v, l, min(M, r), L, M));
if(r>M)ans=max(ans, quer2(2*v+1, max(M+1, l), r, M+1, R));
return ans;
}
void check(int k, int n){
while(maks[1].st==k){
//cout<<"b\n";
int v=1;
while(v<N){
prop1(v);
if(maks[2*v].st==k)v*=2;
else v=2*v+1;
}
add(1, v-N, v-N, 0, N-1, -N);
add2(1, v-N, v-N, 0, N-1, N);
if(v-N<n-1)add2(1, v-N+1, min(v-N+k, n-1), 0, N-1, -1);
if(v-N+k>=n)add2(1, 0, v-N+k-n, 0, N-1, -1);
}
}
vector<int> V, V2;
vector<bitset<N> > b;
int n;
void addbit(int l, int r, bitset<N> c){
for(l+=n, r+=n; l<r; l>>=1, r>>=1){
if(l&1)b[l++]|=c;
if(r&1)b[--r]|=c;
}
}
void comp(int x){
if(x==1)comp(x/2);
b[x]|=b[x/2];
}
vector<bitset<N>> ans;
void init(int k, std::vector<int> r) {
n=r.size();
k--;
V.resize(n);
for(int i=0; i<n; i++){
ma[N+i].nd=-i;
maks[N+i].st=r[i];
maks[N+i].nd=-i;
}
for(int i=N-1; i>0; i--){
ma[i]=max(ma[2*i], ma[2*i+1]);
maks[i]=max(maks[2*i], maks[2*i+1]);
}
vector<int> S;
b.resize(2*n);
ans.resize(n);
for(int i=0; i<n; i++){
//cout<<"a\n";
check(k, n);
while(ma[1].st==N){
S.push_back(-ma[1].nd);
add2(1, -ma[1].nd, -ma[1].nd, 0, N-1, -N);
//cout<<"+";
}
int j=S[i];
//cout<<j<<"\n";
comp(j+n);
V[j]=i;
b[j+n][j]=1;
ans[j]=b[j+n];
assert(ans[j].count()==i+1);
//for(int l=0; l<n; l++)cout<<ans[j][l];
//cout<<"\n";
pair<int, int> u=mp(0,0);
if(j<n-1){
add2(1, j+1, min(j+k, n-1), 0, N-1, 1);
addbit(j+1, min(j+k, n-1)+1, ans[j]);
//u=max(u, quer2(1, j+1, min(j+k, n-1), 0, N-1));
}
if(j+k>=n){
add2(1, 0, j+k-n, 0, N-1, 1);
addbit(0, j+k-n+1, ans[j]);
//u=max(u, quer2(1, 0, j+k-n, 0, N-1));
}
/*if(u.st==N){
b[-u.nd]|=b[j];
cout<<-u.nd<<"x\n";
}*/
u=mp(0, 0);
if(j){
add(1, max(j-k, 0), j-1, 0, N-1, 1);
addbit(max(j-k, 0), j, ans[j]);
//u=max(u, quer1(1, max(j-k, 0), j-1, 0, N-1));
}
if(j-k<0){
add(1, n+j-k, n-1, 0, N-1, 1);
addbit(n+j-k, n, ans[j]);
//u=max(u, quer1(1, n+j-k, n-1, 0, N-1));
}
/*if(u.st==k){
b[-u.nd]|=b[j];
cout<<-u.nd<<"y\n";
}*/
}
return;
}
int compare_plants(int x, int y){
if(ans[x][y])return 1;
if(ans[y][x])return -1;
return 0;
}
Compilation message
In file included from /usr/include/c++/9/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:33,
from plants.cpp:2:
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:142:30: warning: comparison of integer expressions of different signedness: 'std::size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
142 | assert(ans[j].count()==i+1);
| ~~~~~~~~~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4556 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4684 KB |
Output is correct |
| 3 |
Correct |
4 ms |
4812 KB |
Output is correct |
| 4 |
Runtime error |
10 ms |
10160 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4556 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4684 KB |
Output is correct |
| 3 |
Correct |
4 ms |
4940 KB |
Output is correct |
| 4 |
Correct |
5 ms |
4940 KB |
Output is correct |
| 5 |
Runtime error |
26 ms |
28364 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4556 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4684 KB |
Output is correct |
| 3 |
Correct |
4 ms |
4940 KB |
Output is correct |
| 4 |
Correct |
5 ms |
4940 KB |
Output is correct |
| 5 |
Runtime error |
26 ms |
28364 KB |
Execution killed with signal 6 |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
9804 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4636 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4688 KB |
Output is correct |
| 3 |
Runtime error |
10 ms |
9932 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4556 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4684 KB |
Output is correct |
| 3 |
Runtime error |
10 ms |
9804 KB |
Execution killed with signal 6 |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
4556 KB |
Output is correct |
| 2 |
Correct |
4 ms |
4684 KB |
Output is correct |
| 3 |
Correct |
4 ms |
4812 KB |
Output is correct |
| 4 |
Runtime error |
10 ms |
10160 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
