Submission #636713

#	Time	Username	Problem	Language	Result	Execution time	Memory
636713		abeker	Ruka (COI15_ruka)	C++17	100 / 100	442 ms	44936 KiB

ruka

#include <bits/stdc++.h>
using namespace std;

vector <int> operator +(vector <int> a, vector <int> b) {
	int len = a.size();
	assert(b.size() == len);
	vector <int> c(len);
	for (int i = 0; i < len; i++)
		c[i] = a[i] + b[i];
	return c;
}

class Fenwick {
	vector <int> fen;
	vector <int> values;
	vector <pair <int, int>> toDo;
public:
	void update(int x, int val, bool silent = true) {
		if (!val)
			return;
		if (silent) {
			toDo.push_back({x, val});
			return;
		}
		for (x++; x < fen.size(); x += x & -x) 
			fen[x] += val;
	}
	int get(int x, bool silent = true) {
		if (silent) {
			toDo.push_back({x, 0});
			return 0;
		}
		int res = 0;
		for (x++; x; x -= x & -x)
			res += fen[x];
		return res;
	}
	int compress(int x) {
		return lower_bound(values.begin(), values.end(), x) - values.begin();
	}
	vector <int> run() {
		for (auto it : toDo)
			values.push_back(it.first);
		sort(values.begin(), values.end());
		values.resize(unique(values.begin(), values.end()) - values.begin());
		fen.resize(values.size() + 1);
		vector <int> res;
		for (auto it : toDo)
			if (it.second)
				update(compress(it.first), it.second, false);
			else
				res.push_back(get(compress(it.first), false));
		return res;
	}
};

class Counter {
	int n;
	int cursor, shift;
	vector <int> seq, pref, maks;
	Fenwick Left, Right;
public:
	Counter(int _n, int st) {
		n = _n;
		seq.resize(n + 1);
		pref.resize(n + 1);
		maks.resize(n + 1);
		seq[0] = st;
		cursor = 1;
		shift = 0;
	}
	Counter(){}
	void build() {
		pref[0] = maks[0] = seq[0];
		for (int i = 1; i <= n; i++) {
			pref[i] = pref[i - 1] + seq[i];
			maks[i] = max(pref[i], pref[i - 1]);
			Right.update(maks[i], 1);
		}
	}
	void set(int pos, int val) {
		assert(!(val % 2));
		seq[pos] = val;
	}
	void change(int val) {
		shift += val - seq[cursor];
		set(cursor, val);
		Right.update(maks[cursor], -1);
		maks[cursor] = max(pref[cursor - 1] - shift, pref[cursor]);
		Right.update(maks[cursor], 1);
	}
	void backward() {
		if (cursor == 1)
			return;
		cursor--;
		Left.update(maks[cursor], -1);
		maks[cursor] -= shift;
		pref[cursor] -= shift;
		Right.update(maks[cursor], 1);
	}
	void forward() {
		if (cursor == n)
			return;
		Right.update(maks[cursor], -1);
		maks[cursor] += shift;
		pref[cursor] += shift;
		Left.update(maks[cursor], 1);
		cursor++;
	}
	void add_query() {
		Left.get(0);
		Right.get(-shift);
	}
	vector <int> get_queries() {
		return Left.run() + Right.run();
	}
};

int N;
Counter C[4];

void load() {
	scanf("%d", &N);
	for (int j = 0; j < 4; j++)
		C[j] = Counter(N, j % 2 ? -1 : 1);
	for (int i = 1; i <= N; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		for (int j = 0; j < 4; j++)
			C[j].set(i, vector <int>{x, -x, y, -y}[j]);
	}
}

void solve() {
	int M;
	scanf("%d", &M);
	for (int j = 0; j < 4; j++)
		C[j].build();	
	while (M--) {
		char cmd;
		scanf(" %c", &cmd);
		if (cmd == 'C') {
			int nx, ny;
			scanf("%d%d", &nx, &ny);
			for (int j = 0; j < 4; j++)
				C[j].change(vector <int>{nx, -nx, ny, -ny}[j]);
		}
		else if (cmd == 'B')
			for (int j = 0; j < 4; j++)
				C[j].backward();
		else if (cmd == 'F')
			for (int j = 0; j < 4; j++)
				C[j].forward();
		else 
			for (int j = 0; j < 4; j++)
				C[j].add_query();
	}
	vector <int> ans = C[0].get_queries();
	for (int j = 1; j < 4; j++)
		ans = ans + C[j].get_queries();
	for (auto it : ans)
		printf("%d\n", 2 * N - it);
}

int main() {
	double timer = clock();
	load();
	solve();
	fprintf(stderr, "%lf\n", (clock() - timer) / CLOCKS_PER_SEC);
	return 0;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from ruka.cpp:1:
ruka.cpp: In function 'std::vector<int> operator+(std::vector<int>, std::vector<int>)':
ruka.cpp:6:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
    6 |  assert(b.size() == len);
      |         ~~~~~~~~~^~~~~~
ruka.cpp: In member function 'void Fenwick::update(int, int, bool)':
ruka.cpp:25:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |   for (x++; x < fen.size(); x += x & -x)
      |             ~~^~~~~~~~~~~~
ruka.cpp: In function 'void load()':
ruka.cpp:123:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
ruka.cpp:128:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |   scanf("%d%d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~
ruka.cpp: In function 'void solve()':
ruka.cpp:136:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |  scanf("%d", &M);
      |  ~~~~~^~~~~~~~~~
ruka.cpp:141:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |   scanf(" %c", &cmd);
      |   ~~~~~^~~~~~~~~~~~~
ruka.cpp:144:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |    scanf("%d%d", &nx, &ny);
      |    ~~~~~^~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 35 / 35
• Subtask 3: 56 / 56