Submission #1238566

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238566		nlsosad	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	100 / 100	1269 ms	80640 KiB

fortune_telling2

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

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