Paste #1ll -- näytä pelkkänä tekstinä -- uusi tämän pohjalta
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | #include <iostream> using namespace std; #define N (1<<18) #define A 1222333444 int t[2*N]; void muuta(int k, int x) { k += N; t[k] = x; for (k /= 2; k >= 1; k /= 2) { t[k] = min(t[2*k],t[2*k+1]); } } int pienin(int a, int b) { a += N; b += N; int p = A; while (a <= b) { if (a%2 == 1) p = min(p,t[a++]); if (b%2 == 0) p = min(p,t[b--]); a /= 2; b /= 2; } return p; } int n, q; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> q; for (int i = 0; i < 2*N; i++) t[i] = A; while (q--) { string x; int a, b; cin >> x >> a >> b; if (x == "M") { muuta(b,a); } else { if (t[b+N] <= a) { cout << b << "\n"; continue; } int k = b; for (int z = (n-k)/2+1; z >= 1; z /= 2) { while (k+z <= n && pienin(k,k+z) > a) k += z; } if (k == n) cout << "-1\n"; else cout << k+1 << "\n"; } } } |