oj.uz

Submission #42324

# Submission time Handle Problem Language Result Execution time Memory
42324 2018-02-26T06:02:41 Z milmillin Deda (COCI17_deda) C++14
100 / 140
 1000 ms 55228 KB 
#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;
};

void update (int idx,int val) {
	while (idx<200100) {
		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);
	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:49: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:54: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 10 ms 9956 KB Output is correct
3 Correct 19 ms 10576 KB Output is correct
4 Correct 464 ms 24476 KB Output is correct
5 Execution timed out 1068 ms 55228 KB Time limit exceeded
6 Execution timed out 1060 ms 55228 KB Time limit exceeded
7 Correct 951 ms 55228 KB Output is correct