oj.uz

Submission #163993

# Submission time Handle Problem Language Result Execution time Memory
163993 2019-11-16T14:51:51 Z Sorting Ruka (COI15_ruka) C++14
100 / 100
 134 ms 8952 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 3e5 + 7;

struct fenwick{
	int arr[2 * MAXN];

	fenwick(){}

	void update(int idx, int val){
		idx += MAXN;
		for(; idx < 2 * MAXN; idx += (idx & -idx)){
			arr[idx] += val;
		}
	}

	void update_range(int l, int r, int val){
		if(l > r){
			swap(l, r);
		}
		update(l, val);
		update(r + 1, -val);
	}

	int query(int idx){
		idx += MAXN;
		int ret = 0;
		for(; idx >= 1; idx -= (idx & -idx)){
			ret += arr[idx];
		}
		return ret;
	}
};

int n, m;
array<int, 2> p[MAXN];
array<int, 3> queries[MAXN];
fenwick before[2], after[2];
int add[2];

int get_answer(){
	int ret = 0;
	ret += before[0].query(0);
	ret += before[1].query(0);
	ret += after[0].query(add[0]);
	ret += after[1].query(add[1]);

	return ret;
}

void solve(){
	int sum[2] = {1, 1};
	for(int i = 0; i < 1; ++i){
		for(int j = 0; j < 2; ++j){
			before[j].update_range(sum[j], sum[j] + p[i][j], 1);
			sum[j] += p[i][j];
		}
	}
	for(int i = 1; i < n; ++i){
		for(int j = 0; j < 2; ++j){
			after[j].update_range(sum[j], sum[j] + p[i][j], 1);
			sum[j] += p[i][j];
		}
	}

	sum[0] = 1;
	sum[1] = 1;
	add[0] = 0;
	add[1] = 0;

	int curr_line = 0;
	for(int i = 0; i < m; ++i){
		int type = queries[i][0];

		if(type == 'Q'){
			cout << get_answer() << "\n";
			continue;
		}
		if(type == 'B'){
			if(curr_line != 0){
				for(int j = 0; j < 2; ++j){
					before[j].update_range(sum[j], sum[j] + p[curr_line][j], -1);
					after[j].update_range(sum[j] + add[j], sum[j] + p[curr_line][j] + add[j], 1);
					sum[j] -= p[curr_line - 1][j];
				}
				--curr_line;
			} 
			continue;
		}
		if(type == 'F'){
			if(curr_line != n - 1){
				++curr_line;
				for(int j = 0; j < 2; ++j){
					sum[j] += p[curr_line - 1][j] + add[j];
					after[j].update_range(sum[j], sum[j] + p[curr_line][j], -1);
					sum[j] -= add[j];
					before[j].update_range(sum[j], sum[j] + p[curr_line][j], 1);
				}
			}
			continue;
		}

		//type == 'C'
		for(int j = 0; j < 2; ++j){
			add[j] -= queries[i][j + 1] - p[curr_line][j];
			before[j].update_range(sum[j], sum[j] + p[curr_line][j], -1);
		} 
		p[curr_line] = {queries[i][1], queries[i][2]};
		for(int j = 0; j < 2; ++j){
			before[j].update_range(sum[j], sum[j] + p[curr_line][j], 1);
		}
	}
}

void read(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;
	for(int i = 0; i < n; ++i){
		cin >> p[i][0] >> p[i][1];
	}

	cin >> m;
	for(int i = 0; i < m; ++i){
		char type;
		cin >> type;

		queries[i][0] = type;
		if(type == 'C'){
			cin >> queries[i][1] >> queries[i][2];
		}
	}
}

int main(){
	read();
	solve();
}

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 51 ms 3832 KB Output is correct
6 Correct 73 ms 3448 KB Output is correct
7 Correct 54 ms 3548 KB Output is correct
8 Correct 52 ms 3576 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 632 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 3 ms 504 KB Output is correct
5 Correct 51 ms 3832 KB Output is correct
6 Correct 73 ms 3448 KB Output is correct
7 Correct 54 ms 3548 KB Output is correct
8 Correct 52 ms 3576 KB Output is correct
9 Correct 122 ms 8096 KB Output is correct
10 Correct 134 ms 8952 KB Output is correct
11 Correct 120 ms 7852 KB Output is correct
12 Correct 123 ms 7732 KB Output is correct