Submission #334508

#	Time	Username	Problem	Language	Result	Execution time	Memory
334508		syy	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	893 ms	102864 KiB

fortune_telling2

/* WLOG assume a_i < b_i
 * then there are 3 kinds of updates
 * 1: x < b_i, 2: b_i <= x < a_i, 3: a_i <= x
 * ignore updates of type 1, updates of type 2 will ensure a_i is on top, type 3 will flip it
 * so for every card, find the last of type 2 then query number of type 3
 * process in decreasing order of "last type 2 update"
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define FOR(i, a, b) for(ll i = (ll)a; i <= (ll)b; i++)
#define DEC(i, a, b) for(ll i = (ll)a; i >= (ll)b; i--)
typedef pair<ll, ll> pi;
typedef pair<pi, ll> pii;
typedef pair<ll, pi> ipi;
typedef pair<pi, pi> pipi;
#define f first
#define s second
typedef vector<ll> vi;
typedef vector<pi> vpi;
typedef vector<pii> vpii;
#define pb push_back
#define pf push_front
#define all(v) v.begin(), v.end()
#define size(v) (ll) v.size()
#define INF (ll) 1e9 + 100
#define LLINF (ll) 1e18
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define sandybridge __attribute__((optimize("Ofast"), target("arch=sandybridge")))
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline ll rand(ll x, ll y) { ++y; return (rng() % (y-x)) + x; } //inclusivesss

ll n, k, op[200005], ans;
pi arr[200005];
vi disc;
vpi v;

struct node {
	ll s, e, m, maxv;
	node *l, *r;
	node (ll S, ll E) {
		s = S, e = E, m = (s+e)/2, maxv = 0;
		if (s != e) {
			l = new node(s, m);
			r = new node(m+1, e);
		}
	}
	void maxup(ll x, ll nv) {
		if (s == e) {maxv = max(maxv, nv); return;}
		else if (x <= m) l->maxup(x, nv);
		else r->maxup(x, nv);
		maxv = max(l->maxv, r->maxv);
	}
	ll maxq(ll x, ll y) {
		if (s == x and e == y) return maxv;
		else if (y <= m) return l->maxq(x, y);
		else if (x > m) return r->maxq(x, y);
		else return max(l->maxq(x, m), r->maxq(m+1, y));
	}
} *seg;

ll ft[600005]; // note: this fenwick tree is 1-indexed.
ll ls(ll x) { return x & (-x); }

void up(ll p, ll v) {
	for (; p <= size(disc); p += ls(p)) ft[p] += v;
}

ll fquery(ll p) { //Returns sum from [1, p]
	ll sum = 0;
	for (;p; p -= ls(p)) sum += ft[p]; // while p > 0
	return sum;
}

inline ll query(ll a, ll b) {
	return fquery(b) - fquery(a-1);
}

int main() {
	fastio; cin >> n >> k;
	FOR(i, 1, n) {
		cin >> arr[i].f >> arr[i].s;
		disc.pb(arr[i].f);
		disc.pb(arr[i].s);
	}
	FOR(i, 1, k) {
		cin >> op[i];
		disc.pb(op[i]);
	}
	sort(all(disc));
	disc.resize(unique(all(disc)) - disc.begin());
	seg = new node(1, size(disc));
	FOR(i, 1, n) {
		arr[i].f = lower_bound(all(disc), arr[i].f) - disc.begin() + 1;
		arr[i].s = lower_bound(all(disc), arr[i].s) - disc.begin() + 1;
	}
	FOR(i, 1, k) {
		op[i] = lower_bound(all(disc), op[i]) - disc.begin() + 1;
		seg->maxup(op[i], i);
	}
	FOR(i, 1, n) {
		pi t = arr[i];
		if (t.f > t.s) swap(t.f, t.s);
		ll val = 0;
		if (t.f != t.s) val = seg->maxq(t.f, t.s-1);
		v.pb(pi(val, i));
	}
	sort(all(v), greater<pi>());
	ll idx = k;
	for (auto [x, i]:v) {
		while (idx > x) up(op[idx--], 1);
		int flip = 0;
		if (x == 0) flip = 0;
		else flip = (arr[i].f < arr[i].s ? 1 : 0);
		flip += query(max(arr[i].f, arr[i].s), size(disc));
		ans += (flip % 2 ? disc[arr[i].s-1] : disc[arr[i].f-1]);
	}
	cout << ans;
}

• Subtask 1: 4 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65