Submission #28891

#	Time	Username	Problem	Language	Result	Execution time	Memory
28891		cdemirer	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	35 / 100	706 ms	58648 KiB

fortune_telling2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<pair<int, int> > vii;
typedef vector<vector<pair<int, int> > > vvii;
#define pb(x) push_back(x)
#define mp(x, y) make_pair(x, y)

int twopow[22] = {0};
// x is always 2
int mypow(int x, int e) {
	if (twopow[e]) return twopow[e];
	if (e == 0) return 1;
	int a = mypow(x, e/2);
	return (twopow[e] = (e % 2 == 0) ? a*a : a*a*x);
}

int N, K;
vii cisimler;
map<int, int> tbl;
map<int, int> revtbl;
int queries[200002];
vii qs;
int rmqtbl[200002][19];
int rminqtbl[200002][19];
vii tickets;
bool kucuk[200002];
int lg2[200002];

int rmq(int a, int b) {
	//cerr << "max of: ";
	//for (int i = a; i <= b; i++) {
		//cerr << rmqtbl[i][0] << " ";
	//}
	int pop = b - a + 1;
	int e = (int)lg2[pop];
	int a2 = b - mypow(2, e) + 1;
	return max(rmqtbl[a][e], rmqtbl[a2][e]);
}
int rminq(int a, int b) {
	int pop = b - a + 1;
	int e = (int)lg2[pop];
	int a2 = b - mypow(2, e) + 1;
	return min(rminqtbl[a][e], rminqtbl[a2][e]);
}
int binsrc(int x) {
	int l = 0, r = K;
	while (r > l) {
		int mid = (l + r) / 2;
		if (qs[mid].first >= x) r = mid;
		else l = mid+1;
	}
	return l;
}

int bit[524289] = {0};
void bitinc(int x) {
	x += 2;
	while (x <= 524288) {
		bit[x]++;
		x += x & -x;
	}
}
int bitget(int x) {
	x += 2;
	int sum = 0;
	while (x > 0) {
		sum += bit[x];
		x -= x & -x;
	}
	return sum;
}

int main(int argc, char **argv) {

	//freopen("input", "r", stdin);
	//freopen("output", "w", stdout);

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int lgcur = 1;
	for (int i = 1; i < 18; i++) {
		int lim = mypow(2, i);
		for ( ; lgcur < lim; lgcur++) {
			lg2[lgcur] = i-1;
		}
	}

	cin >> N >> K;
	set<int> S;
	for (int i = 0; i < N; i++) {
		int a, b; cin >> a >> b;
		cisimler.pb(mp(a, b));
		S.insert(a);
		S.insert(b);
	}
	for (int i = 0; i < K; i++) {
		int a; cin >> a;
		queries[i] = a;
		qs.pb(mp(a, i));
		S.insert(a);
	}
	int c = 0;
	while ( ! S.empty() ) {
		int x = *S.begin();
		S.erase(S.begin());
		tbl[x] = c;
		revtbl[c] = x;
		c++;
	}
	for (int i = 0; i < N; i++) {
		cisimler[i].first = tbl[cisimler[i].first];
		cisimler[i].second = tbl[cisimler[i].second];
		//cerr << i << " " << revtbl[cisimler[i].first] << " " << revtbl[cisimler[i].second] << "\n";
	}
	for (int i = 0; i < K; i++) {
		queries[i] = tbl[queries[i]];
		qs[i].first = tbl[qs[i].first];
	}
	sort(qs.begin(), qs.end());
	for (int i = 0; i < K; i++) {
		rmqtbl[i][0] = qs[i].second;
		rminqtbl[i][0] = qs[i].second;
	}
	for (int e = 1; e < 18; e++) {
		int off = mypow(2, e-1);
		for (int i = 0; i < K; i++) {
			if (i+2*off > K) break;
			rmqtbl[i][e] = max(rmqtbl[i][e-1], rmqtbl[i+off][e-1]);
			rminqtbl[i][e] = min(rminqtbl[i][e-1], rminqtbl[i+off][e-1]);
		}
	}
	for (int i = 0; i < N; i++) {
		int cmin = min(cisimler[i].first, cisimler[i].second);
		int cmax = max(cisimler[i].first, cisimler[i].second);
		int ls = binsrc(cmin);
		//cerr << cmin << endl;
		int hs = binsrc(cmax);
		if (ls == K) {
			kucuk[i] = (cmin == cisimler[i].first);
			continue;
		} 
		if (hs == K) {
			kucuk[i] = false;
			continue;
		}
		//cerr << "ls : " << ls << " hs : " << hs << endl;
		if (ls != hs) {
			int q = rmq(ls, hs-1);
			//cerr << " is " << q << endl;
			tickets.pb(mp(q+1, i));
		}
	 	else {
			int q = rminq(ls, K-1);
			//cerr << ls << " " << q << endl;
			if (cmin == cisimler[i].first) {
				tickets.pb(mp(q+1, i));
			}
			else {
				tickets.pb(mp(q, i));
			}
		}
	}
	/*for (int i = 0; i < tickets.size(); i++) {
		cerr << tickets[i].first << " " << tickets[i].second << endl;
	}*/
	int cur = K;
	int tot = 0;
	sort(tickets.begin(), tickets.end());
	for (int i = tickets.size()-1; i >= 0; i--) {
		int x = tickets[i].second;
		while (cur > tickets[i].first) {
			cur--;
			bitinc(queries[cur]);
			tot++;
		}
		int lim = max(cisimler[x].first, cisimler[x].second);
		int a = tot - bitget(lim-1);
		//if (x == 3) cerr << lim << "\n";
		kucuk[x] = (a % 2 == 1);
	}
	ll sum = 0;
	for (int i = 0; i < N; i++) {
		//cerr << kucuk[i] << endl;
		if (kucuk[i]) {
			sum += revtbl[ min(cisimler[i].first, cisimler[i].second) ];
		}
		else {
			sum += revtbl[ max(cisimler[i].first, cisimler[i].second) ];
		}
	}
	cout << sum << endl;

	return 0;
}

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