답안 #34854

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
34854	2017-11-16T08:09:45 Z	szawinis	Deda (COCI17_deda)	C++14	40 / 140	59 ms	9344 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() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> q;
	fill(t+1, t+2*N, INT_MAX);
	for(int i = 0; i < q; i++) {
		cin >> 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 {
			cout << qseg(qq[i].a, n, qq[i].x) << endl;
		}
	}
}

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;
              ^

Subtask #1

40.0 / 140.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	9344 KB	Output is correct
2	Correct	0 ms	9344 KB	Output is correct
3	Runtime error	3 ms	9344 KB	Execution killed because of forbidden syscall writev (20)
4	Runtime error	59 ms	9344 KB	Execution killed because of forbidden syscall writev (20)
5	Runtime error	56 ms	9344 KB	Execution killed because of forbidden syscall writev (20)
6	Runtime error	39 ms	9344 KB	Execution killed because of forbidden syscall writev (20)
7	Runtime error	56 ms	9344 KB	Execution killed because of forbidden syscall writev (20)