#include "plants.h"
#include<bits/stdc++.h>
using namespace std;
int perm[200010];
queue<int>kolejka;
set<int>zera;
int n, k;
bool dodane[200010];
int nast(int val){
if(zera.size()==0)return -1;
if(zera.upper_bound(val)==zera.end()){
return *zera.begin();
}
return *zera.upper_bound(val);
}
void rozpatrz(int val){
if(val==-1)return;
if(dodane[val])return;
if(zera.lower_bound(val)==zera.begin()){
int pom = *zera.rbegin();
if(val - pom+n > k-1){
kolejka.push(val);
dodane[val] = 1;
}
return;
}
else{
auto it = zera.lower_bound(val);
it--;
int pom =*it;
if(val-pom > k-1){
kolejka.push(val);
dodane[val] = 1;
}
}
}
const int base = 1<<18;
int mini[2*base];
int lazy[2*base];
void push(int w){
if(!lazy[w])return;
mini[w*2]+=lazy[w];
lazy[w*2]+=lazy[w];
mini[w*2+1]+=lazy[w];
lazy[w*2+1]+=lazy[w];
mini[w] = min(mini[w*2], mini[w*2+1]);
lazy[w] = 0;
}
void dodaj(int w, int l, int p, int a, int b, int val){
if(b<l || p<a)return;
if(a<=l && p<=b){
mini[w]+=val;
lazy[w]+=val;
return;
}
push(w);
dodaj(w*2, l, (l+p)/2, a, b, val);
dodaj(w*2+1, (l+p)/2+1, p, a, b, val);
mini[w] = min(mini[w*2], mini[w*2+1]);
}
void odejmij(int l, int p){
l = (l+n)%n, p = (p+n)%n;
if(l<=p)
dodaj(1, 0, base-1, l, p, -1);
else{
dodaj(1, 0, base-1, l, n-1, -1);
dodaj(1, 0, base-1, 0, p, -1);
}
}
int znajdz(int w){
if(w>=base){
if(mini[w]==0)return w-base;
else return -1;
}
if(mini[w]>0)return -1;
push(w);
int pom = znajdz(w*2);
if(pom==-1)pom = znajdz(w*2+1);
else znajdz(w*2+1);
mini[w] = min(mini[w*2], mini[w*2+1]);
return pom;
}
pair<int, long long> prawo[200010][17], lewo[200010][17];
int skacz_prawo(int start, int odl){
if(prawo[start][0].second==0)return start;
if(odl<prawo[start][0].second)return start;
return skacz_prawo(prawo[start][0].first, odl-prawo[start][0].second);
}
int skacz_lewo(int start, int odl){
if(lewo[start][0].second==0)return start;
if(odl<lewo[start][0].second)return start;
return skacz_lewo(prawo[start][0].first, odl-prawo[start][0].second);
}
void init(int K, std::vector<int> r) {
n = r.size();
int i;
k = K;
//odzyskaj permutacje
for(i=0;i<n;i++)
if(r[i]==0)
zera.insert(i);
for(auto j: zera){
rozpatrz(j);
}
for(i=0;i<base;i++){
if(i>=n || r[i]==0)
dodaj(1, 0, base-1, i, i, 1000000000);
else
dodaj(1, 0, base-1, i, i, r[i]);
}
int numer = n-1;
while(kolejka.size()){
auto x = kolejka.front();
// printf("%d:\n", x);
kolejka.pop();
perm[x] = numer--;
zera.erase(x);
odejmij(x-k+1, x-1);
vector<int>nowe_zera;
while(mini[1]==0){
int j = znajdz(1);
// printf("%d\n", j);
dodaj(1, 0, base-1, j, j, 1000000000);
// for(i=1;i<2*base;i++)printf("%d-%d ", mini[i], lazy[i]);printf("\n");
// printf("drzewo\n");
// exit(0);
zera.insert(j);
nowe_zera.push_back(j);
}
for(auto j: nowe_zera)
rozpatrz(j);
rozpatrz(nast(x));
// for(auto j: nowe_zera)printf("%d ", j);
// printf("\nKONIEC %d\n", x);
}
// for(i=0;i<n;i++)printf("%d ", perm[i]);printf("\n");
//skok w prawo
for(i=0;i<n;i++){
int bestval = -1;
prawo[i][0] = {i, 0};
for(int j=1;j<k;j++)
if(perm[(i+j)%n]>bestval && perm[(i+j)%n]<perm[i]){
prawo[i][0] = {(i+j)%k, j};
bestval = perm[(i+j)%k];
}
}
//skok w lewo
for(i=0;i<n;i++){
int bestval = -1;
lewo[i][0] = {i, 0};
for(int j=1;j<k;j++)
if(perm[(n+i-j)%n]>bestval && perm[(n+i-j)%n]<perm[i]){
lewo[i][0] = {(n+i-j)%k, j};
bestval = perm[(n+i-j)%k];
}
}/*
printf("PRAWO: ");for(i=0;i<n;i++)
printf("%d " ,prawo[i][0].first);printf("\n");
printf("LEWO: ");for(i=0;i<n;i++)
printf("%d " ,lewo[i][0].first);printf("\n");*/
return;
}
int compare_plants(int x, int y) {
int odl, z;
//w prawo od x
odl = (n+y-x)%n;
z = skacz_prawo(x, odl);
if((n+y-z)%n<k && perm[z]>=perm[y])return 1;
//w lowe od x
odl = (n+x-y)%n;
z = skacz_lewo(x, odl);
if((n+z-y)%n<k && perm[z]>=perm[y])return 1;
swap(x, y);
//w prawo od x
odl = (n+y-x)%n;
// printf("odl: %d\n", odl);
z = skacz_prawo(x, odl);
if((n+y-z)%n<k && perm[z]>=perm[y])return -1;
//w lowe od x
odl = (n+x-y)%n;
// printf("odl: %d\n", odl);
z = skacz_lewo(x, odl);
if((n+z-y)%n<k && perm[z]>=perm[y])return -1;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
5836 KB |
Output is correct |
| 2 |
Execution timed out |
4059 ms |
5892 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
5968 KB |
Output is correct |
| 2 |
Execution timed out |
4066 ms |
5716 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
5968 KB |
Output is correct |
| 2 |
Execution timed out |
4066 ms |
5716 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
38 ms |
5968 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
38 ms |
5980 KB |
Output is correct |
| 2 |
Execution timed out |
4094 ms |
5888 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
5968 KB |
Output is correct |
| 2 |
Execution timed out |
4066 ms |
5716 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
52 ms |
5836 KB |
Output is correct |
| 2 |
Execution timed out |
4059 ms |
5892 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
