Submission #52829

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
52829	2018-06-27T04:24:34 Z	polyfish	Deda (COCI17_deda)	C++14	140 / 140	129 ms	18388 KB

deda

//I love armpit fetish

#include <bits/stdc++.h>
using namespace std;
 
#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';
#define PR0(A, n) cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';
#define FILE_NAME "data"

const int INF = 1e9;

struct segmentTree {
	vector<int> st;
	int n;

	segmentTree(int _n) {
		n = _n;
		st.resize(4*n, INF);
	}

	void upd(int pos, int val, int l, int r, int id) {
		if (pos<l || pos>r)
			return;
		if (l==pos && pos==r) {
			st[id] = val;
			return;
		}
		int mid = (l + r) / 2;
		upd(pos, val, l, mid, id*2);
		upd(pos, val, mid+1, r, id*2+1);
		st[id] = min(st[id*2], st[id*2+1]);
	}

	int Find(int bound, int y, int l, int r, int id) {
		if (r<bound || st[id]>y)
			return -1;
		if (l==r)
			return l;
		int mid = (l + r) / 2;
		int tmp = Find(bound, y, l, mid, id*2);
		if (tmp>-1)
			return tmp;
		return Find(bound, y, mid+1, r, id*2+1);
	}

	void upd(int pos, int val) {
		upd(pos, val, 1, n, 1);
	}

	int Find(int b, int y) {
		return Find(b, y, 1, n, 1);
	}
};

void solve() {
	int n, nQuery;
	cin >> n >> nQuery;
	segmentTree tr(n);
	while (nQuery--) {
		char opt; 
		cin >> opt;
		if (opt=='M') {
			int x, a; 
			cin >> x >> a;
			tr.upd(a, x);
		}
		else {
			int y, b; 
			cin >> y >> b;
			cout << tr.Find(b, y) << '\n';
		}
	}
}

int main() {
	//freopen(FILE_NAME".inp", "r", stdin);
	//freopen(FILE_NAME".out", "w", stdout);
	ios::sync_with_stdio(0); cin.tie(0);
	solve();
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	256 KB	Output is correct
2	Correct	3 ms	492 KB	Output is correct
3	Correct	4 ms	604 KB	Output is correct
4	Correct	99 ms	8464 KB	Output is correct
5	Correct	124 ms	9660 KB	Output is correct
6	Correct	127 ms	14164 KB	Output is correct
7	Correct	129 ms	18388 KB	Output is correct