oj.uz

Submission #34854

# Submission time Handle Problem Language Result Execution time Memory
34854 2017-11-16T08:09:45 Z szawinis Deda (COCI17_deda) C++14
40 / 140
 59 ms 9344 KB 
#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

# Verdict Execution time Memory 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)