oj.uz

Submission #92433

# Submission time Handle Problem Language Result Execution time Memory
92433 2019-01-02T20:35:00 Z jasony123123 Ruka (COI15_ruka) C++11
100 / 100
 484 ms 32804 KB 
#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.0 / 9.0

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

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 4 ms 732 KB Output is correct
4 Correct 4 ms 636 KB Output is correct
5 Correct 167 ms 12536 KB Output is correct
6 Correct 163 ms 15204 KB Output is correct
7 Correct 171 ms 9592 KB Output is correct
8 Correct 170 ms 10048 KB Output is correct

Subtask #3
56.0 / 56.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 760 KB Output is correct
2 Correct 3 ms 632 KB Output is correct
3 Correct 4 ms 732 KB Output is correct
4 Correct 4 ms 636 KB Output is correct
5 Correct 167 ms 12536 KB Output is correct
6 Correct 163 ms 15204 KB Output is correct
7 Correct 171 ms 9592 KB Output is correct
8 Correct 170 ms 10048 KB Output is correct
9 Correct 461 ms 28804 KB Output is correct
10 Correct 484 ms 32804 KB Output is correct
11 Correct 410 ms 25148 KB Output is correct
12 Correct 445 ms 24704 KB Output is correct