oj.uz

Submission #967506

# Submission time Handle Problem Language Result Execution time Memory
967506 2024-04-22T09:34:16 Z thunopro Simple game (IZhO17_game) C++14
100 / 100
 51 ms 7260 KB 
#include<bits/stdc++.h>
using namespace std ; 
#define maxn 1000009 
#define ll long long 
#define fi first 
#define se second 
#define pb push_back 
#define left id<<1
#define right id<<1|1 
#define _lower(x) lower_bound(v.begin(),v.end(),x)-v.begin()+1 
#define TIME (1.0*clock()/TIME_PERS_SEC) 
#define re exit(0); 

const int mod = 1e9+7 ; 
const int INF = 1e9 ; 

typedef vector<int> vi ; 
typedef pair<int,int> pii ; 
typedef vector<pii> vii ; 

void add ( int &a , int b ) 
{
	a += b ; 
	if ( a >= mod ) a -= mod ; 
	if ( a < 0 ) a += mod ; 
}

template < typename T > void chkmin ( T &a , T b ) { if ( a > b ) a = b ;} 
template < typename T > void chkmax ( T &a , T b ) { if ( a < b ) a = b ;} 

void rf () 
{
	freopen ("bai1.inp","r",stdin) ; 
}

mt19937 rng (time(0)) ; 

int _pow ( int a , int n ) 
{
	if ( n == 0 ) return 1 ; 
	int res = _pow (a,n/2) ; 
	if ( n % 2 ) return 1ll*res*res%mod*a%mod ; 
	else return 1ll*res*res%mod ; 
}

int n , nq ; 
int a [maxn] ; 

int bit [maxn] ; 

void update ( int x , int w ) 
{
	while ( x < maxn ) bit [x] += w , x += (x&-x) ; 
}
int get ( int x ) 
{
	int res = 0 ; 
	while ( x ) res += bit [x] , x -= (x&-x) ; 
	return res ; 
}
void update ( int x , int y , int w ) 
{
	if ( x > y ) swap (x,y) ; 
	update (x,1*w) ;
	update (y+1,-1*w) ;  
}

int main ()
{
	ios_base::sync_with_stdio(0); 
	cin.tie(0);cout.tie(0); 
//	rf () ; 
	cin >> n >> nq ; 
	for ( int i = 1 ; i <= n ; i ++ ) cin >> a [i] ; 
	for ( int i = 1 ; i < n ; i ++ ) update (a[i],a[i+1],1) ; 
	while ( nq -- ) 
	{
		int op ; cin >> op ; 
		if ( op == 1 ) 
		{
			int pos , val ; cin >> pos >> val ; 
			if ( pos > 1 ) update (a[pos-1],a[pos],-1) ; 
			if ( pos < n ) update (a[pos],a[pos+1],-1) ; 
			a [pos] = val ; 
			if ( pos > 1 ) update (a[pos-1],a[pos],1) ; 
			if ( pos < n ) update (a[pos],a[pos+1],1) ; 
		}
		else 
		{
			int x ; cin >> x ; cout << get (x) << "\n" ; 
		}
	}
}

Compilation message

game.cpp: In function 'void rf()':
game.cpp:33:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |  freopen ("bai1.inp","r",stdin) ;
      |  ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4952 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4952 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 30 ms 6796 KB Output is correct
9 Correct 30 ms 7252 KB Output is correct
10 Correct 30 ms 7256 KB Output is correct
11 Correct 29 ms 6736 KB Output is correct
12 Correct 29 ms 7260 KB Output is correct
13 Correct 28 ms 7160 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 2 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4952 KB Output is correct
6 Correct 1 ms 4700 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 30 ms 6796 KB Output is correct
9 Correct 30 ms 7252 KB Output is correct
10 Correct 30 ms 7256 KB Output is correct
11 Correct 29 ms 6736 KB Output is correct
12 Correct 29 ms 7260 KB Output is correct
13 Correct 28 ms 7160 KB Output is correct
14 Correct 51 ms 6996 KB Output is correct
15 Correct 43 ms 6992 KB Output is correct
16 Correct 38 ms 6992 KB Output is correct
17 Correct 38 ms 6996 KB Output is correct
18 Correct 46 ms 6996 KB Output is correct