제출 #405695

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

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

const int INF = 1e18;

struct FenwickTree{
	vector<bool> a; int n, s;
	FenwickTree(int N){ a.resize((n=N)+1); }
	void add(int i){
		for(++i; i<=n; i+=i&-i) a[i] = a[i] ^ 1;
	}
	int get(int i){
		for(s=0; i>=1; i-=i&-i) s ^= a[i];
		return s;
	}
	int get(int i, int j){ return get(j+1) ^ get(i); }
};

struct SegmentTree{
	vector<int> a; int sz = 1;
	SegmentTree(vector<int> &v){
		while(sz < (int)v.size()) sz += sz;
		a.assign(2*sz, -1);
		build(v, 0, 0, sz);
	}
	void build(vector<int> &v, int x, int lx, int rx){
		if(rx-lx==1){
			if(lx < (int)v.size()) a[x] = v[lx];
			return;
		}
		int mx = (lx + rx) / 2;
		build(v, 2*x+1, lx, mx);
		build(v, 2*x+2, mx, rx);
		a[x] = max(a[2*x+1], a[2*x+2]);
	}
	void update(int i, int v, int x, int lx, int rx){
		if(rx-lx==1) return void(a[x] = v);
		int mx = (lx + rx) / 2;
		if(i < mx) update(i, v, 2*x+1, lx, mx);
		else update(i, v, 2*x+2, mx, rx);
		a[x] = max(a[2*x+1], a[2*x+2]);
	}
	void update(int i, int v){ update(i, v, 0, 0, sz); }
	int lastGreater(int v, int x, int lx, int rx){
		if(rx-lx==1) return (a[x] >= v ? lx : -1);
		int mx = (lx + rx) / 2;
		if(a[2*x+2] >= v) return lastGreater(v, 2*x+2, mx, rx);
		else return lastGreater(v, 2*x+1, lx, mx);
	}
	int lastGreater(int v){ return lastGreater(v, 0, 0, sz); }
};

signed main(){
	cin.tie(0)->sync_with_stdio(0);
	int n, k; cin >> n >> k;
	array<int, 2> a[n], s[k];
	for(auto &i : a) cin >> i[0] >> i[1];
	vector<int> b(k);
	for(int i=0; i<k; ++i) cin >> b[i], s[i] = {b[i], i};

	sort(s, s+k);
	int p = k, res = 0;
	
	sort(a, a+n, [&](array<int, 2> &x, array<int, 2> &y){
		return max(x[0], x[1]) > max(y[0], y[1]);
	});

	SegmentTree st(b);
	FenwickTree f(k);

	for(auto &i : a){
		int x = i[0], y = i[1];
		if(x > y) swap(x, y);
		while(p && s[p-1][0] >= y){
			--p;
			st.update(s[p][1], -1);
			f.add(s[p][1]);
		}
		int j = st.lastGreater(x);
		if(j < 0) res += i[f.get(j+1, k-1)];
		else{
			if(i[0] > i[1]) swap(i[0], i[1]);
			res += i[f.get(j+1, k-1) ^ 1];
		}
	}

	cout << res;

}

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