Submission #962240

#TimeUsernameProblemLanguageResultExecution timeMemory
962240CookieSimple game (IZhO17_game)C++14
100 / 100
47 ms10476 KiB
#include<bits/stdc++.h> #include<fstream> using namespace std; #define sz(a) (int)a.size() #define ALL(v) v.begin(), v.end() #define ALLR(v) v.rbegin(), v.rend() #define ll long long #define pb push_back #define forr(i, a, b) for(int i = a; i < b; i++) #define dorr(i, a, b) for(int i = a; i >= b; i--) #define ld long double #define vt vector #include<fstream> #define fi first #define se second #define pll pair<ll, ll> #define pii pair<int, int> #define mpp make_pair const ld PI = 3.14159265359, prec = 1e-9;; //using u128 = __uint128_t; //const int x[4] = {1, 0, -1, 0}; //const int y[4] = {0, -1, 0, 1}; const ll mod = 1e9 + 7, pr = 31; const int mxn = 1e6 + 5, mxq = 1e5 + 5, sq = 450, mxv = 5e4 + 1; //const int base = (1 <<18); const ll inf = 1e9 + 5, neg = -69420, inf2 = 1e14; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); // have fun! int n, m; int bit[mxn + 1], h[mxn + 1]; void upd(int p, int v){ while(p <= mxn){ bit[p] += v; p += p & (-p); } } int get(int p){ int ans = 0; while(p){ ans += bit[p]; p -= p & (-p); } return(ans); } void upd(int l, int r, int v){ if(l > r)swap(l, r); upd(l, v); upd(r + 1, -v); } void solve(){ cin >> n >> m; for(int i = 1; i <= n; i++)cin >> h[i]; for(int i = 1; i < n; i++){ upd(h[i], h[i + 1], 1); } for(int i = 0; i < m; i++){ int idq; cin >> idq; if(idq == 1){ int pos, val; cin >> pos >> val; if(pos > 1)upd(h[pos - 1], h[pos], -1); if(pos < n)upd(h[pos], h[pos + 1], -1); h[pos] = val; if(pos > 1)upd(h[pos - 1], h[pos], 1); if(pos < n)upd(h[pos], h[pos + 1], 1); }else{ int v; cin >> v; cout << get(v) << "\n"; } } } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); //freopen("netw.inp", "r", stdin); //freopen("netw.out", "w", stdout) int tt; tt = 1; while(tt--){ solve(); } return(0); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...