Submission #1238559

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238559		nlsosad	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	0 / 100	4 ms	5188 KiB

fortune_telling2

#include <bits/stdc++.h>
// #define int long long
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> iset;
#define f first
#define s second
int a[200001], b[200001];
int oa[200001], ob[200001];
pair<int, int> t[200001], ot[200001];
int luu[200001];
int res[200001];
vector<pair<int, int>> tam[200002];
struct segtree{
	int n;
	vector<int> tr;
	segtree(int m){
		n = m;
		tr.resize(4*n);
	}
	void build(int node, int start, int end){
		if(start==end){
			tr[node] = luu[end];
		}else{
			int mid = (start+end)/2;
			build(2*node, start, mid);
			build(2*node+1, mid+1, end);
			tr[node] = max(tr[2*node], tr[2*node+1]);		
		}
	}
	int query(int node, int start, int end, int l, int r){
		if(start > r or end < l){
			return 0;
		}
		if(l<=start and end <= r){
			return tr[node];
		}
		int mid = (start+end)/2;
		return max(query(2*node, start, mid, l, r), query(2*node+1, mid+1, end, l, r));
	}
};
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n, k;
	cin >> n >> k;
	map<int,int> mp;
	for (int i = 1;i<=n;++i){
		cin >> a[i] >> b[i];
		oa[i] = a[i], ob[i] = b[i];
		mp[a[i]] = -1;
	}
	for (int i = 1;i<=n;++i){
		mp[b[i]] = -1;
	}
	for (int i = 1;i<=k;++i){
		cin >> t[i].f;
		ot[i].f = t[i].f;
		t[i].s = i;
		mp[t[i].f] = -1;
	}
	int moc = 1;
	for (auto &i:mp){
		i.second = moc++;
	}
	for (int i= 1;i<=n;++i){
		a[i] = mp[a[i]];
		b[i] = mp[b[i]];
	}
	for (int i = 1;i<=k;++i){
		t[i].f = mp[t[i].f];
	}
	sort(t+1, t+k+1);
	for (int i = 1;i<=k;++i){
		luu[i] = t[i].s;
	}
	segtree st(k);
	st.build(1, 1, k);
	// cout << st.query(1, 1, k, 1, 1);return 0;
	for (int i = 1;i<=n;++i){
		res[i] = oa[i];
		int dau = lower_bound(t+1, t+k+1, make_pair(min(a[i], b[i]), -1)) - t;
		int cuoi = lower_bound(t+1, t+k+1, make_pair(max(a[i], b[i]), -1)) - t;
		// cout << dau << ' ' << cuoi << '\n';
		cuoi--;
		int tmp = st.query(1, 1, k, dau, cuoi);
		if(tmp!=0){
			if(oa[i]<ob[i]){
				res[i] = ob[i];
				tam[tmp+1].push_back({ob[i], i});
			}else{
				tam[tmp+1].push_back({oa[i], i});
			}
		}
	}
	iset s;
	for (int i = k;i>=1;--i){
		pair<int, int> l = make_pair(ot[i].f, i);
		s.insert(l);
		for (auto [v, id]:tam[i]){
			// cout << v << ' ' << id << ' ' << i << '\n';
			int cnt = s.size()-s.order_of_key(make_pair(v, -1));
			// cout << cnt << '\n';
			cnt %= 2;
			if(cnt==1){
				if(res[id]==oa[id])res[id] = ob[id];
				else res[id] = oa[id];
			}
		}
	}
	/*for (int i = 1;i<=k;++i){
		cout << t[i].f <<
	}
	int sol = 0;
	for (int i = 1;i<=n;++i){
		cout << a[i] << ' ';
	}
	cout << '\n';
	for (int i = 1;i<=n;++i){
		cout << b[i] << ' ';
	}
	cout << '\n';*/
	long long sol = 0;
	for (int i = 1;i<=n;++i){
		sol += res[i];
		// cout << res[i] << ' ';
	}
	cout << sol;
}

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