Submission #233690

#	Time	Username	Problem	Language	Result	Execution time	Memory
233690		almogwald	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	566 ms	29828 KiB

fortune_telling2

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#define forr(i,a,b,c) for(int i=a;i<b;i+=c)
#define fort(i,a,b) forr(i,a,b,1)
#define forn(i,n) fort(i,1,n)
#define fori(i,n) fort(i,0,n)
#define forrb(i,a,b,c) for(int i=b-1;i>=a;i-=c)
#define fortb(i,a,b) forrb(i,a,b,1)
#define fornb(i,n) fortb(i,1,n)
#define forib(i,n) fortb(i,0,n)
using namespace std;
#define into(x) cin >> x;
typedef vector<int> veci;
typedef long long lol;
typedef pair<lol,lol> point;
#define def(x) lol x; into(x)

#define logn 20
int main() {
	ios::sync_with_stdio();
	def(n) def(m)
	vector<point> x,y;
	fori(i, n) {
		def(a) def(b)
			x.push_back({ a,b });
	}
	fori(i, m) {
		def(a)
			y.push_back({ a,i });
	}
	sort(y.begin(), y.end());
	vector<veci> arr(logn, veci(m+1));
	
	veci xx(m);
	set<point> r;
	forib(i, m) {
		int ii = y[i].second+1;
		int sum = 0;
		fori(j, logn) {
			if (ii % 2 == 1) {
				sum += arr[j][ii];
				ii++;
			}
			ii /= 2;
		}
		xx[i] = sum;
		ii = y[i].second;
		fori(j, logn) {
			arr[j][ii]++;
			ii /= 2;
		}
	}
	fori(i, m) {
		arr[0][i] = y[i].second;
	}
	forn(j, logn) {
		fori(i, (m / 2) + 1) {
			arr[j][i] = max(arr[j - 1][2 * i], arr[j - 1][2 * i + 1]);
		}
	}
	veci op(m);
	fori(i, m) {
		op[y[i].second] = i;
	}
	lol sum = 0;
	fori(i, n) {
		int low = 0, high = m;
		int small = min(x[i].first, x[i].second);
		while (low < high) {
			int mid = (low + high) / 2;
			if (y[mid].first < small) {
				low = mid + 1;
			}
			else {
				high = mid;
			}
		}
		int lower = low;
		low = -1, high = m - 1;
		int big = max(x[i].first, x[i].second);
		while (low < high) {
			int mid = (low + high+1) / 2;
			if (y[mid].first >= big) {
				high = mid - 1;
			}
			else {
				low = mid;
			}
		}
		int higer = high;
		int best = -1;
		fori(j, logn) {
			if (lower > higer) {
				break;
			}
			if (lower % 2 == 1) {
				best = max(best,arr[j][lower]);
				lower++;
			}
			if (higer % 2 == 0) {
				best = max(best, arr[j][higer]);
				higer--;
				if (higer < 0) {
					break;
				}
			}
			lower /= 2;
			higer /= 2;
		}
		if (best == -1) {
			int num = m - lower;
			if (num % 2 == 1) {
				sum += x[i].second;
			}
			else {
				sum += x[i].first;
			}
		}
		else {
			int num = xx[op[best]];
			if (num % 2 == 1) {
				sum += small;
			}
			else {
				sum += big;
			}
		}
	}
	cout << sum << endl;
	return 0 ;
}

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