Submission #872022

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
872022	2023-11-12T06:33:22 Z	vjudge1	Deda (COCI17_deda)	C++17	140 / 140	143 ms	6100 KB

deda

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

#pragma GCC optimze("Ofast")
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;
int n, q, box[BLOCK], c[N];
map<int, int> mp;
vector<query> qu;
vector<int> vec;

void read_input() {
	cin >> n >> q;
	for (int i = 0; i < q; i++) {
		query t;
		cin >> t.type >> t.a >> t.b;
		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 < BLOCK; i++)
		box[i] = INT_MAX;
	for (int i = 0; i < N; i++)
		c[i] = INT_MAX;
	for (int i = 0; i < q; i++) {
		char type = qu[i].type;
		int a = qu[i].a, b = qu[i].b;
		if (type == 'M') {
			box[b / SQ] = min(box[b / SQ], a);
			c[b] = a;
		}
		else {
			int ans = INT_MAX;
			int l = b, r = n;
			for (; l < r; ) {
				if (l % SQ || l + SQ > r) {
					if (c[l] <= a) {
						ans = l;
						break;
					}
					else
						l++;
				}
				else {
					if (box[l / SQ] <= a) {
						for (int j = l; j < l + SQ; j++)
							if (c[j] <= a) {
								ans = j;
								break;
							}
						break;
					}
					l += SQ;
				}
			}
			cout << (ans == INT_MAX? -1: ans + 1) << '\n';
		}
	}
}

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

Compilation message

deda.cpp:4: warning: ignoring '#pragma GCC optimze' [-Wunknown-pragmas]
    4 | #pragma GCC optimze("Ofast")
      |

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	1112 KB	Output is correct
2	Correct	1 ms	1116 KB	Output is correct
3	Correct	2 ms	1440 KB	Output is correct
4	Correct	143 ms	5592 KB	Output is correct
5	Correct	56 ms	5324 KB	Output is correct
6	Correct	64 ms	5588 KB	Output is correct
7	Correct	75 ms	6100 KB	Output is correct