Submission #872007

#TimeUsernameProblemLanguageResultExecution timeMemory
872007vjudge1Deda (COCI17_deda)C++17
80 / 140
1045 ms28164 KiB
#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; 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; }

Compilation message (stderr)

deda.cpp:4: warning: ignoring '#pragma GCC optimze' [-Wunknown-pragmas]
    4 | #pragma GCC optimze("Ofast")
      |
#Verdict Execution timeMemoryGrader output
Fetching results...