Submission #797174

#TimeUsernameProblemLanguageResultExecution timeMemory
797174eltu0815Fish 2 (JOI22_fish2)C++14
0 / 100
24 ms25896 KiB
#include <bits/stdc++.h> #define MAX 500005 #define MOD (ll)(1e9+7) #define INF (ll)(1e18) #define inf (1000000001) using namespace std; typedef long long ll; typedef pair<ll, ll> pll; typedef pair<int, int> pii; int n, q; int arr[100005]; struct SEG1 { ll seg[400005]; void update(int str, int ed, int idx, ll val, int node) { if(str == ed) { seg[node] = val; return; } int mid = str + ed >> 1; if(idx <= mid) update(str, mid, idx, val, node << 1); else update(mid + 1, ed, idx, val, node << 1 | 1); seg[node] = seg[node << 1] + seg[node << 1 | 1]; } ll query(int str, int ed, int left, int right, int node) { if(str > right || ed < left) return 0; if(left <= str && ed <= right) return seg[node]; int mid = str + ed >> 1; return query(str, mid, left, right, node << 1) + query(mid + 1, ed, left, right, node << 1 | 1); } } seg1; struct SEG2 { int seg[400005]; void update(int str, int ed, int idx, int val, int node) { if(str == ed) { seg[node] = val; return; } int mid = str + ed >> 1; if(idx <= mid) update(str, mid, idx, val, node << 1); else update(mid + 1, ed, idx, val, node << 1 | 1); seg[node] = max(seg[node << 1], seg[node << 1 | 1]); } int get_mx(int str, int ed, int left, int right, int val, int node) { if(str > right || ed < left) return -1; if(seg[node] <= val) return -1; if(str == ed) return str; int mid = str + ed >> 1; int tmp = get_mx(mid + 1, ed, left, right, val, node << 1 | 1); if(tmp != -1) return tmp; return get_mx(str, mid, left, right, val, node << 1); } int get_mn(int str, int ed, int left, int right, ll val, int node) { if(str > right || ed < left) return -1; if(seg[node] <= val) return -1; if(str == ed) return str; int mid = str + ed >> 1; int tmp = get_mn(str, mid, left, right, val, node << 1); if(tmp != -1) return tmp; return get_mn(mid + 1, ed, left, right, val, node << 1 | 1); } } seg2; struct SEG3 { struct Node{ int mn, cnt; Node() { mn = inf, cnt = 0; } }; Node seg[400005]; int lazy[400005]; Node Merge(Node l, Node r) { Node ret; ret.cnt = 0; ret.mn = min(l.mn, r.mn); if(l.mn == ret.mn) ret.cnt += l.cnt; if(r.mn == ret.mn) ret.cnt += r.cnt; return ret; } void init(int str, int ed, int node) { lazy[node] = 0; if(str == ed) { seg[node].mn = 0, seg[node].cnt = 1; return; } int mid = str + ed >> 1; init(str, mid, node << 1); init(mid + 1, ed, node << 1 | 1); seg[node] = Merge(seg[node << 1], seg[node << 1 | 1]); } void lazyProp(int str, int ed, int node) { if(lazy[node]) { seg[node].mn += lazy[node]; if(str != ed) { lazy[node << 1] += lazy[node]; lazy[node << 1 | 1] += lazy[node]; } lazy[node] = 0; } } void update(int str, int ed, int left, int right, int val, int node) { lazyProp(str, ed, node); if(str > right || ed < left) return; if(left <= str && ed <= right) { lazy[node] += val; lazyProp(str, ed, node); return; } int mid = str + ed >> 1; update(str, mid, left, right, val, node << 1); update(mid + 1, ed, left, right, val, node << 1 | 1); seg[node] = Merge(seg[node << 1], seg[node << 1 | 1]); } Node query(int str, int ed, int left, int right, int node) { lazyProp(str, ed, node); if(str > right || ed < left) return Node(); if(left <= str && ed <= right) return seg[node]; int mid = str + ed >> 1; return Merge(query(str, mid, left, right, node << 1), query(mid + 1, ed, left, right, node << 1 | 1)); } } seg3; set<pii> s; struct SEG4 { vector<pii> seg[400005]; void update(int str, int ed, int l, int r, int node) { int mid = str + ed >> 1; if(str == ed || (l <= mid && r > mid)) { //assert(seg[node].empty() || (seg[node].back().first >= l && seg[node].back().second <= r)); seg[node].push_back({l, r}); seg3.update(1, n, l, r, 1, 1); return; } if(r <= mid) update(str, mid, l, r, node << 1); else update(mid + 1, ed, l, r, node << 1 | 1); } void erasex(int str, int ed, int x, int node) { while(!seg[node].empty() && seg[node].back().first <= x && x <= seg[node].back().second) { seg3.update(1, n, seg[node].back().first, seg[node].back().second, -1, 1); s.erase({seg[node].back().first, seg[node].back().second}); seg[node].pop_back(); } if(str == ed) return; int mid = str + ed >> 1; if(x <= mid) erasex(str, mid, x, node << 1); else erasex(mid + 1, ed, x, node << 1 | 1); } } seg4; vector<pii> range; void update(int i) { vector<pll> left, right; int j = i, sum = arr[j]; while(j > 1) { j = seg2.get_mx(1, n, 1, j - 1, sum, 1); if(j == -1) break; left.push_back({j, seg1.query(1, n, 1, j, 1)}); sum += arr[j]; } left.push_back({0, 0}); j = i, sum = arr[j]; while(j < n) { j = seg2.get_mn(1, n, j + 1, n, sum, 1); if(j == -1) break; right.push_back({j, seg1.query(1, n, 1, j - 1, 1)}); sum += arr[j]; } right.push_back({n + 1, seg1.query(1, n, 1, n, 1)}); for(auto l : left) for(auto r : right) { if(l.first == 0 && r.first == n + 1) continue; if(r.second - l.second < min(arr[r.first], arr[l.first])) { range.push_back({l.first + 1, r.first - 1}); } } } int push_range() { sort(range.begin(), range.end(), [&](auto a, auto b) { if(a.second - a.first != b.second - b.first) return a.second - a.first < b.second - b.first; return a.first < b.first; }); for(auto [l, r] : range) { if(s.find({l, r}) == s.end()) { seg4.update(1, n, l, r, 1); s.insert({l, r}); } } range.clear(); } int compL(int i, int lim) { vector<int> right; int j = i, sum = arr[j]; while(j < n) { j = seg2.get_mn(1, n, j + 1, n, sum, 1); if(j == -1) break; right.push_back(j); sum += arr[j]; } int mx = i; for(auto r : right) { if(r <= lim && seg1.query(1, n, i, r - 1, 1) < arr[r]) mx = max(mx, r); } return mx; } int compR(int i, int lim) { vector<int> left; int j = i, sum = arr[j]; while(j > 1) { j = seg2.get_mx(1, n, 1, j - 1, sum, 1); if(j == -1) break; left.push_back(j); sum += arr[j]; } int mn = i; for(auto l : left) { if(l >= lim && seg1.query(1, n, l + 1, i, 1) < arr[l]) mn = min(mn, l); } return mn; } int main() { ios::sync_with_stdio(false); cin.tie(NULL); cin >> n; seg3.init(1, n, 1); arr[0] = arr[n + 1] = inf; for(int i = 1; i <= n; ++i) cin >> arr[i]; for(int i = 1; i <= n; ++i) seg1.update(1, n, i, arr[i], 1); for(int i = 1; i <= n; ++i) seg2.update(1, n, i, arr[i], 1); for(int i = 1; i <= n; ++i) update(i); push_range(); cin >> q; while(q--) { int t, a, b; cin >> t >> a >> b; if(t == 1) { arr[a] = b; seg1.update(1, n, a, b, 1); seg2.update(1, n, a, b, 1); seg4.erasex(1, n, a, 1); update(a); if(a > 1) seg4.erasex(1, n, a - 1, 1); if(a > 1) update(a - 1); if(a < n) seg4.erasex(1, n, a + 1, 1); if(a < n) update(a + 1); push_range(); } else { int l = a, r = b; a = compL(a, r); b = compR(b, l); cout << seg3.query(1, n, a, b, 1).cnt << '\n'; } } return 0; }

Compilation message (stderr)

fish2.cpp: In member function 'void SEG1::update(int, int, int, ll, int)':
fish2.cpp:22:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |         int mid = str + ed >> 1;
      |                   ~~~~^~~~
fish2.cpp: In member function 'll SEG1::query(int, int, int, int, int)':
fish2.cpp:30:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   30 |         int mid = str + ed >> 1;
      |                   ~~~~^~~~
fish2.cpp: In member function 'void SEG2::update(int, int, int, int, int)':
fish2.cpp:42:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |         int mid = str + ed >> 1;
      |                   ~~~~^~~~
fish2.cpp: In member function 'int SEG2::get_mx(int, int, int, int, int, int)':
fish2.cpp:51:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |         int mid = str + ed >> 1;
      |                   ~~~~^~~~
fish2.cpp: In member function 'int SEG2::get_mn(int, int, int, int, ll, int)':
fish2.cpp:60:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |         int mid = str + ed >> 1;
      |                   ~~~~^~~~
fish2.cpp: In member function 'void SEG3::init(int, int, int)':
fish2.cpp:87:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   87 |         int mid = str + ed >> 1;
      |                   ~~~~^~~~
fish2.cpp: In member function 'void SEG3::update(int, int, int, int, int, int)':
fish2.cpp:110:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  110 |         int mid = str + ed >> 1;
      |                   ~~~~^~~~
fish2.cpp: In member function 'SEG3::Node SEG3::query(int, int, int, int, int)':
fish2.cpp:119:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  119 |         int mid = str + ed >> 1;
      |                   ~~~~^~~~
fish2.cpp: In member function 'void SEG4::update(int, int, int, int, int)':
fish2.cpp:128:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  128 |         int mid = str + ed >> 1;
      |                   ~~~~^~~~
fish2.cpp: In member function 'void SEG4::erasex(int, int, int, int)':
fish2.cpp:146:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  146 |         int mid = str + ed >> 1;
      |                   ~~~~^~~~
fish2.cpp: In function 'int push_range()':
fish2.cpp:187:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  187 |     for(auto [l, r] : range) {
      |              ^
fish2.cpp:195:1: warning: no return statement in function returning non-void [-Wreturn-type]
  195 | }
      | ^
#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...