Submission #34867

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
34867	2017-11-16T09:20:56 Z	szawinis	Deda (COCI17_deda)	C++14	140 / 140	333 ms	9184 KB

deda

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N = 1 << 18;

pair<int,int> get_range(int i) {
	int l = 0, r = N-1;
	for(int j = 31 - __builtin_clz(i) - 1; j >= 0; j--) {
		int mid = l+r >> 1;
		if(i >> j & 1) l = mid+1;
		else r = mid;
	}
	return make_pair(l, r);
}

struct query {
	char tp;
	int x, a, i;
	bool operator<(const query& rhs) { return x < rhs.x; }
};

int n, q, t[2*N], res[N];
query qq[N];

void update(int i, int v) {
	for(t[i += N] = v; i > 1; i >>= 1) t[i>>1] = min(t[i], t[i^1]);
}

int qflow(int i, int k) {
	int l, r; tie(l, r) = get_range(i);
	while(i < N) {
		int mid = l+r >> 1;
		if(t[i<<1] <= k) {
			r = mid;
			i = i << 1;
		} else {
			l = mid+1;
			i = i << 1 | 1;
		}
	}
	return (t[i] <= k ? l : INT_MAX);
}

int qseg(int l, int r, int k) {
	int res = INT_MAX;
	vector<int> ls;
	++r;
	for(l += N, r += N; l < r; l >>= 1, r >>= 1) {
		if(l & 1) ls.push_back(l++);
		if(r & 1) ls.push_back(--r);
	}
	for(int i: ls) if(t[i] <= k) res = min(qflow(i, k), res);
	return (res == INT_MAX ? -1 : res);
}

int main() {
	scanf("%d %d", &n, &q);
	fill(t+1, t+2*N, INT_MAX);
	for(int i = 0; i < q; i++) {
		scanf(" %c %d %d",&qq[i].tp,&qq[i].x,&qq[i].a);
	}
	for(int i = 0; i < q; i++) {
		char tp = qq[i].tp;
		if(tp == 'M') {
			update(qq[i].a, qq[i].x);
		} else {
			printf("%d\n", qseg(qq[i].a, n, qq[i].x));
		}
	}
}

Compilation message

deda.cpp: In function 'std::pair<int, int> get_range(int)':
deda.cpp:9:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l+r >> 1;
              ^
deda.cpp: In function 'int qflow(int, int)':
deda.cpp:32:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l+r >> 1;
              ^
deda.cpp: In function 'int main()':
deda.cpp:57:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &q);
                        ^
deda.cpp:60:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c %d %d",&qq[i].tp,&qq[i].x,&qq[i].a);
                                                 ^

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	9184 KB	Output is correct
2	Correct	0 ms	9184 KB	Output is correct
3	Correct	0 ms	9184 KB	Output is correct
4	Correct	249 ms	9184 KB	Output is correct
5	Correct	273 ms	9184 KB	Output is correct
6	Correct	299 ms	9184 KB	Output is correct
7	Correct	333 ms	9184 KB	Output is correct