Submission #871988

#TimeUsernameProblemLanguageResultExecution timeMemory
871988vjudge1Deda (COCI17_deda)C++17
0 / 140
113 ms2240 KiB
/* IN THE NAME OF GOD */ // Oh, let the bullets fly, oh, let them rain #include <bits/stdc++.h> using namespace std; const int MAXN = 200'000, sq = 450, inf = 1'000'000'010; int out[MAXN + 10], mn_sq[sq + 10], n, q; void input(); void solve(); void query1(int x, int a); int query2(int y, int b); int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); input(); solve(); return 0; } void input() { cin >> n >> q; } void solve() { for (int i = 0; i < n; i++) out[i] = inf; for (int i = 0; i < sq; i++) mn_sq[i] = inf; while (q--) { char type; int k1, k2; cin >> type >> k1 >> k2; k2--; if (type == 'M') query1(k1, k2); else cout << query2(k1, k2) << '\n'; } } void query1(int x, int a) { int idx = a / sq; for (int i = idx; i < sq; i++) mn_sq[i] = min(mn_sq[i], x); out[a] = x; } int query2(int y, int b) { int tmp = inf, ptr1 = b; while (ptr1 % sq && ptr1 < n) { tmp = min(tmp, out[ptr1]); if (tmp <= y) return ptr1 + 1; ptr1++; } for (int i = b / sq + 1; i <= n / sq; i++) { tmp = min(tmp, mn_sq[i]); if (tmp <= y) { int res = inf; if (i) res = min(res, mn_sq[i - 1]); for (int j = i * sq; j < min((i + 1) * sq, n); j++) { res = min(res, out[j]); if (res <= y) return j + 1; } } } return -1; }
#Verdict Execution timeMemoryGrader output
Fetching results...