Submission #306251

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
306251	2020-09-25T03:33:19 Z	colazcy	Deda (COCI17_deda)	C++17	140 / 140	157 ms	6904 KB

deda

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 2e5 + 100;
int n,q;
char com[4];
namespace st{
	#define ls (rt << 1)
	#define rs (rt << 1 | 1)
	int mi[maxn << 2];
	inline void pushup(int rt){
		mi[rt] = min(mi[ls],mi[rs]);
	}
	inline void build(int a = 1,int b = n,int rt = 1){
		if(a == b){
			mi[rt] = 0x7fffffff;
			return;
		}
		int mid = (a + b) >> 1;
		build(a,mid,ls);
		build(mid + 1,b,rs);
		pushup(rt);
	}
	inline void modify(int pos,int v,int l = 1,int r = n,int rt = 1){
		if(l == r){
			mi[rt] = v;
			return;
		}
		int mid = (l + r) >> 1;
		if(pos <= mid)modify(pos,v,l,mid,ls);
		else modify(pos,v,mid + 1,r,rs);
		pushup(rt);
	}
	inline int query(int a,int b,int v,int l = 1,int r = n,int rt = 1){
		if(l == r)return l;
		if(a <= l && b >= r && mi[rt] > v)return -1;
		int mid = (l + r) >> 1,res = -1;
		if(a <= mid && mi[ls] <= v){
			res = query(a,b,v,l,mid,ls);
			if(res != -1)return res;
		}
		if(b >= mid + 1 && mi[rs] <= v){
			res = query(a,b,v,mid + 1,r,rs);
			if(res != -1)return res;
		}
		return res;
	}
	#undef ls
	#undef rs
}
int main(){
//	freopen("deda.in","r",stdin);
//	freopen("deda.out","w",stdout);
	scanf("%d %d",&n,&q);
	st::build();
	while(q--){
		scanf("%s",com);
		int x,y;
		if(com[0] == 'M'){
			scanf("%d %d",&x,&y);
			st::modify(y,x);
		}else{
			scanf("%d %d",&x,&y);
			printf("%d\n",st::query(y,n,x));
		}
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}

Compilation message

deda.cpp: In function 'int main()':
deda.cpp:54:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |  scanf("%d %d",&n,&q);
      |  ~~~~~^~~~~~~~~~~~~~~
deda.cpp:57:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   57 |   scanf("%s",com);
      |   ~~~~~^~~~~~~~~~
deda.cpp:60:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |    scanf("%d %d",&x,&y);
      |    ~~~~~^~~~~~~~~~~~~~~
deda.cpp:63:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |    scanf("%d %d",&x,&y);
      |    ~~~~~^~~~~~~~~~~~~~~

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	1 ms	256 KB	Output is correct
3	Correct	3 ms	384 KB	Output is correct
4	Correct	140 ms	6904 KB	Output is correct
5	Correct	138 ms	5368 KB	Output is correct
6	Correct	150 ms	6708 KB	Output is correct
7	Correct	157 ms	6776 KB	Output is correct