oj.uz

답안 #528667

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
528667 2022-02-21T03:13:07 Z colazcy Nekameleoni (COCI15_nekameleoni) C++17
42 / 140
 3000 ms 61036 KB 
#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

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.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 2124 KB Output is correct
2 Correct 248 ms 2224 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 3276 KB Output is correct
2 Correct 607 ms 3300 KB Output is correct

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 3916 KB Output is correct
2 Correct 1463 ms 4020 KB Output is correct

Subtask #4
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 552 ms 15240 KB Output is correct
2 Execution timed out 3075 ms 52608 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 851 ms 30932 KB Output is correct
2 Execution timed out 3066 ms 60136 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1166 ms 30392 KB Output is correct
2 Execution timed out 3072 ms 59436 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1169 ms 31672 KB Output is correct
2 Execution timed out 3062 ms 59720 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #8
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1241 ms 31564 KB Output is correct
2 Execution timed out 3059 ms 59944 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #9
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1598 ms 60820 KB Output is correct
2 Execution timed out 3052 ms 60476 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #10
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1584 ms 61036 KB Output is correct
2 Execution timed out 3057 ms 60596 KB Time limit exceeded
3 Halted 0 ms 0 KB -