#include <math.h>
#include <algorithm>
#include <cstdio>
#include <set>
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, inf};
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];
}
imam[x]=0;
prop[x]=0;
}
else if(imam2[x]){
if(prop2[x]<t[x].first){
t[x]={prop2[x], L};
}
if(x<pot){
imam2[x*2]=1;
prop2[x*2]=prop2[x];
imam2[x*2+1]=1;
prop2[x*2+1]=prop2[x];
}
imam2[x]=0;
prop2[x]=0;
}
}
void update(int x, pair < int, int > val){
t[x]=val;
// printf("update %d %d\n", val.first, val.second);
int x1=x;
int br=0;
while(x1<pot){
x1*=2;
br++;
}
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++;
}
}
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;
int l[maxn];
set < pair < int, int > > red;
int main(){
scanf("%d%d%d", &n, &k, &m);
int x;
for(int i=0; i<n; i++){
scanf("%d", &x);
x--;
l[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;
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[l[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[l[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[l[y]].resetiraj(y+pot);
s[z].update(y+pot, y);
l[y]=z;
if(y<n-1){
for(int j=0; j<k; j++){
red.insert({s[j].query(0, pot-1, 1, y+1, n-1, 0), j});
}
pa=*(--red.end());
// printf("pa %d %d\n", pa.first, pa.second);
if(pa.first!=inf){
T.update1(0, pot-1, 1, y+1, pa.first-1, inf, 1);
}
else{
T.update1(0, pot-1, 1, y+1, n-1, inf, 1);
}
while(!red.empty()){
pa=*(--red.end());
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));
red.erase(--red.end());
}
}
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:175: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:178:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
~~~~~^~~~~~~~~~
nekameleoni.cpp:209:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d", &x);
~~~~~^~~~~~~~~~
nekameleoni.cpp:211: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 |
126 ms |
105592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
224 ms |
105592 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
511 ms |
105720 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3093 ms |
106120 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3088 ms |
107192 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3092 ms |
106540 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3094 ms |
107000 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3075 ms |
107320 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3104 ms |
107512 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3069 ms |
107616 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
