Submission #42328

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
42328	2018-02-26T06:07:38 Z	milmillin	Deda (COCI17_deda)	C++14	100 / 140	1000 ms	49140 KB

deda

#include <cstdio>
#include <algorithm>
#include <set>
#include <map>
#include <vector>

using namespace std;

set<int> bit[200100];
map<int,int> comp;

struct query {
	char x;
	int a,b;
};

int mxx;

void update (int idx,int val) {
	while (idx<mxx) {
		bit[idx].insert(val);
		//printf("++ %d\n",idx);
		//for (auto &i:bit[idx]) {
			//printf("%d ",i);
		//}
		//printf("\n");
		idx+=(idx&-idx);
	}
}

int get (int idx,int val) {
	int ans=2e9;
	while (idx) {
		auto it = bit[idx].lower_bound(val);
		//printf("## %d\n",idx);
		//for (auto &i:bit[idx]) {
			//printf("%d ",i);
		//}
		//printf("\n");
		if (it!=bit[idx].end()) {
			//printf("*** %d\n",*it);
			ans = min(ans,*it);
		}
		idx-=(idx&-idx);
	}
	return ans;
}

int main () {
	int n,q;
	scanf("%d%d",&n,&q);
	mxx=q+1000;
	char x;
	int a,b;
	vector<query> qq;
	for (int i=0;i<q;i++) {
		scanf(" %c%d%d",&x,&a,&b);
		comp[a];
		qq.push_back(query{x,a,b});
	}
	int cnt=1;
	for (auto &i:comp) {
		i.second = cnt++;
	}
	for (auto &i:qq) {
		i.a=comp[i.a];
		//printf("-- %d %d\n",i.a,i.b);
		if (i.x=='M') {
			update(i.a,i.b);
		} else {
			int tmp = get(i.a,i.b);
			printf("%d\n",(tmp==2e9)?-1:tmp);
		}
	}
	return 0;
}

Compilation message

deda.cpp: In function 'int main()':
deda.cpp:51: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:57: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

100.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	9720 KB	Output is correct
2	Correct	9 ms	9824 KB	Output is correct
3	Correct	14 ms	10280 KB	Output is correct
4	Correct	428 ms	21060 KB	Output is correct
5	Execution timed out	1071 ms	49140 KB	Time limit exceeded
6	Execution timed out	1022 ms	49140 KB	Time limit exceeded
7	Correct	903 ms	49140 KB	Output is correct