Submission #505474

#TimeUsernameProblemLanguageResultExecution timeMemory
505474PragmatismSimple game (IZhO17_game)C++17
0 / 100
1 ms332 KiB
#include <iostream> #include <iomanip> #include <algorithm> #include <string> #include <set> #include <vector> #include <cmath> #include <map> #include <algorithm> #include <stack> #include <queue> #include <cstdlib> #include <cstdio> #include <cstring> #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <cmath> #include <string> #include <sstream> #include <vector> #include <queue> #include <set> #include <map> #include <ctime> #include <unordered_map> #include <unordered_set> #include <cassert> #define __builtin_popcount __popcnt #define pb push_back #define pob pop_back #define pll pair <long long, long long> #define pld pair <long double, long double> #define ll long long #define ull unsigned long long #define ld long double #define int ll // HERE CAN BE WA/RE/MLE/TLE #define Int int #define itn int #define nit int #define x first #define y second #define all(v) v.begin(),v.end() #define sz(s) s.size() #define skip continue #define y0 ijl #define y1 hjk #define equal bayan #define friend trs #define delete bae #define div aber #define exp earb #define new aer using namespace std; const int N = 5e6 + 7; const int WN = 1e5 + 7; const int inf = 1e9 + 7; const int INF = 1e18 + 7; const int MOD = 998244353; int a[N]; int t[N]; int z[N]; void push(int v, int tl, int tr) { if (z[v] == 0)return; t[v] += z[v] * (tr - tl + 1); if (tl != tr)z[v * 2] += z[v * 2 + 1] += z[v]; z[v] = 0; } int get(int v, int tl, int tr, int l, int r) { push(v, tl, tr); if (tr < l || tl > r)return 0; if (tl >= l && tr <= r)return t[v]; int mid = (tl + tr) / 2; return (get(v * 2, tl, mid, l, r) + get(v * 2 + 1, mid + 1, tr, l, r)); } void update(int v, int tl, int tr, int l, int r, int x) { push(v, tl, tr); if (tr < l || tl > r)return; if (tl >= l && tr <= r) { z[v] += x; push(v, tl, tr); return; } int mid = (tl + tr) / 2; update(v * 2, tl, mid, l, r, x), update(v * 2 + 1, mid + 1, tr, l, r, x); t[v] = t[v * 2] + t[v * 2 + 1]; } void solve() { int n, q; cin >> n >> q; for (int i = 1;i <= n;i++) { cin >> a[i]; if (i != 1) { if (a[i] - 1 > a[i - 1])update(1, 1, n, a[i - 1] + 1, a[i] - 1, 1); if (a[i] + 1 < a[i - 1])update(1, 1, n, a[i] + 1, a[i - 1] - 1, 1); } } while (q--) { int type, pos, x, h; cin >> type; /*for (int i = 1;i <= n;i++) { for (int j = 1;j <= n;j++) { if (j == i)skip; cout << i << ' ' << j << ':'; cout << get(1, 1, n, i, j) << '\n'; } } */ if (type == 1) { cin >> pos >> x; if (pos != 1) { if (a[pos] - 1 > a[pos - 1])update(1, 1, n, a[pos - 1] + 1, a[pos] - 1, -1); if (a[pos] + 1 < a[pos - 1])update(1, 1, n, a[pos] + 1, a[pos - 1] - 1, -1); } if (pos != n) { if (a[pos] - 1 > a[pos + 1])update(1, 1, n, a[pos + 1] + 1, a[pos] - 1, -1); if (a[pos] + 1 < a[pos + 1])update(1, 1, n, a[pos] + 1, a[pos + 1] - 1, -1); } a[pos] = x; if (pos != 1) { if (a[pos] - 1 > a[pos - 1])update(1, 1, n, a[pos - 1] + 1, a[pos] - 1, 1); if (a[pos] + 1 < a[pos - 1])update(1, 1, n, a[pos] + 1, a[pos - 1] - 1, 1); } if (pos != n) { if (a[pos] - 1 > a[pos + 1])update(1, 1, n, a[pos + 1] + 1, a[pos] - 1, 1); if (a[pos] + 1 < a[pos + 1])update(1, 1, n, a[pos] + 1, a[pos + 1] - 1, 1); } } else { cin >> h; cout << get(1, 1, n, h, h) << '\n'; } } } signed main() { ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0); //freopen("sum.in", "r", stdin); //freopen("sum.out", "w", stdout); int tt; tt = 1; //cin >> tt;//Here can be tupism while (tt--)solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...