Submission #1275175

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

fortune_telling2

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 4e5+5;
int n,k,b[N],l[N],r[N],bits[N],state[N];
pii a[N];
vector<int>nen,kaori[N],emilia[N];
void update(int u){
	if(u == 0) u++;
	while(u <= nen.size()){
		bits[u]++;
		u += u & (-u);
	}
}
int get(int u){
	int sum = 0;
	while(u > 0){
		sum += bits[u];
		u -= u & (-u);
	}
	return sum;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> k;
	for(int i = 1; i <= n; i++){
	    cin >> a[i].fi >> a[i].se;
	    if(a[i].fi > a[i].se){
	    	swap(a[i].fi,a[i].se);
	    	state[i] = 1;
		}
		nen.push_back(a[i].fi);
		nen.push_back(a[i].se);
    }
	sort(nen.begin(),nen.end());
	nen.erase(unique(nen.begin(),nen.end()),nen.end());
	for(int i = 1; i <= k; i++) cin >> b[i];
	for(int i = 1; i <= k; i++) b[i] = upper_bound(nen.begin(),nen.end(),b[i])-nen.begin();
	for(int i = 1; i <= n; i++){
		a[i].fi = lower_bound(nen.begin(),nen.end(),a[i].fi)-nen.begin()+1;
		a[i].se = lower_bound(nen.begin(),nen.end(),a[i].se)-nen.begin()+1;
		r[i] = k;
	}
	while(true){
		int cnt = 0;
		for(int i = 1; i <= k; i++) kaori[i].clear();
		for(int i = 1; i <= n; i++){
			if(l[i] < r[i]){
				kaori[(l[i]+r[i]+1)/2].push_back(i);
				cnt++; 
			}
		}
		if(cnt == 0) break;
		for(int i = 1; i <= nen.size(); i++) bits[i] = 0;
		for(int i = k; i >= 1; i--){
			update(b[i]);
			for(int u: kaori[i]){
				if(get(a[u].se-1) > get(a[u].fi-1)) l[u] = i;
				else r[u] = i-1;
			}
		}
	}
	for(int i = 1; i <= nen.size(); i++) bits[i] = 0;
	long long ans = 0;
	for(int i = 1; i <= n; i++){
		if(l[i] == k) ans += a[i].se;
	    else emilia[l[i]+1].push_back(i);
	}
	for(int i = k; i >= 1; i--){
		update(b[i]);
		for(int u: emilia[i]){
			int chancode = k-i+1-get(a[u].se-1);
			if(l[u] == 0){
				chancode += state[u];
				if(chancode % 2 == 0) ans += nen[a[u].fi-1];
				else ans += nen[a[u].se-1];
			}
			else{
				if(chancode % 2 == 1) ans += nen[a[u].fi-1];
				else ans += nen[a[u].se-1];
			}
		}
	}
	cout << ans;
}

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