제출 #92428

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
92428		jasony123123	Ruka (COI15_ruka)	C++11	9 / 100	2044 ms	11248 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 BIT {
	multiset<int> stuff;
	void add(int x) {
		stuff.insert(x);
	}
	void erase(int x) {
		stuff.erase(stuff.find(x));
	}
	int query(int x) {
		// num<x
		int r = 0;
		for (auto d : stuff) if (d < x) r++;
		return r;
	}
};

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: 0 / 35
• Subtask 3: 0 / 56