oj.uz

Submission #384590

# Submission time Handle Problem Language Result Execution time Memory
384590 2021-04-01T21:17:40 Z ritul_kr_singh Simple game (IZhO17_game) C++17
100 / 100
 97 ms 11244 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

struct FenwickTree{
	vector<int> a; int n, s;
	FenwickTree(int N){ a.resize((n=N)+1); }
	void add(int i, int v){
		for(++i; i<=n; i+=i&-i) a[i] += v;
	}
	int get(int i){
		for(s=0; i>=1; i-=i&-i) s += a[i];
		return s;
	}
	int get(int i, int j){ return get(j+1) - get(i); }
};

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int n, m, type, i, x; cin >> n >> m;
	int a[n]; for(int &i : a) cin >> i;
	FenwickTree b(1e6+1);
	for(i=1; i<n; ++i){
		b.add(min(a[i], a[i-1]), 1);
		b.add(max(a[i], a[i-1]), -1);
	}

	while(m--){
		cin >> type >> i;
		if(type==1){
			--i;
			if(i){
				b.add(min(a[i], a[i-1]), -1);
				b.add(max(a[i], a[i-1]), 1);
			}if(i+1<n){
				b.add(min(a[i], a[i+1]), -1);
				b.add(max(a[i], a[i+1]), 1);
			}
			cin >> a[i];
			if(i){
				b.add(min(a[i], a[i-1]), 1);
				b.add(max(a[i], a[i-1]), -1);
			}if(i+1<n){
				b.add(min(a[i], a[i+1]), 1);
				b.add(max(a[i], a[i+1]), -1);
			}
		}else{
			cout << b.get(0, i) nl;
		}
	}
}

Compilation message

game.cpp: In function 'int main()':
game.cpp:22:21: warning: unused variable 'x' [-Wunused-variable]
   22 |  int n, m, type, i, x; cin >> n >> m;
      |                     ^

Subtask #1
22.0 / 22.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8172 KB Output is correct
2 Correct 7 ms 8172 KB Output is correct
3 Correct 6 ms 8172 KB Output is correct
4 Correct 9 ms 8172 KB Output is correct
5 Correct 6 ms 8172 KB Output is correct
6 Correct 6 ms 8172 KB Output is correct
7 Correct 6 ms 8172 KB Output is correct
8 Correct 47 ms 10028 KB Output is correct
9 Correct 66 ms 11244 KB Output is correct
10 Correct 63 ms 11244 KB Output is correct
11 Correct 46 ms 9836 KB Output is correct
12 Correct 53 ms 11116 KB Output is correct
13 Correct 61 ms 10988 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8172 KB Output is correct
2 Correct 7 ms 8172 KB Output is correct
3 Correct 6 ms 8172 KB Output is correct
4 Correct 9 ms 8172 KB Output is correct
5 Correct 6 ms 8172 KB Output is correct
6 Correct 6 ms 8172 KB Output is correct
7 Correct 6 ms 8172 KB Output is correct
8 Correct 47 ms 10028 KB Output is correct
9 Correct 66 ms 11244 KB Output is correct
10 Correct 63 ms 11244 KB Output is correct
11 Correct 46 ms 9836 KB Output is correct
12 Correct 53 ms 11116 KB Output is correct
13 Correct 61 ms 10988 KB Output is correct
14 Correct 89 ms 11244 KB Output is correct
15 Correct 88 ms 11116 KB Output is correct
16 Correct 97 ms 11116 KB Output is correct
17 Correct 91 ms 11244 KB Output is correct
18 Correct 92 ms 11212 KB Output is correct