Submission #826528

#TimeUsernameProblemLanguageResultExecution timeMemory
826528RifalSimple game (IZhO17_game)C++14
100 / 100
72 ms6844 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; int ans[Max]; 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]) { for(int j = arr[i-1]; j <= M; j += -j&j) { ans[j] += 1; } for(int j = arr[i]+1; j <= M; j += -j&j) { ans[j] -= 1; } } else { for(int j = arr[i]; j <= M; j += -j&j) { ans[j] += 1; } for(int j = arr[i-1]+1; j <= M; j += -j&j) { ans[j] -= 1; } } } while(m--) { int ty; cin >> ty; if(ty == 1) { int pos, val; cin >> pos >> val; pos--; if(pos > 0) { if(arr[pos-1] < arr[pos]) { for(int j = arr[pos-1]; j <= M; j += -j&j) { ans[j] -= 1; } for(int j = arr[pos]+1; j <= M; j += -j&j) { ans[j] += 1; } } else { for(int j = arr[pos]; j <= M; j += -j&j) { ans[j] -= 1; } for(int j = arr[pos-1]+1; j <= M; j += -j&j) { ans[j] += 1; } } if(arr[pos-1] < val) { for(int j = arr[pos-1]; j <= M; j += -j&j) { ans[j] += 1; } for(int j = val+1; j <= M; j += -j&j) { ans[j] -= 1; } } else { for(int j = val; j <= M; j += -j&j) { ans[j] += 1; } for(int j = arr[pos-1]+1; j <= M; j += -j&j) { ans[j] -= 1; } } } if(pos < n-1) { if(arr[pos+1] < arr[pos]) { for(int j = arr[pos+1]; j <= M; j += -j&j) { ans[j] -= 1; } for(int j = arr[pos]+1; j <= M; j += -j&j) { ans[j] += 1; } } else { for(int j = arr[pos]; j <= M; j += -j&j) { ans[j] -= 1; } for(int j = arr[pos+1]+1; j <= M; j += -j&j) { ans[j] += 1; } } if(arr[pos+1] < val) { for(int j = arr[pos+1]; j <= M; j += -j&j) { ans[j] += 1; } for(int j = val+1; j <= M; j += -j&j) { ans[j] -= 1; } } else { for(int j = val; j <= M; j += -j&j) { ans[j] += 1; } for(int j = arr[pos+1]+1; j <= M; j += -j&j) { ans[j] -= 1; } } } arr[pos] = val; } else { int h; cin >> h; int sum = 0; for(int j = h; j > 0; j -= -j&j) { sum += ans[j]; } cout << sum << endl; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...