Submission #933876

#	Time	Username	Problem	Language	Result	Execution time	Memory
933876		Romicro	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	0 / 100	7 ms	26460 KiB

fortune_telling2

#include <iostream>
#include <algorithm>
#include <vector>

#define endl '\n'
#define pb push_back
#define lb(vc, x) lower_bound(vc.begin(), vc.end(), x)
#define ub(vc, x) upper_bound(vc.begin(), vc.end(), x)
#define mp make_pair
#define ll long long

using namespace std;

const int MAXN = 2e5+100;

struct query{
	int i, x;
};

int max(int a, int b){
	return (a > b)? a : b;
}

bool operator<(const query &a, const query &b){
	return mp(a.x, a.i) < mp(b.x, b.i);
}

bool operator>(const query &a, const query &b){
	return mp(a.x, a.i) > mp(b.x, b.i);
}

vector<int> seg[1 << 20];

void combine(int v){
	int lc = (v << 1), rc = lc|1;

	int pl=0, pr=0;

	while(pl < seg[lc].size() and pr < seg[rc].size()){
		if(seg[lc][pl] <= seg[rc][pr]){
			seg[v].pb(seg[lc][pl]);
			pl++;
		}
		else {
			seg[v].pb(seg[rc][pr]);
			pr++;
		}
	}

	while(pl < seg[lc].size()){
		seg[v].pb(seg[lc][pl]);
		pl++;
	}

	while(pr < seg[rc].size()){
		seg[v].pb(seg[rc][pr]);
		pr++;
	}
}

int get_max(int v, int vl, int vr, int l, int r){
	if(vl > r or vr < l) return 0;

	if(l <= vl and vr <= r)
		return seg[v].back();
	
	int vm = (vl + vr) >> 1;

	int getl = get_max((v<<1), vl, vm, l, r);
	int getr = get_max((v<<1)|1, vm+1, vr, l, r);

	return max(getl, getr);
}

int count_gte(int v, int vl, int vr, int l, int r, int x){
	if(vl > r or vr < l) return 0;

	if(l <= vl and vr <= r)
		return seg[v].end() - lb(seg[v], x);
	
	int vm = (vl + vr) >> 1;

	int getl = count_gte((v<<1), vl, vm, l, r, x);
	int getr = count_gte((v<<1)|1, vm+1, vr, l, r, x);

	return getl + getr;
}	
	
int n, sn, k;
int a[MAXN], b[MAXN];

vector<query> queries;

int main(){
	ios::sync_with_stdio(0);cin.tie(0);

	cin >> n >> k;

	for(int i=0; i<n; i++)
		cin >> a[i] >> b[i];
	
	for(int i=0; i<k; i++){
		int x;
		cin >> x;

		queries.pb({i, x});
	}

	sort(queries.begin(), queries.end());	
	reverse(queries.begin(), queries.end());

	// cout << "Q: " << endl;

	// for(query q : queries)
		// cout << q.i << ' ' << q.x << endl;

	sn = 1;
	while(sn < k) sn <<= 1;

	for(int i=0; i<k; i++)
		seg[i + sn].pb(queries[i].i);
	
	for(int i=(sn - 1); i>=0; i--)
		combine(i);

	ll sm = 0;
	for(int i=0; i<n; i++){
		query qa = {0, a[i]}, qb = {0, b[i]};

		if(a[i] <= b[i])
			swap(qa, qb);

		int l = (upper_bound(queries.begin(), queries.end(), qa, greater<query>()) - queries.begin());
		int r = (upper_bound(queries.begin(), queries.end(), qb, greater<query>()) - queries.begin());
		l--;
		
		int gt = 0, mx;
		// cout << l << ' ' << r << ": ";
		if(l <= r){
			mx = get_max(1, 1, sn, l, r);

			// cout << "MX: " << mx << endl;

			gt = count_gte(1, 1, sn, r, k, mx);
		}

		// cout << gt << endl;

		if(a[i] > b[i])
			gt++;

		if(gt&1)
			// cout << b[i] << endl;
			sm += b[i];
		else 
			// cout << a[i] << endl;;
			sm += a[i];
	}

	// cout << "SEG: " << endl;
	// for(int i=1; i<2*sn; i++){
		// for(int u : seg[i]) cout << u << ' ';
		// cout << endl;
	// }

	// cout << endl;
	cout << sm << endl;

	return 0;
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'void combine(int)':
fortune_telling2.cpp:39:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  while(pl < seg[lc].size() and pr < seg[rc].size()){
      |        ~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:39:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |  while(pl < seg[lc].size() and pr < seg[rc].size()){
      |                                ~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:50:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  while(pl < seg[lc].size()){
      |        ~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:55:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |  while(pr < seg[rc].size()){
      |        ~~~^~~~~~~~~~~~~~~~

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