#include <cstdio>
#include <cassert>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <vector>
#include <stack>
#define let const auto
#define rep(name,beg,end) for(auto lim_##name = end,name = beg;name <= lim_##name;name++)
#define per(name,beg,end) for(auto lim_##name = end,name = beg;name >= lim_##name;name--)
#define repn(lim) for(auto REPN_LIM = lim,REPN = 1;REPN <= REPN_LIM;REPN++)
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define trace() debug("Line : %d, Function : %s\n",__LINE__,__FUNCTION__)
using ull = unsigned long long;
// constexpr int maxn = 1e5 + 100;
constexpr int maxn = 1e5 + 10,maxk = 50,inf = 0x3f3f3f3f;
ull full;
int n,k,q,val[maxn];
namespace seg{
#define ls (x << 1)
#define rs (x << 1 | 1)
ull sum[maxn];
int lst[maxn][maxk],fir[maxn][maxk],ans[maxn];
extern void pushup(const int x,const int l,const int r);
void build(const int l = 1,const int r = n,const int x = 1){
if(l == r){
sum[x] = 1 << val[l];
rep(i,0,k - 1)
fir[x][i] = inf,lst[x][i] = -inf;
fir[x][val[l]] = lst[x][val[l]] = l;
ans[x] = (sum[x] == full ? 1 : inf);
return;
}
let mid = (l + r) >> 1;
build(l,mid,ls);
build(mid + 1,r,rs);
pushup(x,l,r);
}
ull query(const int a,const int b,const int l,const int r,const int x){
// debug("[%d,%d] [%d,%d]\n",a,b,l,r);
if(a <= l && b >= r)return sum[x];
ull res = 0;
let mid = (l + r) >> 1;
if(a <= mid)res |= query(a,b,l,mid,ls);
if(b > mid)res |= query(a,b,mid + 1,r,rs);
return res;
}
void pushup(const int x,const int l,const int r){
sum[x] = sum[ls] | sum[rs];
rep(i,0,k - 1)
fir[x][i] = std::min(fir[ls][i],fir[rs][i]),
lst[x][i] = std::max(lst[ls][i],lst[rs][i]);
ans[x] = std::min(ans[ls],ans[rs]);
static int lbuf[maxk],lsiz;
static int rbuf[maxk],rsiz;
lsiz = rsiz = 0;
rep(i,0,k - 1)
if(lst[ls][i] != -inf)lbuf[++lsiz] = lst[ls][i];
rep(i,0,k - 1)
if(fir[rs][i] != inf)rbuf[++rsiz] = fir[rs][i];
std::sort(lbuf + 1,lbuf + 1 + lsiz);
std::sort(rbuf + 1,rbuf + 1 + rsiz);
// debug("pushup : %d [%d %d]\n",x,l,r);
// rep(i,1,lsiz)debug("%d ",lbuf[i]);
// rep(i,1,rsiz)debug("%d ",rbuf[i]);
// debug("\n");
int rp = 1;
rep(lp,1,lsiz){
while(rp <= rsiz && query(lbuf[lp],rbuf[rp],l,r,x) != full)rp++;
if(rp == rsiz + 1)break;
ans[x] = std::min(ans[x],rbuf[rp] - lbuf[lp] + 1);
}
}
void modify(const int p,const int v,const int l = 1,const int r = n,const int x = 1){
if(l == r){
sum[x] = 1 << v;
fir[x][val[p]] = inf;
lst[x][val[p]] = -inf;
val[p] = v;
fir[x][v] = lst[x][v] = p;
ans[x] = sum[x] == full ? 1 : inf;
return;
}
let mid = (l + r) >> 1;
if(p <= mid)modify(p,v,l,mid,ls);
else modify(p,v,mid + 1,r,rs);
pushup(x,l,r);
}
#undef ls
#undef rs
}
int main(){
// std::freopen("nekameleoni.in","r",stdin);
// std::freopen("nekameleoni.out","w",stdout);
std::scanf("%d %d %d",&n,&k,&q);
full = (1ull << k) - 1;
rep(i,1,n)std::scanf("%d",val + i),val[i]--;
seg::build();
repn(q){
int opt; std::scanf("%d",&opt);
if(opt == 1){
int p,v; std::scanf("%d %d",&p,&v);
seg::modify(p,v - 1);
}else if(opt == 2)std::printf("%d\n",seg::ans[1] == inf ? -1 : seg::ans[1]);
}
std::fclose(stdin);
std::fclose(stdout);
return 0;
}
Compilation message
nekameleoni.cpp: In function 'int main()':
nekameleoni.cpp:99:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
99 | std::scanf("%d %d %d",&n,&k,&q);
| ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
nekameleoni.cpp:101:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | rep(i,1,n)std::scanf("%d",val + i),val[i]--;
| ~~~~~~~~~~^~~~~~~~~~~~~~
nekameleoni.cpp:104:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
104 | int opt; std::scanf("%d",&opt);
| ~~~~~~~~~~^~~~~~~~~~~
nekameleoni.cpp:106:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
106 | int p,v; std::scanf("%d %d",&p,&v);
| ~~~~~~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
44 ms |
3636 KB |
Output is correct |
| 2 |
Correct |
19 ms |
3664 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
102 ms |
5596 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
165 ms |
6960 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1924 ms |
27188 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
56 ms |
62500 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
52 ms |
62280 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
64 ms |
62664 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
81 ms |
62612 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
1596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
10 ms |
1556 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
