Submission #528667

#	Time	Username	Problem	Language	Result	Execution time	Memory
528667		colazcy	Nekameleoni (COCI15_nekameleoni)	C++17	42 / 140	3075 ms	61036 KiB

nekameleoni

#include <cstdio>
#include <cassert>
#include <algorithm>
#include <set>
#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 = 52,inf = 0x3f3f3f3f;

int n,k,q,val[maxn];
namespace seg{
	#define ls (x << 1)
	#define rs (x << 1 | 1)
	
	bool same[maxn << 2];
	int val[maxn << 2][maxk],ans[maxn << 2];

	void build(const int l = 1,const int r = n + 1,const int x = 1){
		rep(i,1,k)val[x][i] = inf;
		same[x] = true;
		ans[x] = inf;
		if(l == r)return;
		let mid = (l + r) >> 1;
		build(l,mid,ls);
		build(mid + 1,r,rs);
	}
	void modify(const int a,const int b,const int id,const int v,const int l = 1,const int r = n + 1,const int x = 1){
		// debug("%d %d [%d %d] %d\n",a,b,l,r,x);
		if(l == r)assert(same[x]);
		if(same[x])
			if(a <= l && b >= r){
				val[x][id] = v;
				ans[x] = *std::max_element(val[x] + 1,val[x] + 1 + k) - r + 1;
				return;
			}
		assert(l != r);
		same[x] = false;
		let mid = (l + r) >> 1;
		if(a <= mid)modify(a,b,id,v,l,mid,ls);
		if(b > mid)modify(a,b,id,v,mid + 1,r,rs);
		ans[x] = std::min(ans[ls],ans[rs]);
	}
}
std::set<int> s[maxk];
void ins(const int id,const int p){
	auto &s = ::s[id];
	let nxt = *s.upper_bound(p);
	let pre = *std::prev(s.lower_bound(p));
	seg::modify(pre + 1,p,id,p);
	seg::modify(p + 1,std::min(nxt,n + 1),id,nxt);
	s.insert(p);
}
void del(const int id,const int p){
	auto &s = ::s[id];
	s.erase(p);
	let nxt = *s.upper_bound(p);
	let pre = *std::prev(s.lower_bound(p));
	seg::modify(pre + 1,std::min(nxt,n + 1),id,nxt);
}
int main(){
	// std::freopen("nekameleoni.in","r",stdin);
	// std::freopen("nekameleoni.out","w",stdout);
	std::scanf("%d %d %d",&n,&k,&q);
	seg::build();
	rep(i,1,k)
		s[i].insert(0),s[i].insert(inf);
	rep(i,1,n)std::scanf("%d",val + i),ins(val[i],i);
	repn(q){
		int opt; std::scanf("%d",&opt);
		if(opt == 1){
			int p,v; std::scanf("%d %d",&p,&v);
			del(val[p],p);
			ins(val[p] = v,p);
		}else if(opt == 2)std::printf("%d\n",seg::ans[1] > n ? -1  : seg::ans[1]);
	}
	std::fclose(stdin);
	std::fclose(stdout);
	return 0;
}

Compilation message (stderr)

nekameleoni.cpp: In function 'int main()':
nekameleoni.cpp:67:12: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |  std::scanf("%d %d %d",&n,&k,&q);
      |  ~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
nekameleoni.cpp:71:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |  rep(i,1,n)std::scanf("%d",val + i),ins(val[i],i);
      |            ~~~~~~~~~~^~~~~~~~~~~~~~
nekameleoni.cpp:73:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |   int opt; std::scanf("%d",&opt);
      |            ~~~~~~~~~~^~~~~~~~~~~
nekameleoni.cpp:75:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |    int p,v; std::scanf("%d %d",&p,&v);
      |             ~~~~~~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 14 / 14
• Subtask 4: 0 / 14
• Subtask 5: 0 / 14
• Subtask 6: 0 / 14
• Subtask 7: 0 / 14
• Subtask 8: 0 / 14
• Subtask 9: 0 / 14
• Subtask 10: 0 / 14