Submission #1290890

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290890		Jawad_Akbar_JJ	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	100 / 100	1631 ms	69536 KiB

fortune_telling2

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;
const int N = (1<<20) + 1;
int A[N], B[N], T[N], idx[N], cnt[N], ft[N], Mx[N<<1], cur;

void insert(int i, int vl, int cur = 1, int st = 1, int en = N){
	if (i >= en or i < st)
		return;
	if (en - st == 1){
		Mx[cur] = vl;
		return;
	}
	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	insert(i, vl, lc, st, mid);
	insert(i, vl, rc, mid, en);
	Mx[cur] = max(Mx[cur], vl);
}

int get(int l, int r, int cur = 1, int st = 1, int en = N){
	if (l >= en or r <= st)
		return 0;
	if (l <= st and r >= en)
		return Mx[cur];
	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	return max(get(l, r, lc, st, mid), get(l, r, rc, mid, en));
}

void Add(int i){
	for (; i; i -= i & -i)
		ft[i]++;
}
void get2(int i, int &ans){
	for (; i < N; i += i & -i)
		ans += ft[i];
}

map<int,int> mp, mp2;
int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	long long n, q, Ans = 0;
	cin>>n>>q;

	for (int i=1;i<=n;i++){
		cin>>A[i]>>B[i];
		mp[A[i]];
		mp[B[i]];
	}

	for (int i=1;i<=q;i++)
		cin>>T[i], mp[T[i]];

	for (auto [i, j] : mp)
		mp2[i] = ++cur;

	vector<pair<int,int>> Quer;
	for (int i=1;i<=q;i++){
		T[i] = mp2[T[i]];
		insert(T[i], i);
		Quer.push_back({T[i], i + N});
	}

	for (int i=1;i<=n;i++){
		int a = mp2[min(A[i], B[i])], b = mp2[max(A[i], B[i])];

		idx[i] = get(a, b);
		Quer.push_back({b, i});
	}

	sort(rbegin(Quer), rend(Quer));
	for (auto [i, j] : Quer){
		if (j > N)
			Add(j - N);
		else
			get2(idx[j] + 1, cnt[j]);
	}

	for (int i=1;i<=n;i++){
		if (idx[i] != 0 and A[i] < B[i])
			swap(A[i], B[i]);
		if (cnt[i] % 2 == 0)
			Ans += A[i];
		else
			Ans += B[i];
	}
	cout<<Ans<<'\n';
}

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