Submission #34865

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
34865	2017-11-16T09:19:03 Z	szawinis	Deda (COCI17_deda)	C++14	0 / 140	83 ms	9184 KB

deda

#include <bits/stdc++.h>
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("%d%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:8:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l+r >> 1;
              ^
deda.cpp: In function 'int qflow(int, int)':
deda.cpp:31:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l+r >> 1;
              ^
deda.cpp: In function 'int main()':
deda.cpp:59:45: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'char*' [-Wformat=]
   scanf("%d%d%d",&qq[i].tp,&qq[i].x,&qq[i].a);
                                             ^
deda.cpp:56: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:59:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&qq[i].tp,&qq[i].x,&qq[i].a);
                                              ^

Subtask #1

0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	0 ms	9184 KB	Output isn't correct
2	Incorrect	0 ms	9184 KB	Output isn't correct
3	Incorrect	0 ms	9184 KB	Output isn't correct
4	Incorrect	73 ms	9184 KB	Output isn't correct
5	Incorrect	73 ms	9184 KB	Output isn't correct
6	Incorrect	83 ms	9184 KB	Output isn't correct
7	Incorrect	79 ms	9184 KB	Output isn't correct