oj.uz

Submission #673255

# Submission time Handle Problem Language Result Execution time Memory
673255 2022-12-20T03:43:38 Z Cutebol Simple game (IZhO17_game) C++17
100 / 100
 399 ms 34480 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;

void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define Xiao ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0);
#define int long long
#define endl "\n"

const int N = 1e6 + 5 ;
const int mod = 1e9 + 7 ;

int n , m ;
int g[4*N] , a[N] , lz[4*N] ;

void push( int v , int l , int r ){
	if ( !lz[v] ) return ;
	if ( l != r ){
		lz[v+v] += lz[v] ;
		lz[v+v+1] += lz[v] ;
	}
	g[v] += (r-l+1)*lz[v] ;
	lz[v] = 0 ;
}

void build ( int v , int l , int r , int x , int y , int val ){
	push(v,l,r) ;
	if ( l > y || r < x ) return ;
	if ( ( x <= l && y >= r ) ){
		lz[v] += val ;
		push(v,l,r) ;
		return ;
	}
	int mid = ( l + r ) / 2 ;
	build( v + v , l , mid , x , y , val ) ;
	build( v + v + 1 , mid + 1 , r , x , y , val ) ;
	g[v] = g[v+v]+g[v+v+1] ;
}

int get ( int v , int l , int r , int x ){
	push(v,l,r) ;
	if ( l == r ) return g[v] ;
	int mid = ( l + r ) / 2 ;
	if ( x <= mid ) return get( v + v , l , mid , x ) ;
	else return get( v + v + 1 , mid + 1 , r , x ) ;
}

void solve(){

	cin >> n >> m ;
	for ( int i = 1 ; i <= n ; i ++ ) cin >> a[i] ;
	
	for ( int i = 1 ; i < n ; i ++ ) build( 1 , 1 , N , min(a[i],a[i+1]) , max(a[i],a[i+1]) , 1 ) ;
	while ( m -- ){
		int tt ;
		cin >> tt ;
		if ( tt == 1 ){
			int pos , val ;
			cin >> pos >> val ;
			if ( pos > 1 ) build( 1 , 1 , N , min(a[pos-1],a[pos]) , max(a[pos-1],a[pos]) , -1 ) ;
			if ( pos < n ) build( 1 , 1 , N , min(a[pos],a[pos+1]) , max(a[pos],a[pos+1]) , -1 ) ;
			a[pos] = val ;
			if ( pos > 1 ) build( 1 , 1 , N , min(a[pos-1],a[pos]) , max(a[pos-1],a[pos]) , 1 ) ;
			if ( pos < n ) build( 1 , 1 , N , min(a[pos],a[pos+1]) , max(a[pos],a[pos+1]) , 1 ) ;
		}
		else{
			int x ;
			cin >> x ;
			cout << get( 1 , 1 , N , x ) << endl ;
		}
	}
}

signed main(){

	Xiao ;
	int t = 1 ;
//	cin >> t ;
	while ( t -- )
		  solve() ;

}

Compilation message

game.cpp: In function 'void fopn(std::string)':
game.cpp:8:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
game.cpp:8:72: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | void fopn(string name){freopen((name+".in").c_str(),"r",stdin); freopen((name+".out").c_str(),"w",stdout);}
      |                                                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 14 ms 24276 KB Output is correct
3 Correct 14 ms 23796 KB Output is correct
4 Correct 13 ms 24280 KB Output is correct
5 Correct 14 ms 24276 KB Output is correct
6 Correct 15 ms 24404 KB Output is correct
7 Correct 15 ms 19028 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 14 ms 24276 KB Output is correct
3 Correct 14 ms 23796 KB Output is correct
4 Correct 13 ms 24280 KB Output is correct
5 Correct 14 ms 24276 KB Output is correct
6 Correct 15 ms 24404 KB Output is correct
7 Correct 15 ms 19028 KB Output is correct
8 Correct 73 ms 1324 KB Output is correct
9 Correct 161 ms 34480 KB Output is correct
10 Correct 184 ms 34456 KB Output is correct
11 Correct 49 ms 1328 KB Output is correct
12 Correct 129 ms 2708 KB Output is correct
13 Correct 130 ms 34460 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 14 ms 24276 KB Output is correct
3 Correct 14 ms 23796 KB Output is correct
4 Correct 13 ms 24280 KB Output is correct
5 Correct 14 ms 24276 KB Output is correct
6 Correct 15 ms 24404 KB Output is correct
7 Correct 15 ms 19028 KB Output is correct
8 Correct 73 ms 1324 KB Output is correct
9 Correct 161 ms 34480 KB Output is correct
10 Correct 184 ms 34456 KB Output is correct
11 Correct 49 ms 1328 KB Output is correct
12 Correct 129 ms 2708 KB Output is correct
13 Correct 130 ms 34460 KB Output is correct
14 Correct 354 ms 34220 KB Output is correct
15 Correct 346 ms 34156 KB Output is correct
16 Correct 399 ms 34220 KB Output is correct
17 Correct 340 ms 34140 KB Output is correct
18 Correct 310 ms 34236 KB Output is correct