Submission #1279880

#TimeUsernameProblemLanguageResultExecution timeMemory
1279880dostsSimple game (IZhO17_game)C++20
100 / 100
121 ms33064 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2") #define int long long #define pii pair<int,int> #define vi vector<int> #define ff first #define ss second #define sp << " " << #define all(x) x.begin(),x.end() #define big(x) ((int)(x.size())) using namespace std; const int MOD = 1e9+7, LIM = 1e6+1, inf = 2e9; const int N = 1e5+1; struct ST { vi t; ST(int nn) { t.assign(4*nn+1,0); } void update(int node,int l,int r,int L,int R,int v) { if (l > R || r < L) return; if (l >= L && r <= R) { t[node]+=v; return; } int m = (l+r) >> 1; update(2*node,l,m,L,R,v),update(2*node+1,m+1,r,L,R,v); } int query(int node,int l,int r,int p) { if (l == r) return t[node]; int m = (l+r) >> 1; if (p<=m) return t[node]+query(2*node,l,m,p); else return t[node]+query(2*node+1,m+1,r,p); } }st(LIM); void solve() { int n,m; cin >> n >> m; vi h(n+1); for (int i=1;i<=n;i++) cin >> h[i]; for (int i=1;i<n;i++) { st.update(1,1,LIM,min(h[i],h[i+1]),max(h[i],h[i+1]),1); } while (m--) { int type; cin >> type; if (type == 2) { int x; cin >> x; cout << st.query(1,1,LIM,x) << '\n'; }else { int p,v; cin >> p >> v; if (p>1) st.update(1,1,LIM,min(h[p-1],h[p]),max(h[p-1],h[p]),-1); if (p<n) st.update(1,1,LIM,min(h[p],h[p+1]),max(h[p],h[p+1]),-1); h[p] = v; if (p>1) st.update(1,1,LIM,min(h[p-1],h[p]),max(h[p-1],h[p]),1); if (p<n) st.update(1,1,LIM,min(h[p],h[p+1]),max(h[p],h[p+1]),1); } } } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); #ifdef Dodi freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif int t = 1; //cin >> t; while (t --> 0) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...