Submission #758155

#TimeUsernameProblemLanguageResultExecution timeMemory
758155vjudge1Simple game (IZhO17_game)C++17
0 / 100
11 ms16196 KiB
#include <bits/stdc++.h> #include <fstream> #define endl '\n' #define mod 1000007 #define INF 1000000000000000000 //#define ll long long ///#define cin fin ///#define cout fout #define fi first #define se second using namespace std; double const EPS = 1e-14; ///ofstream fout("herding.out"); ///ifstream fin("herding.in"); const int Max = 1e6 + 5; const int M = 1e6; struct Lazy{ int sum; bool laz; int va; }; Lazy seg[4*Max]; void push(int x, int l, int r) { if(seg[x].laz == 0 || l == r) return; int mid = (l+r)/2; seg[x].laz = 0; seg[x*2].laz = 1; seg[x*2+1].laz = 1; seg[x*2].sum = (mid-l+1)*seg[x].va; seg[x*2+1].sum = (r-(mid+1)+1)*seg[x].va; seg[x*2].va = seg[x].va; seg[x*2+1].va = seg[x].va; // cout << l << ' ' << r << ' ' << mid << 'h' << endl; // cout << seg[x].sum << ' ' << seg[x*2].sum << ' ' << seg[x*2+1].sum << endl; } void Update(int x, int l, int r, int L, int R,int val) { push(x,l,r); if(R < l || r < L) { return;} else if(l >= L && r <= R) { // cout << l << ' ' << r << 'k' << endl; seg[x].laz = 1; seg[x].sum += (r-l+1)*val; seg[x].va += val; // cout << seg[x].sum << 'j' << endl; } else { int mid = (l+r)/2; Update(x*2,l,mid,L,R,val); Update(x*2+1,mid+1,r,L,R,val); } } int sol(int x, int l, int r, int L, int R) { push(x,l,r); if(R < l || r < L) { return 0;} else if(l >= L && r <= R) { return seg[x].sum; } else { int mid = (l+r)/2; return sol(x*2,l,mid,L,R)+sol(x*2+1,mid+1,r,L,R); } } int main() { ios_base::sync_with_stdio(0);cout.tie(0);cin.tie(0); int n, m; cin >> n >> m; int arr[n]; for(int i = 0; i < n; i++) cin >> arr[i]; for(int i = 1; i < n; i++) { if(arr[i-1] < arr[i]) { Update(1,1,M,arr[i-1],arr[i],1); } else { Update(1,1,M,arr[i],arr[i-1],1); } } // cout << sol(1,1,M,3,3) << endl; while(m--) { int ty; cin >> ty; if(ty == 1) { int pos, val; cin >> pos >> val; if(pos > 1) { if(arr[pos-2] < arr[pos-1]) { Update(1,1,M,arr[pos-2],arr[pos-1],-1); } else { Update(1,1,M,arr[pos-1],arr[pos-2],-1); } if(arr[pos-2] < val) { Update(1,1,M,arr[pos-2],val,1); } else { Update(1,1,M,val,arr[pos-2],1); } } if(pos < n) { if(arr[pos] < arr[pos-1]) { Update(1,1,M,arr[pos],arr[pos-1],-1); } else { Update(1,1,M,arr[pos-1],arr[pos],-1); } if(arr[pos] < val) { Update(1,1,M,arr[pos],val,1); } else { Update(1,1,M,val,arr[pos],1); } } arr[pos-1] = val; } else { int h; cin >> h; cout << sol(1,1,M,h,h) << endl; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...