oj.uz

Submission #1114006

# Submission time Handle Problem Language Result Execution time Memory
1114006 2024-11-18T05:43:05 Z adiyer Simple game (IZhO17_game) C++17
100 / 100
 280 ms 24136 KB 
// 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

game.cpp:2: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    2 | #pragma optimize ("g",on)
      |

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8528 KB Output is correct
2 Correct 7 ms 19280 KB Output is correct
3 Correct 9 ms 19024 KB Output is correct
4 Correct 10 ms 18512 KB Output is correct
5 Correct 9 ms 18768 KB Output is correct
6 Correct 11 ms 18768 KB Output is correct
7 Correct 6 ms 16464 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8528 KB Output is correct
2 Correct 7 ms 19280 KB Output is correct
3 Correct 9 ms 19024 KB Output is correct
4 Correct 10 ms 18512 KB Output is correct
5 Correct 9 ms 18768 KB Output is correct
6 Correct 11 ms 18768 KB Output is correct
7 Correct 6 ms 16464 KB Output is correct
8 Correct 46 ms 11512 KB Output is correct
9 Correct 117 ms 22984 KB Output is correct
10 Correct 142 ms 24136 KB Output is correct
11 Correct 43 ms 7572 KB Output is correct
12 Correct 72 ms 10964 KB Output is correct
13 Correct 71 ms 21320 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8528 KB Output is correct
2 Correct 7 ms 19280 KB Output is correct
3 Correct 9 ms 19024 KB Output is correct
4 Correct 10 ms 18512 KB Output is correct
5 Correct 9 ms 18768 KB Output is correct
6 Correct 11 ms 18768 KB Output is correct
7 Correct 6 ms 16464 KB Output is correct
8 Correct 46 ms 11512 KB Output is correct
9 Correct 117 ms 22984 KB Output is correct
10 Correct 142 ms 24136 KB Output is correct
11 Correct 43 ms 7572 KB Output is correct
12 Correct 72 ms 10964 KB Output is correct
13 Correct 71 ms 21320 KB Output is correct
14 Correct 274 ms 23112 KB Output is correct
15 Correct 280 ms 23116 KB Output is correct
16 Correct 262 ms 24136 KB Output is correct
17 Correct 253 ms 23216 KB Output is correct
18 Correct 258 ms 23072 KB Output is correct