oj.uz

답안 #405693

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
405693 2021-05-16T19:05:43 Z ritul_kr_singh 운세 보기 2 (JOI14_fortune_telling2) C++17
0 / 100
 1 ms 332 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sp << ' ' <<
#define nl << '\n'

const int INF = 1e18;

struct FenwickTree{
	vector<int> 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;
	}
	bool get(int i){
		for(s=0; i>=1; i-=i&-i) s ^= a[i];
		return s;
	}
	bool 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 lx;
		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 >= k || b[j] < x) res += i[0];
		else{
			if(i[0] > i[1]) swap(i[0], i[1]);
			res += i[f.get(j+1, k-1) ^ 1];
		}
	}

	cout << res;

}

Subtask #1
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -