oj.uz

답안 #34865

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
34865 2017-11-16T09:19:03 Z szawinis Deda (COCI17_deda) C++14
0 / 140
 83 ms 9184 KB 
#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

# 결과 실행 시간 메모리 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