제출 #410243

#제출 시각아이디문제언어결과실행 시간메모리
410243yoavL다리 (APIO19_bridges)C++14
0 / 100
21 ms3268 KiB
#include <iostream> #include <vector> #include <algorithm> #include <string> #include <set> #include <unordered_set> #include <map> #include <unordered_map> #include <queue> #include <stack> #include <bitset> #include <math.h> #include <fstream> #include <iomanip> using namespace std; using ll = long long; using ld = long double; using vll = vector<ll>; using vvll = vector<vll>; using vvvll = vector<vvll>; using vvvvll = vector<vvvll>; using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>; using vld = vector<ld>; using vvld = vector<vld>; using vstr = vector<string>; using pll = pair<ll, ll>; using vpll = vector<pll>; using vvpll = vector<vpll>; using pb = pair<bool, bool>; using vpb = vector<pb>; using vvpb = vector<vpb>; using vi = vector<int>; using vvi = vector<vi>; const ll mod = (ll)1e9 + 7; const ll inf = (ll)1e18; #define FAST ios_base::sync_with_stdio(0) #define FASTIN cin.tie(0) #define FASTOUT cout.tie(0) #define upmin(a, b) a = min(a, b) #define upmax(a, b) a = max(a, b) #define pr(x) cout << x << endl; #define prv(v) cout << #v << ": "; for(auto it = v.begin(); it != v.end(); ++it) cout << *it << " "; cout << endl; #define prvv(v) for(auto it : v) { for(auto it2 : it) cout << it2 << " "; cout << endl; } cout << endl; #define wpr(x) cout << #x << " = " << (x) << endl; #define wprv(v) cout << #v << ": " << endl; for(auto it : v) cout << *it << " "; cout << endl; #define wprvv(v) cout << #v << ": " << endl; for(auto it : v) { for(auto it2 : it) cout << it2 << " "; cout << endl; } cout << endl; #define rep(i,s,e) for(ll i = s; i < e; i++) #define all(x) x.begin(),x.end() #define pb push_back ll n, m, q; vll arr; struct SEG { vll a; ll sz; const ll bval = 1e18; // ll f(ll a, ll b) // { return min(a, b); } SEG() {} SEG(ll n) { for (sz = 1; sz < n; sz <<= 1); a.resize(2 * sz, bval); } void make(ll n) { for (sz = 1; sz < n; sz <<= 1); a.resize(2 * sz, bval); } void up(ll ind, ll nval) { ind += sz; a[ind] = nval; for (ind >>= 1; ind; ind >>= 1) a[ind] = f(a[ind * 2], a[ind * 2 + 1]); } ll query(ll l, ll r) { l += sz, r += sz; ll res = bval; while (l <= r) { if (l % 2 == 1) res = f(res, a[l++]); if (r % 2 == 0) res = f(res, a[r--]); l >>= 1, r >>= 1; } return res; } }; void solve() { cin >> n >> m; arr.resize(n-1); rep(i, 0, m) { ll xt, yt, dt; cin >> xt >> yt >> dt; arr[i] = dt; } SEG seg; seg.make(n-1); rep(i, 0, n-1) { seg.up(i, arr[i]); } cin >> q; while (q--) { ll type; cin >> type; if (type == 1) { ll i, v; cin >> i >> v; seg.up(i, v); } else { ll w, s; cin >> w >> s; ll ans = 1; { ll low = 0, high = s-1, mid; ll res = s; while (low <= high) { mid = (low + high) / 2; ll v = seg.query(mid, s); if (w <= v) { // ok upmin(res, mid-1); high = mid - 1; } else { low = mid + 1; } } ans += s - res; } { ll low = s, high = n-2, mid; ll res = s; while (low <= high) { mid = (low + high) / 2; ll v = seg.query(s, mid); if (w <= v) { // ok upmax(res, mid+1); low = mid + 1; } else { high = mid - 1; } } ans += res - s; } pr(ans); } } } int main() { FAST; FASTIN; FASTOUT; solve(); }
#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...