제출 #161990

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
161990		nvmdava	운세 보기 2 (JOI14_fortune_telling2)	C++17	100 / 100	635 ms	55140 KiB

fortune_telling2

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

int s[N][2];

int t[N];

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

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

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

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

pair<int, int> query(int id, int l, int r, int f, int s){
	auto it = lower_bound(seg[id].begin(), seg[id].end(), min(f, s));
	if(it == seg[id].end())
		return {0, 0};
	if(*it >= max(f, s))
		return {0, seg[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 == 1) 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>>t[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)
    		if(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