Submission #162035

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
162035	2019-11-06T03:23:51 Z	DifferentHeaven	Deda (COCI17_deda)	C++17	140 / 140	732 ms	9592 KB

deda

#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]

Subtask #1

140.0 / 140.0

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