Submission #170197

#TimeUsernameProblemLanguageResultExecution timeMemory
170197andrewSimple game (IZhO17_game)C++17
100 / 100
96 ms11384 KiB
#include <bits/stdc++.h> #pragma GCC optimize("-O3") #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #define fi first #define se second #define p_b push_back #define pll pair<ll,ll> #define pii pair<int,int> #define m_p make_pair #define all(x) x.begin(),x.end() #define sset ordered_set #define sqr(x) (x)*(x) #define pw(x) (1ll << x) #define sz(x) (int)x.size() using namespace std; typedef long long ll; typedef long double ld; const ll MAXN = 1123456; const ll N = 1e6; const ll inf = 3e18; mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count()); template <typename T> void vout(T s){cout << s << endl;exit(0);} ll t[N + 2]; void u(ll pos, ll val){ for(; pos <= N; pos += pos & -pos)t[pos] += val; } ll f(ll pos){ ll res = 0; for(; pos > 0; pos -= pos & -pos)res += t[pos]; return res; } int main(){ ios_base :: sync_with_stdio(0); cin.tie(0); #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif // LOCAL ll n, m; cin >> n >> m; vector <ll> a(n + 1); for(int i = 1; i <= n; i++){ cin >> a[i]; } for(int i = 2; i <= n; i++){ if(a[i - 1] <= a[i]){ ll l = a[i - 1], r = a[i] - 1; if(i == n)r++; u(l, 1); u(r + 1, -1); }else{ ll l = a[i] + 1, r = a[i - 1]; if(i == n)l++; u(l, 1); u(r + 1, -1); } } while(m--){ ll t; cin >> t; if(t == 2){ ll h; cin >> h; cout << f(h) << "\n"; }else{ ll pos, val; cin >> pos >> val; ll l, r; if(pos > 1){ if(a[pos - 1] <= a[pos]){ l = a[pos - 1], r = a[pos] - 1; if(pos == n)r++; u(l, -1); u(r + 1, 1); }else{ l = a[pos] + 1, r = a[pos - 1]; if(pos == n)l++; u(l, -1); u(r + 1, 1); } } if(pos < n){ if(a[pos] <= a[pos + 1]){ l = a[pos], r = a[pos + 1] - 1; if(pos + 1 == n)r++; u(l, -1); u(r + 1, 1); }else{ l = a[pos + 1] + 1, r = a[pos]; if(pos + 1 == n)l++; u(l, -1); u(r + 1, 1); } } a[pos] = val; if(pos > 1){ if(a[pos - 1] <= a[pos]){ l = a[pos - 1], r = a[pos] - 1; if(pos == n)r++; u(l, 1); u(r + 1, -1); }else{ l = a[pos] + 1, r = a[pos - 1]; if(pos == n)l++; u(l, 1); u(r + 1, -1); } } if(pos < n){ if(a[pos] <= a[pos + 1]){ l = a[pos], r = a[pos + 1] - 1; if(pos + 1 == n)r++; u(l, 1); u(r + 1, -1); }else{ l = a[pos + 1] + 1, r = a[pos]; if(pos + 1 == n)l++; u(l, 1); u(r + 1, -1); } } } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...