#include <iostream>
#include <cstdio>
#include <math.h>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
#include <array>
using namespace std;
const int maxn=1e5+5, Log=17, pot=(1<<Log);
const int inf=1e9;
struct tournament1{
pair < int, int > t[pot*2];
tournament1(){
for(int i=0; i<pot*2; i++){
t[i]={inf, -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 reset(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].second;
}
else{
return t[x].first;
}
}
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 max(lijeva, desna);
}
else{
return min(lijeva, desna);
}
}
};
struct tournament2{
pair < int, int > t[pot*2];
pair < int, int > t1[pot*2];
int prop[pot*2];
bool jesam[pot*2];
tournament2(){
for(int i=0; i<pot*2; i++){
t[i]={-inf, inf};
t1[i]={inf, -inf};
}
}
void propagate(int x, int L){
if(jesam[x]){
t[x]={prop[x], L};
t1[x]={prop[x], prop[x]};
if(x<pot){
jesam[x*2]=1;
jesam[x*2+1]=1;
prop[x*2]=prop[x];
prop[x*2+1]=prop[x];
}
jesam[x]=0;
}
}
void update(int x, pair < int, int > val){
int br=0, x1=x;
while(x1<pot){
x1*=2;
br++;
}
// cout << "Update " << x-pot << " " << val.first << endl;
propagate(x, x1-pot);
t[x]=val;
t1[x]={val.first, val.first};
for(x/=2; x>0; x/=2){
propagate(x*2, x1-pot);
propagate(x*2+1, x1-pot+(1<<br));
t1[x].first=min(t1[x*2].first, t1[x*2+1].first);
t1[x].second=max(t1[x*2].second, t1[x*2+1].second);
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){
propagate(x, L);
if(L>=l && D<=d){
update(x, {val, L});
if(x<pot){
prop[x*2]=val;
prop[x*2+1]=val;
jesam[x*2]=1;
jesam[x*2+1]=1;
}
return;
}
if((L+D)/2>=l){
update1(L, (L+D)/2, x*2, l, d, val);
}
if((L+D)/2+1<=d){
update1((L+D)/2+1, D, x*2+1, l, d, val);
}
}
int query(int val){
int x=1;
int L=0;
int br=16;
propagate(1, L);
// cout << "Query\n";
while(x<pot){
propagate(x*2, L);
propagate(x*2+1, L+(1<<br));
// cout << t1[x].second << endl;
if(t1[x*2].second>val){
x*=2;
}
else{
x=x*2+1;
L+=(1<<br);
}
br--;
}
return x-pot;
}
};
tournament1 s[50];
tournament2 T;
int l[maxn];
set < pair < int, int > > red;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, m, k;
cin >> n >> k >> m;
for(int i=0; i<n; i++){
cin >> l[i];
l[i]--;
s[l[i]].update(i+pot, i);
}
int x, y, z;
int mini;
bool p;
for(int i=0; i<n; i++){
mini=inf;
p=1;
for(int j=0; j<k; j++){
x=s[j].query(0, pot-1, 1, 0, i, 1);
if(x==-inf){
p=0;
break;
}
mini=min(mini, x);
}
if(p){
// cout << "update " << i << endl;
T.update(i+pot, {mini, i});
}
}
int prosli, iduci;
int neki;
pair < int, int > pa;
for(int i=0; i<m; i++){
cin >> x;
if(x==1){
cin >> y >> z;
y--;
z--;
if(y==n-1){
prosli=n;
}
else{
prosli=s[l[y]].query(0, pot-1, 1, y+1, n-1, 0);
}
if(prosli==inf){
prosli=n;
}
prosli--;
if(y-1==-1){
iduci=-inf;
}
else{
iduci=s[l[y]].query(0, pot-1, 1, 0, y-1, 1);
}
neki=T.query(iduci);
// cout << neki << " " << prosli << " " << iduci << '\n';
if(neki<prosli){
T.update1(0, pot-1, 1, neki, prosli, iduci);
}
s[l[y]].reset(y+pot);
s[z].update(y+pot, y);
l[y]=z;
if(y!=n-1){
prosli=s[z].query(0, pot-1, 1, y+1, n-1, 0);
if(prosli==inf){
prosli=n;
}
prosli--;
for(int j=0; j<k; j++){
red.insert({s[j].query(0, pot-1, 1, 0, y, 1), s[j].query(0, pot-1, 1, y+1, prosli, 0)-1});
}
iduci=y+1;
while(!red.empty()){
pa=*red.begin();
red.erase(red.begin());
if(pa.second==inf-1){
pa.second=prosli;
}
if(pa.second>=iduci){
T.update1(0, pot-1, 1, iduci, pa.second, pa.first);
iduci=pa.second+1;
}
}
}
mini=inf;
for(int j=0; j<k; j++){
mini=min(mini, s[j].query(0, pot-1, 1, 0, y, 1));
}
T.update1(0, pot-1, 1, y, y, mini);
}
else{
// cout << T.t[1].first << " " << T.t[1].second << '\n';
if(T.t[1].first==-inf){
cout << -1 << '\n';
}
else{
cout << T.t[1].second-T.t[1].first+1 << '\n';
}
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
122 ms |
107256 KB |
Output is correct |
| 2 |
Correct |
108 ms |
107128 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
181 ms |
107128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
295 ms |
107256 KB |
Output is correct |
| 2 |
Correct |
291 ms |
107128 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1958 ms |
107768 KB |
Output is correct |
| 2 |
Execution timed out |
3094 ms |
108280 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3045 ms |
108540 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3093 ms |
107808 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3091 ms |
108384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3077 ms |
108164 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3091 ms |
108536 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3085 ms |
108636 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
