oj.uz

Submission #666353

# Submission time Handle Problem Language Result Execution time Memory
666353 2022-11-28T09:01:04 Z Kaztaev_Alisher Simple game (IZhO17_game) C++17
100 / 100
 350 ms 36296 KB 
//#pragma GCC optomize ("Ofast")
//#pragma GCC optomize ("unroll-loops")
//#pragma GCC target ("avx,avx2,fma")
 
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define sz size
#define cl clear
#define ins insert
#define ers erase
#define pii pair < int , int >
#define pll pair< long long  , long long >
#define all(x) x.begin() , x.end()
#define ios ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
#define tostr(x) to_string(x)
#define tonum(s) atoi(s.c_str())
#define seon(x) setprecision(x)
#define bpop(x) __builtin_popcount(x)
#define deb(x) cerr << #x  << " = " << x << endl;
 
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
const double PI = 3.14159265;
 
const ll N = 1e6+5;
const ll mod = 1e9+7;
const ll inf = 1e9;
const ll INF = 1e18;
 
using namespace std;
 
ll a[N] , t[N*4] , u[N*4];

void push(int v , int tl , int tr){
	if(tl == tr || u[v] == 0) return;
	int tm = (tl+tr) >> 1;
	t[v*2] += (tm-tl+1)*u[v];
	t[v*2+1] += (tr-tm)*u[v];
	u[v*2] += u[v];
	u[v*2+1] += u[v];
	u[v] = 0;			
}
void upd(int l , int r , int val , int v = 1, int tl = 1 , int tr = N-5){
	push(v , tl , tr);
	if(tl >= l && tr <= r) {
		t[v] += val*(tr-tl+1);
		u[v] += val;
		return;
	} if(tl > r || tr < l) return;
	int tm = (tl+tr) >> 1;
	upd(l,r,val,v*2,tl,tm);
	upd(l,r,val,v*2+1,tm+1,tr);
	t[v] = t[v*2] + t[v*2+1];
}
int get(int pos , int v = 1, int tl = 1, int tr = N-5){
	push(v , tl , tr);
	if(tl == tr) return t[v];
	int tm = (tl+tr) >> 1;
	if(tm >= pos) return get(pos,v*2,tl,tm);
	else return get(pos,v*2+1,tm+1,tr);
}

void solve(){
	int n , m;
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		if(i > 1){
			int l = min(a[i] , a[i-1]);
			int r = max(a[i] , a[i-1]);
			upd(l , r , 1);
		}
	}
	while(m--){
		ll tp , pos , val;
		cin >> tp >> pos;
		if(tp == 2){
			cout << get(pos) <<"\n";
		} else {
			cin >> val;
			if(pos > 1){
				upd(min(a[pos] , a[pos-1]) , max(a[pos] , a[pos-1]) , -1);
				upd(min(val , a[pos-1]) , max(val , a[pos-1]) , 1);
			} 
			if(pos < n){
				upd(min(a[pos] , a[pos+1]) , max(a[pos] , a[pos+1]) , -1);
				upd(min(val , a[pos+1]) , max(val , a[pos+1]) , 1);
			}
			a[pos] = val;
		}
	}
}
signed main(){
	file("game");
	ios;
	solve();
	return 0;
}
/*
*/

Compilation message

game.cpp: In function 'int main()':
game.cpp:17:48: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 | #define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
      |                                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
game.cpp:99:2: note: in expansion of macro 'file'
   99 |  file("game");
      |  ^~~~
game.cpp:17:77: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 | #define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
      |                                                                      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
game.cpp:99:2: note: in expansion of macro 'file'
   99 |  file("game");
      |  ^~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 13 ms 25040 KB Output is correct
3 Correct 16 ms 24316 KB Output is correct
4 Correct 18 ms 24784 KB Output is correct
5 Correct 16 ms 24824 KB Output is correct
6 Correct 13 ms 24916 KB Output is correct
7 Correct 8 ms 18944 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 13 ms 25040 KB Output is correct
3 Correct 16 ms 24316 KB Output is correct
4 Correct 18 ms 24784 KB Output is correct
5 Correct 16 ms 24824 KB Output is correct
6 Correct 13 ms 24916 KB Output is correct
7 Correct 8 ms 18944 KB Output is correct
8 Correct 56 ms 2132 KB Output is correct
9 Correct 163 ms 36080 KB Output is correct
10 Correct 159 ms 36148 KB Output is correct
11 Correct 48 ms 1996 KB Output is correct
12 Correct 97 ms 4148 KB Output is correct
13 Correct 70 ms 35968 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 13 ms 25040 KB Output is correct
3 Correct 16 ms 24316 KB Output is correct
4 Correct 18 ms 24784 KB Output is correct
5 Correct 16 ms 24824 KB Output is correct
6 Correct 13 ms 24916 KB Output is correct
7 Correct 8 ms 18944 KB Output is correct
8 Correct 56 ms 2132 KB Output is correct
9 Correct 163 ms 36080 KB Output is correct
10 Correct 159 ms 36148 KB Output is correct
11 Correct 48 ms 1996 KB Output is correct
12 Correct 97 ms 4148 KB Output is correct
13 Correct 70 ms 35968 KB Output is correct
14 Correct 347 ms 36068 KB Output is correct
15 Correct 350 ms 36156 KB Output is correct
16 Correct 345 ms 36296 KB Output is correct
17 Correct 350 ms 36188 KB Output is correct
18 Correct 336 ms 36044 KB Output is correct