oj.uz

Submission #872006

# Submission time Handle Problem Language Result Execution time Memory
872006 2023-11-12T06:18:30 Z vjudge1 Deda (COCI17_deda) C++17
80 / 140
 1000 ms 27944 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define len(x) (int) x.size()
#define pb push_back
mt19937 rnd(time(0));

struct query {
	char type;
	int a, b;
};

const int N = 2e5 + 7, SQ = 460, BLOCK = N / SQ + 7;
map<int, int> mp;
set<int> box[BLOCK], c[N];
vector<query> qu;
vector<int> vec;
int n, q;

void read_input() {
	cin >> n >> q;
	for (int i = 0; i < q; i++) {
		query t;
		cin >> t.type >> t.a >> t.b;
		vec.pb(t.a);
		qu.pb(t);
	}
}

void prepare() {
	sort(all(vec));
	vec.resize(unique(all(vec)) - vec.begin());
	for (int i = 0; i < len(vec); i++)
		mp[vec[i]] = i;
}

void solve() {
	for (int i = 0; i < q; i++) {
		char type = qu[i].type;
		int a = qu[i].a, b = qu[i].b;
		a = mp[a];
		if (type == 'M') {
			box[a / SQ].insert(b);
			c[a].insert(b);
		}
		else {
			int l = 0, r = a + 1, ans = INT_MAX;
			for (; l < r; ) {
				if (l % SQ || l + SQ > r) {
					if (c[l].empty() || *(--c[l].end()) < b) 
						l++;
					else {
						ans = min(ans, *c[l].lower_bound(b));
						l++;
					}
				}
				else {
					if (box[l / SQ].empty() || *(--box[l / SQ].end()) < b) 
						l += SQ;
					else {
						ans = min(ans, *box[l / SQ].lower_bound(b));
						l += SQ;
					}
				}
			}
			cout << (ans == INT_MAX? -1: ans) << '\n';
		}
	}
}

int32_t main() {
	ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
	read_input(), prepare(), solve();
	return 0;
}

Subtask #1
80.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9820 KB Output is correct
2 Correct 2 ms 9820 KB Output is correct
3 Correct 7 ms 10076 KB Output is correct
4 Correct 307 ms 21452 KB Output is correct
5 Execution timed out 1039 ms 27944 KB Time limit exceeded
6 Execution timed out 1016 ms 26136 KB Time limit exceeded
7 Execution timed out 1022 ms 25972 KB Time limit exceeded