Submission #934382

#	Time	Username	Problem	Language	Result	Execution time	Memory
934382		Romicro	Fortune Telling 2 (JOI14_fortune_telling2)	C++17	100 / 100	455 ms	59504 KiB

fortune_telling2

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

#define endl '\n'
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define lc (v<<1)
#define rc (v<<1)|1
#define lb(vc, x) lower_bound(vc.begin(), vc.end(), x)
#define ub(vc, x) upper_bound(vc.begin(), vc.end(), x)
#define ll long long

using namespace std;

typedef pair<int, int> pii;

const int MAXN = 2e5+100;

vector<int> seg[1 << 20];
int a[MAXN], b[MAXN];
vector<pii> ques;

int n, sn, k;
ll sm;

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

void merge(int v){
	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(lc, vl, vm, l, r);
	int getr = get_max(rc, vm+1, vr, l, r);

	return max(getl, getr);
}
	
int cnt_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 = cnt_gte(lc, vl, vm, l, r, x);
	int getr = cnt_gte(rc, vm+1, vr, l, r, x);

	return getl + getr;
}

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;
		ques.pb(mp(x, i));
	}

	sort(ques.begin(), ques.end());


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

	for(int i=0; i<k; i++)
		seg[i + sn].pb(ques[i].sc);

	for(int i=(sn-1); i>=1; i--)
		merge(i);

	for(int i=0; i<n; i++){
		pii qa = mp(a[i], 0), qb = mp(b[i], 0);

		if(qa >= qb)
			swap(qa, qb);

		int l = lb(ques, qa) - ques.begin();
		int r = lb(ques, qb) - ques.begin();
		
		l++;

		// cout << l << ' ' << r << ' ';

		int cnt=0, mx=0;
		if(l <= r)
			mx = get_max(1, 1, sn, l, r);

		// cout << mx << ' ';
		if(r < k)
			cnt = cnt_gte(1, 1, sn, r+1, k, mx);
		

		// cout << cnt << ": ";

		if(a[i] <= b[i] and l<=r)
			cnt++;

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

	}

	cout << sm << endl;

	return 0;
}

Compilation message (stderr)

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

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