Submission #876672

#	Time	Username	Problem	Language	Result	Execution time	Memory
876672		vjudge1	Deda (COCI17_deda)	C++17	20 / 140	91 ms	25224 KiB

deda

#include <bits/stdc++.h>
using namespace std;

#define ll long long int
#define F first
#define S second
#define pb push_back

const int N = 4 * (1e6 + 10), M = 1e6 + 10;
int seg[N], inf = 1e9, ans[N];
vector<pair<int, pair<int, pair<int, int>>>> v;

void upd(int id, int s, int e, int i, int x)
{
	if (i == s && i == e - 1)
	{
		seg[id] = min(seg[id], x);
		return;
	}
	if (i < s || i >= e)
		return;
	int mid = (s + e) / 2;
	upd(id * 2, s, mid, i, x);
	upd(id * 2 + 1, mid, e, i, x);
	seg[id] = min(seg[id * 2], seg[id * 2 + 1]);
}

int solve(int id, int l, int r, int s, int e)
{
	// cout << id << " " << s << " " << e << " " << i << "\n";
	if (l <= s && e <= r)
		return seg[id];
	if (r <= s || l >= e)
		return inf;
	int mid = (s + e) / 2;
	int x = solve(id * 2, l, r, s, mid);
	int y = solve(id * 2 + 1, l, r, mid, e);
	return min(min(x, y), inf);
}

int main()
{

	ios_base::sync_with_stdio(false),cin.tie(0);
	
	for (int i = 0; i < N; i ++)
		seg[i] = inf;
	int n, q;
	cin >> n >> q;
	vector<int> Q;
	for (int i= 1; i <= q; i ++)
	{
		char op;
		int x, y, tt = 10;
		cin >> op >> x >> y;
		if (op == 'D')
			tt = 20;
		v.pb({y, {-i, {tt, -x}}});
		if (op == 'D')
			Q.pb(i);
	}
	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());
// 	for (auto i : v)
// 	      cout << i.F <<" " << i.S.F << " " << i.S.S.F << " " << i.S.S.S << "\n";

	for (auto i : v)
	{
	      i.S.S.S *= (-1), i.S.F *= (-1);
		if (i.S.S.F == 10)
		{
			upd(1, 0, M, i.S.S.S, i.F);
			continue;
		}
		int tmp = solve(1, 1, i.S.S.S + 1, 0, M);
		ans[i.S.F] = tmp;
	}
	for (auto i : Q)
		cout << (ans[i] == inf ? -1 : ans[i]) << "\n";
	
	return 0;

}

• Subtask 1: 20 / 140