Submission #483510

#TimeUsernameProblemLanguageResultExecution timeMemory
483510ak2006Simple game (IZhO17_game)C++14
100 / 100
211 ms7064 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using vb = vector<bool>; using vvb = vector<vb>; using vi = vector<int>; using vvi = vector<vi>; using vl = vector<ll>; using vvl = vector<vl>; using vc = vector<char>; using vvc = vector<vc>; using vs = vector<string>; const ll mod = 1e9 + 7,inf = 1e18; #define pb push_back #define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); void setIO() { fast; } vi bit(1e6 + 1); void add(int i,int v) { for (;i<=1e6;i += i & (-i))bit[i] += v; } void add(int l,int r,int v) { add(l,v); add(r + 1,-v); } int get(int i) { int ret = 0; for (;i>0;i -= i &(-i))ret += bit[i]; return ret; } int main() { setIO(); int n,q; cin>>n>>q; vi h(n + 1); for (int i = 1;i<=n;i++){ cin>>h[i]; if (i >= 2) add(min(h[i - 1],h[i]),max(h[i - 1],h[i]),1); } while (q--){ int t; cin>>t; if (t == 1){ int p,v; cin>>p>>v; if (p >= 2) add(min(h[p - 1],h[p]),max(h[p - 1],h[p]),-1); if (p < n) add(min(h[p],h[p + 1]),max(h[p],h[p + 1]),-1); h[p] = v; if (p >= 2) add(min(h[p - 1],h[p]),max(h[p - 1],h[p]),1); if (p < n) add(min(h[p],h[p + 1]),max(h[p],h[p + 1]),1); } else{ int H; cin>>H; cout<<get(H)<<endl; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...