oj.uz

답안 #528661

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
528661 2022-02-21T02:11:45 Z colazcy Nekameleoni (COCI15_nekameleoni) C++17
42 / 140
 3000 ms 106636 KB 
#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 << 2];
	int lst[maxn << 2][maxk],fir[maxn << 2][maxk],ans[maxn << 2];
	
	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] = 1ull << 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[64],lsiz;
		static int rbuf[64],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] = 1ull << 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);
      |             ~~~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 45 ms 3532 KB Output is correct
2 Correct 20 ms 3616 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 128 ms 5452 KB Output is correct
2 Correct 93 ms 5604 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 235 ms 6908 KB Output is correct
2 Correct 187 ms 6860 KB Output is correct

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2925 ms 26928 KB Output is correct
2 Execution timed out 3079 ms 93812 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3076 ms 53560 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3078 ms 53584 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3072 ms 53920 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3100 ms 53648 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3088 ms 106612 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3097 ms 106636 KB Time limit exceeded
2 Halted 0 ms 0 KB -