Submission #92423

#TimeUsernameProblemLanguageResultExecution timeMemory
92423jasony123123Ruka (COI15_ruka)C++11
9 / 100
2055 ms3584 KiB
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 
	/* online submission */

#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}

const ll MOD = 1000000007LL;
const ll PRIME = 105943LL;
const ll INF = 1e18;
/****************************************************************/

const int MAXN = 100099;

struct Seg {
	v<int> stac;
	void push(int x) {
		stac.push_back(x);
	}
	int pop() {
		int ret = stac.back();
		stac.pop_back();
		return ret;
	}
	void add(int delta) {
		for (auto &x : stac) x += delta;
	}
	int query() {
		int r = 0;
		for (auto &x : stac) if (x < 0) r++;
		return r;
	}
};

struct Robot {
	int N; // number of vectors
	int X[MAXN], V[MAXN];
	int i, P;
	Seg minseg, maxseg;

	void init(v<int> &vec) {
		N = vec.size();
		FOR(k, 0, vec.size()) V[k + 1] = vec[k];
		X[0] = 1;
		FORE(k, 1, N) X[k] = X[k - 1] + V[k];
		RFORE(k, N, 1) minseg.push(min(X[k - 1], X[k])), maxseg.push(max(X[k - 1], X[k]));
		i = 1;
		P = 0;
	}

	void forward() {
		if (i == N) return;
		int xlo = minseg.pop(), xhi = maxseg.pop();
		if (V[i] < 0) X[i - 1] = xhi, X[i] = xlo;
		else X[i - 1] = xlo, X[i] = xhi;
		if ((X[i - 1] < 0 && X[i]>0) || (X[i - 1] > 0 && X[i] < 0)) P++;
		i++;
	}
	void backward() {
		if (i == 1) return;
		minseg.push(min(X[i - 2], X[i - 1])), maxseg.push(max(X[i - 2], X[i - 1]));
		if ((X[i - 2] < 0 && X[i - 1]>0) || (X[i - 2] > 0 && X[i - 1] < 0)) P--;
		i--;
	}
	void change(int nv) {
		int xlo = minseg.pop(), xhi = maxseg.pop();
		if (V[i] < 0) X[i - 1] = xhi, X[i] = xlo;
		else X[i - 1] = xlo, X[i] = xhi;
		int d = nv - V[i];
		minseg.add(d), maxseg.add(d);
		V[i] += d, X[i] += d;
		minseg.push(min(X[i - 1], X[i])), maxseg.push(max(X[i - 1], X[i]));
	}
	int query() {
		return P + minseg.query() - maxseg.query();
	}
};

Robot robx, roby;

int main() {
	io();
	int n;
	cin >> n;
	v<int> vinx(n), viny(n);
	FOR(i, 0, n) cin >> vinx[i] >> viny[i];
	robx.init(vinx), roby.init(viny);
	int m;
	cin >> m;
	FOR(i, 0, m) {
		char cmd;
		cin >> cmd;
		if (cmd == 'B')
			robx.backward(), roby.backward();
		else if (cmd == 'F')
			robx.forward(), roby.forward();
		else if (cmd == 'Q')
			cout << robx.query() + roby.query() << "\n";
		else {
			int x, y;
			cin >> x >> y;
			robx.change(x), roby.change(y);
		}
	}
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...