oj.uz

Submission #528691

# Submission time Handle Problem Language Result Execution time Memory
528691 2022-02-21T06:19:00 Z colazcy Nekameleoni (COCI15_nekameleoni) C++17
140 / 140
 2473 ms 105608 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 + 10,maxk = 50,inf = 0x3f3f3f3f;

ull full;
int n,k,q,val[maxn];
namespace seg{
	#define ls (x << 1)
	#define rs (x << 1 | 1)
	int lst[maxn << 2][maxk],fir[maxn << 2][maxk],ans[maxn << 2];
	
	void pushup(const int x){
		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);

		ull lt = 0,rt = 1ull << val[rbuf[1]];
		rep(i,1,lsiz)lt |= 1ull << val[lbuf[i]];
		int rp = 1;
		rep(lp,1,lsiz){
			while(rp < rsiz && (lt | rt) != full)
				rt |= 1ull << val[rbuf[++rp]];
			// if(rp == rsiz + 1)break;
			if((lt | rt) == full)ans[x] = std::min(ans[x],rbuf[rp] - lbuf[lp] + 1);
			lt ^= 1ull << val[lbuf[lp]];
		}
	}
	void build(const int l = 1,const int r = n,const int x = 1){
		if(l == r){
			rep(i,0,k - 1)
				fir[x][i] = inf,lst[x][i] = -inf;
			fir[x][val[l]] = lst[x][val[l]] = l;
			ans[x] = (k == 1 ? 1 : inf);	
			return;
		}
		let mid = (l + r) >> 1;
		build(l,mid,ls);
		build(mid + 1,r,rs);
		pushup(x);	
	}

	void modify(const int p,const int v,const int l = 1,const int r = n,const int x = 1){
		if(l == r){
			fir[x][val[p]] = inf;
			lst[x][val[p]] = -inf;
			val[p] = v;
			fir[x][v] = lst[x][v] = p;
			ans[x] = k == 1 ? 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);
	}
	#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:86:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |  std::scanf("%d %d %d",&n,&k,&q);
      |  ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
nekameleoni.cpp:88:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |  rep(i,1,n)std::scanf("%d",val + i),val[i]--;
      |            ~~~~~~~~~~^~~~~~~~~~~~~~
nekameleoni.cpp:91:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |   int opt; std::scanf("%d",&opt);
      |            ~~~~~~~~~~^~~~~~~~~~~
nekameleoni.cpp:93:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |    int p,v; std::scanf("%d %d",&p,&v);
      |             ~~~~~~~~~~^~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 3532 KB Output is correct
2 Correct 10 ms 3532 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 5276 KB Output is correct
2 Correct 34 ms 5340 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 6752 KB Output is correct
2 Correct 75 ms 6836 KB Output is correct

Subtask #4
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 712 ms 26820 KB Output is correct
2 Correct 2185 ms 92356 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1063 ms 53080 KB Output is correct
2 Correct 2283 ms 105580 KB Output is correct

Subtask #6
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1559 ms 53060 KB Output is correct
2 Correct 2360 ms 105552 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1792 ms 53396 KB Output is correct
2 Correct 2364 ms 105532 KB Output is correct

Subtask #8
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1806 ms 53620 KB Output is correct
2 Correct 2379 ms 105608 KB Output is correct

Subtask #9
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2169 ms 105540 KB Output is correct
2 Correct 2473 ms 105556 KB Output is correct

Subtask #10
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2220 ms 105588 KB Output is correct
2 Correct 2372 ms 105580 KB Output is correct