oj.uz

Submission #666346

# Submission time Handle Problem Language Result Execution time Memory
666346 2022-11-28T08:48:02 Z Kaztaev_Alisher Simple game (IZhO17_game) C++17
49 / 100
 671 ms 11960 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] , b[N] , x[N];
vector<int> v;
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]);
			x[l]++;
			x[r+1]--;
		}
	}	
	if(n <= 1000 && m <= 1000){
		while(m--){
			int tp ,pos , val;
			cin >> tp >> pos;
			if(tp == 2){
				int ans = 0;
				for(int i = 2; i <= n; i++){
					int mn = min(a[i] , a[i-1]);					
					int mx = max(a[i] , a[i-1]);
					if(mn <= pos && pos < mx) ans++;
					else if(mn < pos && pos <= mx) ans++;
				}
				cout << ans <<"\n";
			} else {
				cin >> val;
				a[pos] = val;	
			}
		}
		return;
	}
	for(int i = 1; i <= N-5; i++) x[i] += x[i-1];
	for(int i = 1; i <= m; i++){
		int tp;
		cin >> tp;
		if(tp == 2){
			int pos;
			cin >> pos;
			int ans = x[pos];
			for(int j : v){
				if(j-1 > 0){
					int mn = min(a[j] , a[j-1]);
					int mx = max(a[j] , a[j-1]);
					if(mn <= pos && pos <= mx) ans--;
					mn = min(a[j-1] , b[j]);
					mx = max(a[j-1] , b[j]);
					if(mn <= pos && pos <= mx) ans++;
				} 
				if(j+1 <= n){
					int mn = min(a[j] , a[j+1]);
					int mx = max(a[j] , a[j+1]);
					if(mn <= pos && pos <= mx) ans--;
					mn = min(a[j+1] , b[j]);
					mx = max(a[j+1] , b[j]);
					if(mn <= pos && pos <= mx) ans++;
				} 
			}	
			cout << ans <<"\n";
		} else {
			int pos , val;
			cin >> pos >> val;
			if(b[pos] == 0) v.pb(pos);
			b[pos] = val;
			if(v.sz() == 400){
				for(int j : v){
					a[j] = b[j];
					b[j] = 0;
				}
				for(int i = 1; i <= N-5; i++) x[i] = 0;
				for(int i = 2; i <= n; i++){
					int l = min(a[i] , a[i-1]);
					int r = max(a[i] , a[i-1]);
					x[l]++;
					x[r+1]--;
				}
				for(int i = 1; i <= N-5; i++) x[i] += x[i-1];
				v.cl();
			}	
		}
	}
}
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:122:2: note: in expansion of macro 'file'
  122 |  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:122:2: note: in expansion of macro 'file'
  122 |  file("game");
      |  ^~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 4 ms 3412 KB Output is correct
3 Correct 4 ms 3548 KB Output is correct
4 Correct 4 ms 3416 KB Output is correct
5 Correct 4 ms 3420 KB Output is correct
6 Correct 5 ms 3540 KB Output is correct
7 Correct 2 ms 352 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 4 ms 3412 KB Output is correct
3 Correct 4 ms 3548 KB Output is correct
4 Correct 4 ms 3416 KB Output is correct
5 Correct 4 ms 3420 KB Output is correct
6 Correct 5 ms 3540 KB Output is correct
7 Correct 2 ms 352 KB Output is correct
8 Correct 30 ms 9848 KB Output is correct
9 Correct 49 ms 11088 KB Output is correct
10 Correct 49 ms 11072 KB Output is correct
11 Correct 28 ms 9732 KB Output is correct
12 Correct 43 ms 10832 KB Output is correct
13 Correct 37 ms 10964 KB Output is correct

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 4 ms 3412 KB Output is correct
3 Correct 4 ms 3548 KB Output is correct
4 Correct 4 ms 3416 KB Output is correct
5 Correct 4 ms 3420 KB Output is correct
6 Correct 5 ms 3540 KB Output is correct
7 Correct 2 ms 352 KB Output is correct
8 Correct 30 ms 9848 KB Output is correct
9 Correct 49 ms 11088 KB Output is correct
10 Correct 49 ms 11072 KB Output is correct
11 Correct 28 ms 9732 KB Output is correct
12 Correct 43 ms 10832 KB Output is correct
13 Correct 37 ms 10964 KB Output is correct
14 Incorrect 671 ms 11960 KB Output isn't correct
15 Halted 0 ms 0 KB -