제출 #1246012

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1246012		nguyenhuythach	운세 보기 2 (JOI14_fortune_telling2)	C++20	0 / 100	3 ms	5184 KiB

fortune_telling2

//cre: khanh nguyen
// luoi code qua -_-

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define F first
#define S second
#define pb push_back
#define pii pair<int, int>
 
const int N = 2e5 + 5; 

struct SegTree {
	int n;
	vector<int> st;
	
	SegTree() {}
	
	SegTree(int n) : n(n) {
		st.resize(4 * n + 5); 
	}
	
	void update(int id, int l, int r, int i, int x) {
		if (l == r) {
			st[id] = max(st[id], x); 
			return; 
		}
		int mid = (l + r) / 2; 
		if (i <= mid) update(id * 2, l, mid, i, x); 
		else update(id * 2 + 1, mid + 1, r, i, x); 
		st[id] = max(st[id * 2], st[id * 2 + 1]); 
	}
	
	int get(int id, int l, int r, int u, int v) {
		if (u > v) return 0;
		if (l > v || r < u) return 0; 
		if (u <= l && r <= v) {
			return st[id]; 
		}
		int mid = (l + r) / 2;
		return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v)); 
	}
} st;

struct BIT {
	int n; 
	vector<int> bit;
	
	BIT() {}
	BIT(int n) : n(n) {
		bit.resize(n + 3); 
	}
	
	void update(int id, int val) {
		for (int i = id; i <= n; i += (i & -i)) bit[i] += val; 
	}
	
	int get(int id) {
		int ret = 0;
		for (int i = id; i; i -= (i & -i)) ret += bit[i]; 
		return ret;
	}
} bit;

int n, m; 
pii a[N]; 
int c[N]; 
vector<int> cmp; 
int t[N]; 
int res[N]; 
int sz;

struct Event {
	int x, sign, id;
};

vector<Event> ev[N]; 

signed main() {
	ios_base::sync_with_stdio(0); 
	cin.tie(0); 
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].F >> a[i].S;
		cmp.pb(a[i].F); 
		cmp.pb(a[i].S); 
	}
	for (int i = 1; i <= m; i++) {
		cin >> c[i];
		cmp.pb(c[i]); 
	}
	sort(cmp.begin(), cmp.end());
	cmp.erase(unique(cmp.begin(), cmp.end()), cmp.end()); 
	sz = cmp.size(); 
	st = SegTree(sz);
	int sz = cmp.size(); 
	for (int i = 1; i <= m; i++) {
		int id = upper_bound(cmp.begin(), cmp.end(), c[i]) - cmp.begin(); 
		st.update(1, 1, sz, id, i); 
	}
	for (int i = 1; i <= n; i++) {
		int ida, idb;
		ida = upper_bound(cmp.begin(), cmp.end(), a[i].F) - cmp.begin(); 
		idb = upper_bound(cmp.begin(), cmp.end(), a[i].S) - cmp.begin(); 
		if (ida > idb) swap(ida, idb); 
		t[i] = st.get(1, 1, sz, ida, idb - 1);  
		//cout << t[i] << ' ';
		ev[t[i]].pb({idb, -1, i}); 
		ev[m].pb({idb, 1, i}); 
	} // cout << '\n';
	bit = BIT(sz);
	for (int i = 1; i <= m; i++) {
		int id = upper_bound(cmp.begin(), cmp.end(), c[i]) - cmp.begin(); 
		bit.update(id, 1); 
		for (auto it : ev[i]) {
			res[it.id] += (bit.get(sz) - bit.get(it.x - 1)) * it.sign;  
		}
	}
	int sum=0;
	for (int i = 1; i <= n; i++) {
		int ans;
		if (t[i]) {
			ans = max(a[i].F, a[i].S); 
			if (res[i] & 1) ans = min(a[i].F, a[i].S);
		}
		else {
			ans = a[i].F;
			if (res[i] & 1) ans = a[i].S; 
		}
		sum+=ans;
	}
	cout << sum;
}

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