Submission #161992

#	Time	Username	Problem	Language	Result	Execution time	Memory
161992		nvmdava	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	596 ms	49604 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define pb push_back
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define N 200005
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007LL

int s[N][2];

int a[N];

vector<int> t[N << 2];

void build(int id, int l, int r){
	if(l == r){
		t[id] = {a[l]};
		return;
	}
	int i1 = 0, i2 = 0, id1 = id << 1, id2 = id << 1 | 1, s1, s2, m = (l + r) >> 1;
	build(id1, l, m);
	build(id2, m + 1, r);

	s1 = t[id1].size();
	s2 = t[id2].size();

	while(i1 != s1 && i2 != s2)
		if(t[id1][i1] > t[id2][i2])
			t[id].pb(t[id2][i2++]);
		else
			t[id].pb(t[id1][i1++]);
	while(i1 != s1)
		t[id].pb(t[id1][i1++]);
	while(i2 != s2)
		t[id].pb(t[id2][i2++]);
}

pair<int, int> query(int id, int l, int r, int f, int s){
	auto it = lower_bound(t[id].begin(), t[id].end(), min(f, s));
	if(it == t[id].end())
		return {0, 0};
	if(*it >= max(f, s))
		return {0, t[id].end() - it};
	if(l == r)
		return {1, 0};
	int m = (l + r) >> 1;
	auto r2 = query(id << 1 | 1, m + 1, r, f, s);
	if(r2.ff) return r2;
	auto r1 = query(id << 1, l, m, f, s);
	return {r1.ff, r1.ss ^ r2.ss};
}


int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, k;
    cin>>n>>k;
    for(int i = 1; i <= n; i++)
    	cin>>s[i][0]>>s[i][1];
    for(int i = 1; i <= k; i++)
    	cin>>a[i];

    build(1, 1, k);
    ll res = 0;
    for(int i = 1; i <= n; i++){
    	auto w = query(1, 1, k, s[i][0], s[i][1]);

    	if(w.ff && s[i][0] < s[i][1])
   			swap(s[i][0], s[i][1]);
    	res += s[i][w.ss & 1]; 
    }
    cout<<res;
}

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