Submission #669228

#	Time	Username	Problem	Language	Result	Execution time	Memory
669228		penguin133	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	0 / 100	1 ms	340 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pi pair<int, int>
#define pii pair<int, pair<int, int> > 
#define fi first
#define se second
int n,m,q;
int ft[200005];
void upd(int p, int v){
	for(;p<=m;p+=(p & -p))ft[p] += v;
}

int query(int p){
	int sum = 0;
	for(;p;p-=(p & -p))sum += ft[p];
	return sum;
}

pi A[200005];
bool cmp(pi a, pi b){
	return max(a.fi, a.se) < max(b.fi, b.se);
}
pi Q[200005];
void solve(){
	cin >> n >> m;
	for(int i=1;i<=n;i++)cin >> A[i].fi >> A[i].se;
	sort(A+1, A+n+1, cmp);
	for(int i=1;i<=m;i++)cin >> Q[i].fi, Q[i].se = i, upd(i, 1);
	sort(Q+1, Q+m+1);
	int in = 1, cur = 0;
	Q[0].fi = -1e9;
	int ans = 0;
	for(int i=1;i<=n;i++){
		while(in <= m && Q[in].fi < max(A[i].fi, A[i].se))cur = max(cur, Q[in].se), upd(Q[in].se, -1), in++;
		int tmp;
		if(Q[in-1].fi < min(A[i].fi, A[i].se)){
			tmp = query(m);
			ans += (tmp%2 ? A[i].se : A[i].fi);
		}
		else {
			tmp = query(m) - query(cur);
			ans += (tmp%2 ? min(A[i].fi, A[i].se) : max(A[i].fi, A[i].se));
		}
		//cout << ans << ' ' << A[i].fi << ' ' << A[i].se << '\n';
	}
	cout << ans;
}
 
main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Compilation message (stderr)

fortune_telling2.cpp:50:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   50 | main(){
      | ^~~~

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