#include <math.h>
#include <algorithm>
#include <cstdio>
#include <set>
#include <queue>
using namespace std;
const int maxn=1e5+5, pot=131072;
const int inf=1e9;
int n, k, m;
struct tournament1{
pair < int, int > t[pot*2];
tournament1(){
for(int i=0; i<pot*2; i++){
t[i].first=inf;
t[i].second=-inf;
}
}
void update(int x, int val){
t[x]={val, val};
for(x/=2; x>0; x/=2){
t[x].first=min(t[x*2].first, t[x*2+1].first);
t[x].second=max(t[x*2].second, t[x*2+1].second);
}
}
void resetiraj(int x){
t[x]={inf, -inf};
for(x/=2; x>0; x/=2){
t[x].first=min(t[x*2].first, t[x*2+1].first);
t[x].second=max(t[x*2].second, t[x*2+1].second);
}
}
int query(int L, int D, int x, int l, int d, bool p){
if(L>=l && D<=d){
if(!p){
return t[x].first;
}
else{
return t[x].second;
}
}
int lijeva, desna;
if(!p){
lijeva=inf;
desna=inf;
}
else{
lijeva=-inf;
desna=-inf;
}
if((L+D)/2>=l){
lijeva=query(L, (L+D)/2, x*2, l, d, p);
}
if((L+D)/2+1<=d){
desna=query((L+D)/2+1, D, x*2+1, l, d, p);
}
if(!p){
return min(lijeva, desna);
}
else{
return max(lijeva, desna);
}
}
};
struct tournament2{
pair < int, int > t[pot*2];
int prop[pot*2];
int prop2[pot*2];
bool imam[pot*2], imam2[pot*2];
tournament2(){
for(int i=0; i<pot*2; i++){
t[i]={-inf, i};
imam[i]=0;
imam2[i]=0;
}
}
void propagate(int x, int L){
if(imam[x]){
t[x]={prop[x], L};
if(x<pot){
imam[x*2]=1;
prop[x*2]=prop[x];
imam[x*2+1]=1;
prop[x*2+1]=prop[x];
}
imam2[x*2]=0;
imam2[x*2+1]=0;
imam[x]=0;
prop[x]=0;
}
else if(imam2[x]){
if(prop2[x]<=t[x].first){
t[x]={prop2[x], L};
}
if(x<pot){
if(imam2[x*2]){
prop2[x*2]=min(prop2[x*2], prop2[x]);
}
else{
prop2[x*2]=prop2[x];
imam2[x*2]=1;
}
if(imam2[x*2+1]){
prop2[x*2+1]=min(prop2[x*2+1], prop2[x]);
}
else{
prop2[x*2+1]=prop2[x];
imam2[x*2+1]=1;
}
imam[x*2]=0;
imam[x*2+1]=0;
}
imam2[x]=0;
prop2[x]=0;
}
}
void update(int x, pair < int, int > val){
// printf("update %d %d\n", val.first, val.second);
int x1=x;
int br=0;
while(x1<pot){
x1*=2;
br++;
}
// printf("granice %d %d\n", x1-pot, x1-pot+(1<<(br+1))-1);
propagate(x, x1-pot);
t[x]=val;
for(x/=2; x>0; x/=2){
propagate(x*2, x1-pot);
propagate(x*2+1, x1-pot+(1<<br));
if(t[x*2].second-t[x*2].first>t[x*2+1].second-t[x*2+1].first){
t[x]=t[x*2+1];
}
else{
t[x]=t[x*2];
}
br++;
}
// printf("a sad je: %d %d\n", t[1].first, t[1].second);
}
void update1(int L, int D, int x, int l, int d, int val, bool p){
propagate(x, L);
if(L>=l && D<=d){
if(p){
update(x, {val, L});
if(x<pot){
propagate(x*2, L);
propagate(x*2+1, (L+D)/2+1);
prop[x*2]=val;
imam[x*2]=1;
prop[x*2+1]=val;
imam[x*2+1]=1;
}
}
else{
// printf("updateam %d %d %d %d\n", L, D, val, t[x].first);
if(val<=t[x].first){
// printf("in\n");
update(x, {val, L});
}
if(x<pot){
propagate(x*2, L);
propagate(x*2+1, (L+D)/2+1);
prop2[x*2]=val;
imam2[x*2]=1;
prop2[x*2+1]=val;
imam2[x*2+1]=1;
}
}
return;
}
if((L+D)/2>=l){
update1(L, (L+D)/2, x*2, l, d, val, p);
}
if((L+D)/2+1<=d){
update1((L+D)/2+1, D, x*2+1, l, d, val, p);
}
}
};
tournament1 s[50];
tournament2 T;
queue < pair < int, int > > red;
int main(){
int lis[maxn];
scanf("%d%d%d", &n, &k, &m);
int x;
for(int i=0; i<n; i++){
scanf("%d", &x);
x--;
lis[i]=x;
s[x].update(i+pot, i);
// printf("%d\n", s[x].t[1].first);
}
int mini;
bool p;
for(int i=0; i<n; i++){
mini=1e9;
p=1;
for(int j=0; j<k; j++){
x=s[j].query(0, pot-1, 1, 0, i, 1);
// printf("%d ", x);
if(x==-1){
p=0;
break;
}
mini=min(mini, x);
}
// printf("\n");
if(p){
// printf("updateam\n");
T.update(i+pot, {mini, i});
}
}
int y, z;
// int iduci;
// int sad;
pair < int, int > pa;
int naj;
for(int i=0; i<m; i++){
scanf("%d", &x);
if(x==1){
scanf("%d%d", &y, &z);
y--;
z--;
/* if(y==n-1){
iduci=n;
}
else{
iduci=s[lis[y]].query(0, pot-1, 1, y+1, n-1, 0);
}
if(iduci==inf){
iduci=n;
}
iduci--;
if(y==0){
y=-1;
}
else{
sad=s[lis[y]].query(0, pot-1, 1, 0, y-1, 1);
}
// printf("%d %d\n", iduci, sad);
T.update1(0, pot-1, 1, sad+1, iduci, sad, 0);*/
// printf("prosao\n");
s[lis[y]].resetiraj(y+pot);
// printf("kaj %d\n", lis[y]);
s[z].update(y+pot, y);
lis[y]=z;
// printf("sumnjivo %d\n", s[1].t[2+pot].first);
if(y<n-1){
naj=0;
for(int j=0; j<k; j++){
pa={s[j].query(0, pot-1, 1, y+1, n-1, 0), j};
red.push(pa);
naj=max(naj, pa.first);
}
// printf("pa %d\n", naj);
if(naj!=inf){
T.update1(0, pot-1, 1, y+1, naj-1, inf, 1);
}
else{
T.update1(0, pot-1, 1, y+1, n-1, inf, 1);
}
while(!red.empty()){
pa=red.front();
red.pop();
if(pa.first==inf){
// printf("USAAAO\n");
T.update1(0, pot-1, 1, y+1, n-1, s[pa.second].query(0, pot-1, 1, 0, y, 1), 0);
}
else{
if(pa.first-1>=y+1){
T.update1(0, pot-1, 1, y+1, pa.first-1, s[pa.second].query(0, pot-1, 1, 0, y, 1), 0);
}
}
// printf("na %d %d %d\n", pa.first, pa.second, s[pa.second].query(0, pot-1, 1, 0, y, 1));
}
}
T.update1(0, pot-1, 1, y, y, inf, 1);
for(int j=0; j<k; j++){
T.update1(0, pot-1, 1, y, y, s[j].query(0, pot-1, 1, 0, y, 1), 0);
// printf("sad %d %d\n", j, s[j].query(0, pot-1, 1, 0, y, 1));
}
}
else{
// printf("%d %d\n", T.t[1].first, T.t[1].second);
// printf("%d %d\n", T.t[3+pot].first, T.t[3+pot].second);
if(T.t[1].first==-inf){
printf("%d\n", -1);
}
else{
printf("%d\n", T.t[1].second-T.t[1].first+1);
}
}
}
return 0;
}
Compilation message
nekameleoni.cpp: In function 'int main()':
nekameleoni.cpp:192:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &n, &k, &m);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
nekameleoni.cpp:195:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
~~~~~^~~~~~~~~~
nekameleoni.cpp:227:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
~~~~~^~~~~~~~~~
nekameleoni.cpp:229:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &y, &z);
~~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
149 ms |
105592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
233 ms |
105592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
374 ms |
105720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2782 ms |
106412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3061 ms |
107040 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3065 ms |
106776 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3077 ms |
107000 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3055 ms |
106936 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3075 ms |
107640 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3087 ms |
107640 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
