Submission #92433

#	Time	Username	Problem	Language	Result	Execution time	Memory
92433		jasony123123	Ruka (COI15_ruka)	C++11	100 / 100	484 ms	32804 KiB

ruka

#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 TNode {
	const static int ID = 0;
	int data;
	TNode* C[2];

	TNode() {
		C[0] = C[1] = NULL;
		data = ID;
	}

	inline TNode* get(int c) {
		if (!C[c]) C[c] = new TNode();
		return C[c];
	}

	void combine() {
		data = get(0)->data + get(1)->data;
	}

	int query(int lo, int hi, int L, int R) { // node represents L, R ... query lo, hi
		if (lo > R || hi < L) return ID;
		if (lo <= L && R <= hi) return data;
		int M = (L + R) / 2;
		return get(0)->query(lo, hi, L, M) + get(1)->query(lo, hi, M + 1, R);
	}

	void update(int p, int val, int L, int R) { // change [p] with val
		if (p > R || p < L) return;
		if (L==p && p==R) {
			data += val;
			return;
		}
		int M = (L + R) / 2;
		get(0)->update(p, val, L, M);
		get(1)->update(p, val, M + 1, R);
		combine();
	}
};

const int MX = 5e7 + 99;
const int SZ = 1e8 + 500;
struct BIT {
	TNode root;
	void add(int x) {
		x += MX;
		root.update(x, 1, 0, SZ);
	}
	void erase(int x) {
		x += MX;
		root.update(x, -1, 0, SZ);
	}
	int query(int x) {
		x += MX;
		return root.query(0, x, 0, SZ);
	}
};

struct Seg {
	stack<int> stac;
	BIT bit;
	int d;
	
	Seg() {
		d = 0;
	}
	void push(int x) {
		stac.push(x - d);
		bit.add(x - d);
	}
	int pop() {
		int top = stac.top();
		stac.pop();
		bit.erase(top);
		return top + d;
	}
	void add(int delta) {
		d += delta;
	}
	int query() {
		return bit.query(-d);
	}
};

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;
}

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