Submission #1135000

#	Time	Username	Problem	Language	Result	Execution time	Memory
1135000		kamrad	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	100 / 100	1361 ms	216676 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("Ofast,unroll-loops")
//pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
#pragma GCC target("sse4")

using ll  = long long;
using ld  = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pi3 = pair<pii, int>;

#define IOS               ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define F                 first
#define S                 second
#define sz(x)             x.size()
#define all(x)            x.begin(), x.end()
#define pb                push_back
#define cl                clear
#define minr(a, b)        a = min(a, b);
#define maxr(a, b)        a = max(a, b);
#define shit              cout << "shit\n" << flush;
#define tl                while(1&1) continue;
#define FOR(i, st, nd)    for(int i = st; i <= n; i++)
#define rand(l, r)        uniform_int_distribution<int64_t>(l,r)(rng)
random_device device;     default_random_engine rng(device());

const int Mod    = 1e9 + 7; //998244353;
const int LG     = 64;
const int SQ     = 500;
const int Inf    = 2e9 + 10;
const int maxN   = 2e5 + 10;
const int maxC   = 5e5 + 10;

int a[maxN];
int b[maxN];

vector <int> quest;

set <int> num;

unordered_map <int, int> NewVal;

struct SegTree {
	struct Node {
		int mx;
		vector <int> query;
		Node() {
			mx = 0;
		}
	} t[maxC<<3];

	void Add(int id, int L, int R, int idx, int val) {
		if(idx < L or idx >= R)
			return;

		maxr(t[id].mx, val);
		if(L+1 == R) {
			t[id].query.pb(val);
			return;
		}

		int mid = (L+R)>>1;
		if(idx < mid)
			Add(2*id+0, L, mid, idx, val);
		else
			Add(2*id+1, mid, R, idx, val);
	}

	void merge(int id, int L, int R) {
		if(L+1 == R)
			return;
		int mid = (L+R)>>1;
		merge(2*id+0, L, mid);
		merge(2*id+1, mid, R);

		int ptr1 = 0;
		int ptr2 = 0;
		while(ptr1 < sz(t[2*id+0].query) and ptr2 < sz(t[2*id+1].query)) {
			if(t[2*id+0].query[ptr1] < t[2*id+1].query[ptr2]) {
				t[id].query.pb(t[2*id+0].query[ptr1]);
				ptr1++;
			}
			else {
				t[id].query.pb(t[2*id+1].query[ptr2]);
				ptr2++;
			}
		}
		while(ptr1 < sz(t[2*id+0].query)) {
			t[id].query.pb(t[2*id+0].query[ptr1]);
			ptr1++;
		}
		while(ptr2 < sz(t[2*id+1].query)) {
			t[id].query.pb(t[2*id+1].query[ptr2]);
			ptr2++;
		}
	}

	int GetMax(int id, int L, int R, int l, int r) {
		if(l >= r)
			return 0;

		if(L == l and R == r)
			return t[id].mx;

		int ans = 0;
		int mid = (L+R)>>1;
		if(l < mid)
			maxr(ans, GetMax(2*id+0, L, mid, l, min(mid, r)));
		if(r > mid)
			maxr(ans, GetMax(2*id+1, mid, R, max(l, mid), r));
		return ans;
	}

	int GetCnt(int id, int L, int R, int l, int r, int v) {
		if(L == l and R == r) {
			auto it = lower_bound(all(t[id].query), v);
			return int(t[id].query.end()-it);
		}
		int ans = 0;
		int mid = (L+R)>>1;
		if(l < mid)
			ans += GetCnt(2*id+0, L, mid, l, min(mid, r), v);
		if(r > mid)
			ans += GetCnt(2*id+1, mid, R, max(l, mid), r, v);
		return ans;
	}
} s;

void Compress() {
	int lst = 1;
	for(auto it = num.begin(); it != num.end(); it++) {
		NewVal[*it] = lst;
		lst++;
	}
}

int main() {
	IOS;

	int n, k;
	cin >> n >> k;

	for(int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i];
		num.insert(a[i]);
		num.insert(b[i]);
	}

	for(int i = 1; i <= k; i++) {
		int x;
		cin >> x;
		quest.pb(x);
		num.insert(x);
	}
	Compress();
	
	int l = sz(num);
	for(int i = 0; i < k; i++)
		s.Add(1, 1, l+1, NewVal[quest[i]], i+1);
	s.merge(1, 1, l+1);

	ll ret = 0;
	for(int i = 1; i <= n; i++) {
		bool swaped = false;
		int tmp = 0;
		if(NewVal[a[i]] > NewVal[b[i]]) {
			swap(a[i], b[i]);
			swaped = true;
			tmp = 1;
		}

		int LastFix = s.GetMax(1, 1, l+1, NewVal[a[i]], NewVal[b[i]]);
		if(LastFix)
			tmp = 1;
		int ChangeCnt = s.GetCnt(1, 1, l+1, NewVal[b[i]], l+1, LastFix);
		tmp = (tmp + (ChangeCnt % 2))%2;

		if(tmp == 0)
			ret += a[i];
		else
			ret += b[i];
	}
	cout << ret;
}

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