Submission #42333

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
42333	2018-02-26T07:13:29 Z	milmillin	Deda (COCI17_deda)	C++14	140 / 140	169 ms	3920 KB

deda

#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

int seg[600100];

void update(int idx,int l,int r,int k,int val) {
	if (k<l||k>=r) return;
	if (l+1==r) {
		seg[idx]=val;
		return;
	}
	int m = (l+r)>>1;
	update(idx*2,l,m,k,val);
	update(idx*2+1,m,r,k,val);
	seg[idx]=min(seg[idx*2],seg[idx*2+1]);
	//printf("++ %d %d %d\n",l,r,seg[idx]);
}

int get(int idx,int l,int r,int ll,int rr,int k) {
	//printf("gg %d %d %d %d %d %d\n",l,r,ll,rr,k,seg[idx]);
	if (ll>=r||rr<=l) return 2e9;
	if (l+1==r) return (seg[idx]<=k)?l:2e9;
	if (ll<=l&&rr>=r&&seg[idx]>k) return 2e9;
	int m = (l+r)>>1;
	if (ll>=m) {
		return get(idx*2+1,m,r,ll,rr,k);
	} else if (rr<=m) {
		return get(idx*2,l,m,ll,rr,k);
	} else {
		int tmp = get(idx*2,l,m,ll,rr,k);
		if (tmp!=2e9) return tmp;
		return get(idx*2+1,m,r,ll,rr,k);
		//return min(get(idx*2,l,m,ll,rr,k),get(idx*2+1,m,r,ll,rr,k));
		//if (seg[idx*2]<=k) return get(idx*2,l,m,ll,rr,k);
		//else if (seg[idx*2+1]<=k) return get(idx*2+1,m,r,ll,rr,k);
		//else return 2e9;
	}
}

int main () {
	int n,q;
	scanf("%d%d",&n,&q);
	memset(seg,63,sizeof(seg));
	char x;
	int a,b;
	for (int i=0;i<q;i++) {
		scanf(" %c%d%d",&x,&a,&b);
		if (x=='M') {
			update(1,1,n+1,b,a);
		} else {
			int tmp = get(1,1,n+1,b,n+1,a);
			printf("%d\n",(tmp==2e9)?-1:tmp);
		}
	}
	
	return 0;
}

Compilation message

deda.cpp: In function 'int main()':
deda.cpp:45:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&q);
                     ^
deda.cpp:50:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c%d%d",&x,&a,&b);
                            ^

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	2552 KB	Output is correct
2	Correct	3 ms	2656 KB	Output is correct
3	Correct	5 ms	2728 KB	Output is correct
4	Correct	164 ms	3816 KB	Output is correct
5	Correct	169 ms	3816 KB	Output is correct
6	Correct	159 ms	3832 KB	Output is correct
7	Correct	160 ms	3920 KB	Output is correct