답안 #162035

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
162035 2019-11-06T03:23:51 Z DifferentHeaven Deda (COCI17_deda) C++17
140 / 140
732 ms 9592 KB
#include <bits/stdc++.h>
#define ii pair <int, int>
#define x first
#define y second
#define db(x) cerr << #x << " = " << x << endl;
#define _ << " _ " <<

using namespace std;

const int N = 2e5 + 7;
const int oo = 1e9 + 7;

int n, m;

struct segTree{
	int tree[N << 3];

	segTree() {
		for (int i = 0; i < (N << 3); i++)
			tree[i] = oo;
	}

	void Update(int x, int l, int r, int i, int j, int val){
		if (l > j || r < i) return;
		if (l >= i && r <= j){
			tree[x] = val;
			return;
		}
		int mid = l + r >> 1;
		Update(2 * x, l, mid, i, j, val);
		Update(2 * x + 1, mid + 1, r, i, j, val);
		tree[x] = min(tree[2 * x], tree[2 * x + 1]);
	}

	int Find(int x, int l, int r, int i, int j, int val){
		if (l > j || r < i) return -1;

		if (l >= i && r <= j){
			while (l < r){
				int mid = l + r >> 1;
				if (tree[2 * x] <= val){
					r = mid;
					x = 2 * x;
				}
				else{
					l = mid + 1;
					x = 2 * x + 1;
				}
			}
			if (tree[x] <= val) return r;
			return -1;
		}

		int mid = l + r >> 1;
		int L = Find(2 * x, l, mid, i, j, val);
		if (L != -1) return L;
		int R = Find(2 * x + 1, mid + 1, r, i, j, val);
		return R;
	}
}IT;

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);

	cin >> n >> m;

	for (int i = 1; i <= m; i++){
		char ch;
		int x, y;

		cin >> ch >> x >> y;
		if (ch == 'M'){
			IT.Update(1, 1, n, y, y, x);
		}
		else{
			cout << IT.Find(1, 1, n, y, n, x) << endl;
		}
	}
}

Compilation message

deda.cpp: In member function 'void segTree::Update(int, int, int, int, int, int)':
deda.cpp:29:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
             ~~^~~
deda.cpp: In member function 'int segTree::Find(int, int, int, int, int, int)':
deda.cpp:40:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
deda.cpp:54:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int mid = l + r >> 1;
             ~~^~~
deda.cpp: In function 'int main()':
deda.cpp:66:60: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin), freopen("test.out", "w", stdout);
                             ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
deda.cpp:66:60: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 6520 KB Output is correct
2 Correct 9 ms 6520 KB Output is correct
3 Correct 21 ms 6648 KB Output is correct
4 Correct 732 ms 8928 KB Output is correct
5 Correct 500 ms 9208 KB Output is correct
6 Correct 556 ms 9436 KB Output is correct
7 Correct 598 ms 9592 KB Output is correct