제출 #410669

#제출 시각아이디문제언어결과실행 시간메모리
410669dynam1c다리 (APIO19_bridges)C++17
0 / 100
1 ms460 KiB
//#pragma comment(linker, "/stack:200000000") //#pragma GCC optimize("Ofast") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include <bits/stdc++.h> using namespace std; typedef long long ll; #define endl "\n" #define all(c) (c).begin(),(c).end() // when you ponder, divide and conquer struct RMQ { int n; vector<int> seg; RMQ(vector<int> arr) : n(arr.size()), seg(2*n) { for (int i = 0; i < n; i++) seg[i+n] = arr[i]; for (int i = n-1; i > 0; i--) seg[i] = min(seg[i<<1], seg[i<<1|1]); } int query(int l, int r) { int acc = INT_MAX; for (l += n, r += n; l != r; l >>= 1, r >>= 1) { if (l&1) acc = min(acc, seg[l++]); if (r&1) acc = min(acc, seg[--r]); } return acc; } void update(int i, int x) { for (seg[i += n] = x; i > 1; i >>= 1) seg[i>>1] = min(seg[i], seg[i^1]); } }; constexpr int L = 16; signed main() { // freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); std::ios::sync_with_stdio(false); cin.tie(0); assert(0 == 1); int n, m, q; cin >> n >> m; vector<int> ws(m); for (int i = 0; i < m; i++) { int x, y; cin >> x >> y >> ws[i]; } cin >> q; RMQ rmq(ws); for (int qq = 0; qq < q; qq++) { int t, x, y; cin >> t >> x >> y; x--; if (t == 1) { rmq.update(x, y); } else { int l = x, r = x; for (int i = L-1; i >= 0; i--) { int d = 1<<i; if (r+d <= n and rmq.query(x, r+d) >= y) r += d; if (l-d >= 0 and rmq.query(l-d, x) >= y) l -= d; } cout << r-l+1 << endl; } } } /* --- PSolving --- * Simplifying (getting rid of variables, conditions, code logic, etc.) * Reframing * Solving a subtask (subgoal, aux. problem, removing a condition or fixing a parameter, etc.) * Inducing * Divide and conquer * Working backwards * Visual intuition * !! Reductions don't have to be specializations, they can be generalizations */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...