oj.uz

답안 #930600

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
930600 2024-02-20T07:42:04 Z allin27x Simple game (IZhO17_game) C++17
0 / 100
 3 ms 2652 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAXN = 2e5+7;

int t[4*MAXN];
int ina[MAXN];
int n;

map<int,int> key;


void update(int l, int r, int v){
	for (l+=n, r+=n+1; l<r; l>>=1, r>>=1){
		if (l&1) t[l++] += v;
		if (r&1) t[--r] += v;
	}
}

int get(int ind){
	int res = 0;
	for (int i=ind+n; i>0; i>>=1) res+=t[i];
	return res;
}


signed main(){
	int m; cin>>n>>m;
	vector<int> values;
	vector<tuple<int,int,int>> queries(m);
	for (int i=0; i<n; i++) cin>>ina[i];
	for (int i=0; i<n; i++) values.push_back(ina[i]);
	for (int i=0; i<m; i++){
		int r; cin>>r;
		if (r==1){
			int a,b; cin>>a>>b; a--; values.push_back(b); queries[i] = {1,a,b};
		} else {
			int k; cin>>k; values.push_back(k); queries[i] = {2,k,0};
		}
	}
	sort(values.begin(), values.end());
	int ind = 0;
	for (int i=0; i<values.size(); i++){
		if (key.count(values[i])) continue;
		key[values[i]]  = ind++;
	}
	for (int i=0; i<n; i++) ina[i] = key[ina[i]];
	for (int i=0; i<m; i++){
		int r = get<0> (queries[i]); 
		if (r==1){
			get<2> (queries[i]) = key[get<2> (queries[i])];
		} else {
			get<1> (queries[i]) = key[get<1> (queries[i])];
		}
	}
	// for (int i=0; i<n; i++) cout<<ina[i]<<' '; cout<<'\n';
	// for (auto [a,b,c]: queries){
	// 	if (a==1) {
	// 		cout<<b<<' '<<c<<'\n';
	// 	} else {
	// 		cout<<b<<'\n';
	// 	}
	// }

	for (int i=0; i<n-1; i++){
		update(min(ina[i], ina[i+1]), max(ina[i],ina[i+1]), 1);
	}
	for (auto [a,b,c]: queries){
		if (a==1){
			if (b){
				update(min(ina[b], ina[b-1]), max(ina[b], ina[b-1]), -1);
				update(min(ina[b-1], c), max(ina[b-1], c), 1);
			}
			if (b!=n-1){
				update(min(ina[b], ina[b+1]), max(ina[b], ina[b+1]), -1);
				update(min(ina[b+1], c), max(ina[b+1], c), 1);
			}
			ina[b] = c;
		} else {
			cout<<get(b)<<'\n';
		}
	}
}

Compilation message

game.cpp: In function 'int main()':
game.cpp:44:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |  for (int i=0; i<values.size(); i++){
      |                ~^~~~~~~~~~~~~~

Subtask #1
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 3 ms 2652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 3 ms 2652 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Incorrect 3 ms 2652 KB Output isn't correct
3 Halted 0 ms 0 KB -