oj.uz

Submission #229654

# Submission time Handle Problem Language Result Execution time Memory
229654 2020-05-05T17:47:52 Z vee_nits123 Deda (COCI17_deda) C++14
0 / 140
 465 ms 19500 KB 
#include <iostream>
#include <climits>
#include <cstring>

using namespace std;

#define int long long int
#define endl '\n'

const int N = 2e5 + 5;
const int M = 1e9 + 1;
int tree[4 * N];

void update(int ind, int val, int st, int end, int pos) {
	//if (st > end || ind > end || ind < st) return ;
	if (st == end && st == ind) {
		tree[pos] = val;
		return ;
	}
	int mid = (st + end) / 2;
	if(ind<=mid)
		update(ind, val, st, mid, 2 * pos);
	else
		update(ind, val, mid + 1, end, 2 * pos + 1);
	tree[pos] = min(tree[2 * pos], tree[2 * pos + 1]);
	return ;
}

int query(int l, int r, int val, int st, int end, int pos) {

	if (st == l && r == end && l == r)
		return l;
	int mid = (st + end) / 2;
	int a = -1, b = -1;
	if (tree[2 * pos] <= val && l <= mid) {
		a = query(l, min(mid, r), val, st, mid, 2 * pos);
	}
	if (a == -1 && tree[2 * pos + 1] <= val && r > mid) {
		b = query(max(l, mid + 1), r, val, mid + 1, end, 2 * pos + 1);
	}
	return a == -1 ? b : (b == -1 ? a : min(a, b));
}

int32_t main() {

	ios_base:: sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	// code starts

	//int t;cin>>t;while(t--){}

	fill(tree, tree + 4 * N, M);

	int n, q; cin >> n >> q;
	while (q--) {
		char x;
		int val, ind; cin >> x >> val >> ind;
		if (x == 'M') {
			update(ind, val, 1, n, 1);
		}
		else {
			cout << query(ind, n, val, 1, n, 1) << endl;
		}
	}


	return 0;
}

Compilation message

deda.cpp: In function 'int32_t main()':
deda.cpp:50:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("input.txt", "r", stdin);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
deda.cpp:51:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  freopen("output.txt", "w", stdout);
  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 421 ms 19324 KB Output isn't correct
2 Incorrect 429 ms 19320 KB Output isn't correct
3 Incorrect 428 ms 19500 KB Output isn't correct
4 Incorrect 427 ms 19268 KB Output isn't correct
5 Incorrect 465 ms 19336 KB Output isn't correct
6 Incorrect 425 ms 19320 KB Output isn't correct
7 Incorrect 421 ms 19320 KB Output isn't correct