Submission #1215877

#TimeUsernameProblemLanguageResultExecution timeMemory
1215877M_SH_OSimple game (IZhO17_game)C++20
0 / 100
152 ms305620 KiB
#include <bits/stdc++.h> //#include "grader.h" /*#include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp>*/ #define ll long long #define ll1 long long #define ull unsigned long long #define dou long double #define str string #define vll vector<ll> #define vi vector<int> #define pll pair<ll, ll> #define vpll vector<pll> #define vbool vector<bool> #define vstr vector<str> #define vvll vector<vll> #define pb push_back #define pf push_front #define endl "\n" #define fr first #define se second // #define sortcmp(a) sort(a.begin(), a.end(), cmp) #define sort(a) sort(a.begin(), a.end()) #define all(a) a.begin(), a.end() #define reverse(a) reverse(a.begin(), a.end()) #define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define INF 1000000000000000000 #define ordered_set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update> using namespace std; //using namespace __gnu_pbds; mt19937 rng(1488); ll randll(ll l, ll r){ return uniform_int_distribution<ll>(l, r)(rng); } /*vector<map<ll, vll>> s; vll p; ll find(ll v) { if (p[v] == v) return v; return p[v] = find(p[v]); } void unite(ll a, ll b) { a = find(a); b = find(b); if (a == b) return; if (s[a].size() < s[b].size()) { p[a] = b; for (auto i : s[a]) { for (int j : i.se) { s[b][i.fr].pb(j); } } s[a].clear(); } else { p[b] = a; for (auto i : s[b]) { for (int j : i.se) { s[a][i.fr].pb(j); } } s[b].clear(); } }*/ vll tree1, d; void push(ll v, ll tl, ll tr) { if (tl == tr) return; tree1[v*2] += d[v]; tree1[v*2+1] += d[v]; d[v*2] += d[v]; d[v*2+1] += d[v]; d[v] = 0; tree1[v] = tree1[v*2]+tree1[v*2+1]; } void bt(ll v, ll tl, ll tr, vll& a) { if (tl == tr) { tree1[v] = a[tl]; return; } ll tm = (tl+tr)/2; bt(v*2, tl, tm, a); bt(v*2, tm+1, tr, a); tree1[v] = tree1[v*2]+tree1[v*2+1]; } ll get(ll l, ll r, ll v, ll tl, ll tr) { if (l <= tl && tr <= r) return tree1[v]; if (tl > r || tr < l) return 0; ll tm = (tl+tr)/2; push(v, tl, tr); return get(l, r, v*2, tl, tm)+get(l, r, v*2+1, tm+1, tr); } void update(ll l, ll r, ll val, ll v, ll tl, ll tr) { if (l <= tl && tr <= r) { tree1[v] += val; d[v] += val; push(v, tl, tr); return; } if (tl > r || tr < l) return; ll tm = (tl+tr)/2; push(v, tl, tr); update(l, r, val, v*2, tl, tm); update(l, r, val, v*2+1, tm+1, tr); tree1[v] = tree1[v*2]+tree1[v*2+1]; } int main() { ll n, q; cin >> n >> q; vll a(n), res(1000007, 0); vvll m(10000007); for (int i =0 ; i < n; i ++) { cin >> a[i]; m[a[i]].pb(i); } if (n == 1) { while (q --) { ll x; cin >> x; if (x == 1) { ll pos, val; cin >> pos >> val; pos --; a[pos] = val; } else { ll k; cin >> k; if (k == a[0]) cout << 1 << endl; else cout << 0 << endl; } } return 0; } ll res1 = 0; for (int i = 1; i <= 1000000; i ++) { for (int j : m[i]) { if (j == 0) { if (a[j+1] >= i) res1 ++; continue; } if (j == n-1) { if (a[j-1] >= i) res1 ++; continue; } if (a[j-1] >= i && a[j+1] >= i) res1 ++; if (a[j-1] < i && a[j+1] < i) res1 --; } res[i] = res1; for (int j : m[i]) { res1 --; if (j == 0) { if (a[j+1] > i) res1 ++; continue; } if (j == n-1) { if (a[j-1] > i) res1 ++; continue; } if (a[j-1] > i && a[j+1] > i) res1 += 2; else if (a[j-1] > i || a[j+1] > i) res1 ++; } } tree1.resize(4000007, 0); d.resize(4000007, 0); bt(1, 0, 1000000, res); while (q --) { ll x; cin >> x; if (x == 1) { ll pos, val; cin >> pos >> val; pos --; if (pos == 0) { if (val > a[pos]) { if (a[pos] > a[pos+1]) { update(a[pos]+1, val, 1, 1, 0, 1000000); } else if (a[pos] <= a[pos+1]) { update(a[pos], min(val, a[pos+1]-1), -1, 1, 0, 1000000); update(min(val, a[pos+1]), min(val, a[pos+1]), 1, 1, 0, 1000000); if (val > a[pos+1]) { update(a[pos+1], a[pos+1], -1, 1, 0, 1000000); update(a[pos+1]+1, val, 1, 1, 0, 1000000); } } } else if (val < a[pos]){ if (a[pos] < a[pos+1]) { update(val, a[pos]-1, 1, 1, 0, 1000000); } else if (a[pos] >= a[pos+1]) { update(max(val, a[pos+1]+1), a[pos], -1, 1, 0, 1000000); update(max(val, a[pos+1]), max(val, a[pos+1]), 1, 1, 0, 1000000); if (val < a[pos+1]) { update(a[pos+1], a[pos+1], -1, 1, 0, 1000000); update(val, a[pos+1]-1, 1, 1, 0, 1000000); } } } } else if (pos == n-1) { if (val > a[pos]) { if (a[pos] > a[pos-1]) { update(a[pos]+1, val, 1, 1, 0, 1000000); } else if (a[pos] <= a[pos-1]) { update(a[pos], min(val, a[pos-1]-1), -1, 1, 0, 1000000); update(min(val, a[pos-1]), min(val, a[pos-1]), 1, 1, 0, 1000000); if (val > a[pos-1]) { update(a[pos-1], a[pos-1], -1, 1, 0, 1000000); update(a[pos-1]+1, val, 1, 1, 0, 1000000); } } } else if (val < a[pos]){ if (a[pos] < a[pos-1]) { update(val, a[pos]-1, 1, 1, 0, 1000000); } else if (a[pos] >= a[pos-1]) { update(max(val, a[pos-1]+1), a[pos], -1, 1, 0, 1000000); update(max(val, a[pos-1]), max(val, a[pos-1]), 1, 1, 0, 1000000); if (val < a[pos-1]) { update(a[pos-1], a[pos-1], -1, 1, 0, 1000000); update(val, a[pos-1]-1, 1, 1, 0, 1000000); } } } } else { ll x = a[pos-1], y = a[pos+1]; if (y < x) swap(x, y); if (val > a[pos]) { if (a[pos] > y) { update(a[pos]+1, val, 2, 1, 0, 1000000); update(val, val, -1, 1, 0, 1000000); update(a[pos], a[pos], -1, 1, 0, 1000000); } else if (a[pos] > x) { if (val == y) { if (a[pos] != y) update(val, val, 1, 1, 0, 1000000); } else if (val > y){ update(y, val, 2, 1, 0, 1000000); update(val, val, -1, 1, 0, 1000000); update(y, y, -1, 1, 0, 1000000); if (a[pos] == y) update(y, y, -1, 1, 0, 1000000); } } else { } } else if (val < a[pos]){ if (a[pos] < a[pos+1]) { update(val, a[pos]-1, 1, 1, 0, 1000000); } else if (a[pos] >= a[pos+1]) { update(max(val, a[pos+1]+1), a[pos], -1, 1, 0, 1000000); update(max(val, a[pos+1]), max(val, a[pos+1]), 1, 1, 0, 1000000); if (val < a[pos+1]) { update(a[pos+1], a[pos+1], -1, 1, 0, 1000000); update(val, a[pos+1]-1, 1, 1, 0, 1000000); } } } } a[pos] = val; } else { ll k; cin >> k; cout << get(k, k, 1, 0, 1000000) << endl; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...