oj.uz

Submission #526115

# Submission time Handle Problem Language Result Execution time Memory
526115 2022-02-13T18:44:53 Z ezdp Simple game (IZhO17_game) C++14
100 / 100
 241 ms 5624 KB 
#pragma GCC target ("sse4")
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>

#define endl '\n'
#define pb push_back
#define fr first
#define sc second
#define ll long long int
#define ld long double
#define lsb(idx) idx&(-idx)
#define bin(x) bitset<32>(x).to_string()
#define all(A) A.begin(), A.end()
#define de(x) cout << #x << " = " << x << endl;

using namespace std;
using namespace __gnu_pbds;

template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> using matrix = vector<vector<T>>;
/// find_by_order(x) -> x-th element in the set
/// order_of_key(x)  -> how many elements are less than x
/// insert(x)		 -> inserts x into the set

const int MAXN = 1e6 + 6;

int BIT[MAXN];

void add(int x, int v){
	for(++ x; x < MAXN; x += lsb(x))
		BIT[x] += v;
}

int qry(int x){
	int ret = 0;
	for(++ x; x > 0; x -= lsb(x))
		ret += BIT[x];
	return ret;
}

int main(){
	/// ios_base::sync_with_stdio(false); cin.tie(NULL);
	/// freopen("filename.in" , "r", stdin); 
	/// freopen("filename.out", "w", stdout);
	int n, q; cin >> n >> q;
	vector<int> A(n);
	for(auto &x : A) cin >> x;
	for(int i = 0; i < n - 1; i ++){
		add(min(A[i], A[i + 1]), +1);
		add(max(A[i], A[i + 1]), -1);
	}
	for(int i = 0; i < q; i ++){
		int t; cin >> t;
		if(t == 1){
			int i, y; cin >> i >> y; -- i;
			if(i != n - 1){
				add(min(A[i], A[i + 1]), -1);
				add(max(A[i], A[i + 1]), +1);
			}
			if(i != 0){
				add(min(A[i], A[i - 1]), -1);
				add(max(A[i], A[i - 1]), +1);
			}
			A[i] = y;
			if(i != n - 1){
				add(min(A[i], A[i + 1]), +1);
				add(max(A[i], A[i + 1]), -1);
			}
			if(i != 0){
				add(min(A[i], A[i - 1]), +1);
				add(max(A[i], A[i - 1]), -1);
			}
		}
		if(t == 2){
			int y; cin >> y;
			cout << qry(y) << endl;
		}
	}
}
/**

*/

Compilation message

game.cpp:3: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    3 | #pragma GCC optimization ("O3")
      | 
game.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 4 ms 4044 KB Output is correct
3 Correct 4 ms 4044 KB Output is correct
4 Correct 4 ms 4044 KB Output is correct
5 Correct 4 ms 4016 KB Output is correct
6 Correct 3 ms 4020 KB Output is correct
7 Correct 3 ms 332 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 4 ms 4044 KB Output is correct
3 Correct 4 ms 4044 KB Output is correct
4 Correct 4 ms 4044 KB Output is correct
5 Correct 4 ms 4016 KB Output is correct
6 Correct 3 ms 4020 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 189 ms 1428 KB Output is correct
9 Correct 231 ms 5604 KB Output is correct
10 Correct 205 ms 5624 KB Output is correct
11 Correct 241 ms 1324 KB Output is correct
12 Correct 194 ms 1924 KB Output is correct
13 Correct 210 ms 1744 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 4 ms 4044 KB Output is correct
3 Correct 4 ms 4044 KB Output is correct
4 Correct 4 ms 4044 KB Output is correct
5 Correct 4 ms 4016 KB Output is correct
6 Correct 3 ms 4020 KB Output is correct
7 Correct 3 ms 332 KB Output is correct
8 Correct 189 ms 1428 KB Output is correct
9 Correct 231 ms 5604 KB Output is correct
10 Correct 205 ms 5624 KB Output is correct
11 Correct 241 ms 1324 KB Output is correct
12 Correct 194 ms 1924 KB Output is correct
13 Correct 210 ms 1744 KB Output is correct
14 Correct 189 ms 5448 KB Output is correct
15 Correct 177 ms 5276 KB Output is correct
16 Correct 194 ms 5304 KB Output is correct
17 Correct 206 ms 5368 KB Output is correct
18 Correct 196 ms 5360 KB Output is correct