Submission #1114006

#TimeUsernameProblemLanguageResultExecution timeMemory
1114006adiyerSimple game (IZhO17_game)C++17
100 / 100
280 ms24136 KiB
// 194.67 #pragma optimize ("g",on) #pragma GCC optimize("inline") #pragma GCC optimize ("Ofast") #pragma GCC optimize ("unroll-loops") #pragma GCC optimize ("03") // #pragma GCC target ("sse,sse2,sse3,ssse3,sse4,popcnt,abm,avx2,mmx,fma,avx,tune=native") #include <bits/stdc++.h> #define file(s) freopen(s".in", "r", stdin); freopen(s".out", "w", stdout); #define adiyer(); ios_base::sync_with_stdio(0); cin.tie(0); #define bitcount(n) __builtin_popcountll(n) #define puts(x) cout << (x ? "YES\n" : "NO\n"); #define ent (i == n ? '\n' : ' ') #define all(x) x.begin(), x.end() #define md ((l + r) >> 1) #define rv(v) ((v << 1) | 1) #define lv(v) (v << 1) #define rs(v) rv(v), md + 1, r #define ls(v) lv(v), l, md #define len(s) (int) s.size() #define yes { cout << "YES\n"; return; } #define no { cout << "NO\n"; return; } #define skip continue #define pb push_back #define S second #define F first #define ne != // #define int long long using namespace std; typedef int ll; typedef long double ld; typedef vector < ll > vll; typedef pair < ll, ll > pll; typedef vector < pair < ll, ll > > vpll; const int dx[8] = {-1, 0, 1, 0, 1, 1, -1, -1}; const int dy[8] = {0, 1, 0, -1, -1, 1, -1, 1}; const int N = 1e6 + 5; const int K = 1e5 + 3; const int MAX = 1e6; const int mod = 998244353; const long long inf = 2e9; const ll o = 1; mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); ll n, q; ll a[N], t[5 * MAX + 3], z[5 * MAX]; void push(ll v, ll l, ll r){ if(z[v] == 0) return; if(l != r) z[lv(v)] += z[v], z[rv(v)] += z[v]; t[v] += (r - l + 1) * z[v]; z[v] = 0; } void upd(ll tl, ll tr, ll x, ll v = 1, ll l = 1, ll r = MAX){ push(v, l, r); if(tr < l || r < tl) return; if(tl <= l && r <= tr){ z[v] = x; push(v, l, r); return; } upd(tl, tr, x, v + v, l, md); upd(tl, tr, x, v + v + 1, md + 1, r); t[v] = t[lv(v)] + t[rv(v)]; } ll get(ll tl, ll tr, ll v = 1, ll l = 1, ll r = MAX){ push(v, l, r); if(r < tl || tr < l) return 0; if(tl <= l && r <= tr) return t[v]; return get(tl, tr, ls(v)) + get(tl, tr, rs(v)); } void output(){ cin >> n >> q; for(ll i = 1; i <= n; i++) cin >> a[i]; for(ll i = 2; i <= n; i++) upd(min(a[i], a[i - 1]), max(a[i], a[i - 1]), 1); while(q--){ ll tp, x, y; cin >> tp >> x; if(tp == 1){ cin >> y; if(x > 1) upd(min(a[x], a[x - 1]), max(a[x], a[x - 1]), -1); if(x < n) upd(min(a[x], a[x + 1]), max(a[x], a[x + 1]), -1); a[x] = y; if(x > 1) upd(min(a[x], a[x - 1]), max(a[x], a[x - 1]), 1); if(x < n) upd(min(a[x], a[x + 1]), max(a[x], a[x + 1]), 1); } else{ cout << get(x, x) << '\n'; } } } const bool cases = 0; signed main(){ // file("disrupt"); adiyer(); int tt = 1; if(cases) cin >> tt; for(int i = 1; i <= tt; i++){ // cout << "Case " << i << ":\n"; output(); // slow(); // stress(); } }

Compilation message (stderr)

game.cpp:2: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    2 | #pragma optimize ("g",on)
      |
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...