Submission #1137801

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137801		SmuggingSpun	Fortune Telling 2 (JOI14_fortune_telling2)	C++20	0 / 100	3 ms	5952 KiB

fortune_telling2

#include<bits/stdc++.h>
#define taskname "B"
using namespace std;
typedef long long ll;
int n, k;
namespace sub1{
	const int lim = 1e3 + 5;
	int a[lim][2];
	void solve(){
		for(int i = 1; i <= n; i++){
			cin >> a[i][0] >> a[i][1];
		}
		for(int _ = 0; _ < k; _++){
			int x;
			cin >> x;
			for(int i = 1; i <= n; i++){
				if(a[i][0] <= x){
					swap(a[i][0], a[i][1]);
				}
			}
		}
		ll ans = 0;
		for(int i = 1; i <= n; i++){
			ans += a[i][0];
		}
		cout << ans;
	}
}
namespace sub23{
	const int lim = 2e5 + 5;
	int a[lim], b[lim], X[lim], log_v[lim], bit[lim], spt_x_pos[lim][18];
	pair<int, int>sorted_x[lim];
	vector<int>query[lim];
	int get_max_x_pos(int l, int r){
		if(l > r){
			return 0;
		}
		int t = log_v[r - l + 1];
		return max(spt_x_pos[l][t], spt_x_pos[r - (1 << t) + 1][t]);
	}
	void update(int p){
		for(; p <= k; p += p & -p){
			bit[p]++;
		}
	}
	int get(int p){
		int ans = 0;
		for(; p > 0; p -= p & -p){
			ans += bit[p];
		}
		return ans;
	}
	void solve(){
		for(int i = 1; i <= n; i++){
			cin >> a[i] >> b[i];
		}
		log_v[0] = -1;
		for(int i = 1; i <= k; i++){
			cin >> X[i];
			sorted_x[i] = make_pair(X[i], i);
			log_v[i] = log_v[i >> 1] + 1;
		}
		sort(sorted_x + 1, sorted_x + k + 1);
		for(int i = 1; i <= k; i++){
			spt_x_pos[i][0] = sorted_x[i].second;
		}
		for(int j = 1; j < 18; j++){
			for(int i = 1; i + (1 << j) - 1 <= n; i++){
				spt_x_pos[i][j] = max(spt_x_pos[i][j - 1], spt_x_pos[i + (1 << (j - 1))][j - 1]);
			}
		}
		ll ans = 0;
		for(int i = 1; i <= n; i++){
			if(a[i] == b[i]){
				ans += a[i];
				continue;
			}
			query[get_max_x_pos(lower_bound(sorted_x + 1, sorted_x + k + 1, make_pair(min(a[i], b[i]), -1)) - sorted_x, lower_bound(sorted_x + 1, sorted_x + k + 1, make_pair(max(a[i], b[i]), -1)) - sorted_x - 1)].emplace_back(i);
		}
		memset(bit, 0, sizeof(bit));
		for(int i = k; i > -1; update(lower_bound(sorted_x + 1, sorted_x + k + 1, make_pair(X[i], -1)) - sorted_x), i--){
			for(int& j : query[i]){
				if(i == 0){
					ans += (((k - get(lower_bound(sorted_x + 1, sorted_x + k + 1, make_pair(max(a[j], b[j]), -1)) - sorted_x - 1)) & 1) ? b[j] : a[j]);
					continue;
				}
				ans += (((k - i - get(lower_bound(sorted_x + 1, sorted_x + k + 1, make_pair(max(a[j], b[j]), -1)) - sorted_x - 1)) & 1) ? min(a[j], b[j]) : max(a[j], b[j]));
			}
		}
		cout << ans;
	}
}
int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	if(fopen(taskname".inp", "r")){
		freopen(taskname".inp", "r", stdin);
	}
	cin >> n >> k;
	if(max(n, k) <= 1000){
		sub23::solve();
	}
	else{
		sub23::solve();
	}
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:96:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |                 freopen(taskname".inp", "r", stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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