Submission #673255

#	Time	Username	Problem	Language	Result	Execution time	Memory
673255		Cutebol	Simple game (IZhO17_game)	C++17	100 / 100	399 ms	34480 KiB

game

#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 (stderr)

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 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51