Submission #73763

#	Time	Username	Problem	Language	Result	Execution time	Memory
73763		shoemakerjo	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	2204 ms	165656 KiB

fortune_telling2

#include <bits/stdc++.h>

using namespace std;

#define maxn 200010
#define pii pair<int, int>
#define ppi pair<pii, pii>
#define mp make_pair
int N, K;

int a[maxn];
int b[maxn];
int t[maxn];

vector<ppi> events;
int ans[maxn];

int seg[maxn*4]; //store the minimum value
int ct = 0;
int inf = 1234567890;
#define ll long long

int qu(int qs, int qe, int ss, int se, int si) {
	if (qs > qe || ss > se) return inf;
	if (qs > se || qe < ss) return inf;
	if (qs <= ss && se <= qe) return seg[si];
	int mid = (ss+se)/2;
	return min(qu(qs, qe, ss, mid, si*2+1), 
		qu(qs, qe, mid+1, se, si*2+2));
}

int query(int qs, int qe) {
	return qu(qs, qe, 0, K, 0);
}

void up(int spot, int val, int ss, int se, int si) {
	if (ss == se) {
		seg[si] = min(seg[si], val);
		return;
	}
	int mid = (ss+se)/2;
	if (spot <= mid) up(spot, val, ss, mid, si*2+1);
	else up(spot, val, mid+1, se, si*2+2);
	seg[si] = min(seg[si*2+1], seg[si*2+2]);
}

void update(int spot, int val) {
	up(spot, val, 0, K, 0);
}

int walkdown(int goal, int ss, int se, int si) {
	//wnat last index s.t. the value is < it
	if (ss == se) return ss;
	int mid = (ss+se)/2;
	if (seg[si*2+2] < goal) {
		//something is good enough in the left, go there
		return walkdown(goal, mid+1, se, si*2+2);
	}
	else return walkdown(goal, ss, mid, si*2+1);
}


int BIT[maxn];

int bq(int val) {
	int res = 0;
	while (val > 0) {
		res += BIT[val];
		val -= val & (-val);
	}
	return res;
}

int bquery(int lo, int hi) {
	lo++;
	hi++;
	return bq(hi) - bq(lo-1);
}

void bupdate(int spot) {
	spot++;
	while (spot < maxn) {
		BIT[spot]++;
		spot += spot & (-spot);
	}
}


map<int, int> deco;
map<int, int> goback;

int main() {
	fill(seg, seg+maxn*4, inf);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> N >> K;
	set<int> vals;
	for (int i = 0; i < N; i++) {
		cin >> a[i] >> b[i];
		vals.insert(a[i]);
		vals.insert(b[i]);
	}
	vector<int> vvec;
	for (int vv : vals) {
		goback[ct] = vv;
		deco[vv] = ct++;
		vvec.push_back(vv);
	}
	for (int i = 0; i < N; i++) {
		a[i] = deco[a[i]];
		b[i] = deco[b[i]];
		events.push_back(mp(mp(min(a[i], b[i]), 0), mp(max(a[i], b[i]), i)));
	}

	for (int i = 0; i < K; i++) {
		cin >> t[i];
		int indo = upper_bound(vvec.begin(), vvec.end(), t[i]) -
			vvec.begin()-1;
		t[i] = indo;
		events.push_back(mp(mp(t[i], 1), mp(-1, i)));
	}
	sort(events.begin(), events.end());
	reverse(events.begin(), events.end());

	for (int i = 0; i < events.size(); i++) {
		int tp = events[i].first.second;
		if (tp == 0) {

			//this is one of the queries
			//(lol we don't need indices anymore)
			int ai = events[i].first.first;
			int bi = events[i].second.first;
			int indo = events[i].second.second;
			ai = a[indo];
			bi = b[indo];
			// cout << "got indo: " << indo << endl;

			if (ai == bi) {
				ans[indo] = ai;
				continue;
			}

			bool flip = ai <= bi;
			int mx = max(ai, bi);

			int nx = -1;
			if (query(0, K) >= mx) {
				//no last value
			}
			else {
				nx = walkdown(mx, 0, K, 0);

			}
			

			int avals = bquery(nx+1, K);
			if (nx == -1 && ai != mx) avals++; //think this works
			avals %= 2;
			if (ai == mx) {
				if (avals) ans[indo] = bi;
				else ans[indo] = ai;
			}
			else {
				if (avals) ans[indo] = ai;
				else ans[indo] = bi;
			}


		}
		else {
			update(events[i].second.second, events[i].first.first);
			bupdate(events[i].second.second);
		}
	}
	ll fans = 0;
	// cout << "answers: " << endl;
	for (int i = 0; i < N; i++) {
		// cout << ans[i] << " ";
		// cout << "   " << i << ": " << a[i] << " " << b[i] << " : " << ans[i] << endl;
		fans += goback[ans[i]] + 0LL;
	}
	// cout << endl;
	cout << fans << '\n';
	cout.flush();
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:125:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < events.size(); i++) {
                  ~~^~~~~~~~~~~~~~~
fortune_telling2.cpp:143:9: warning: unused variable 'flip' [-Wunused-variable]
    bool flip = ai <= bi;
         ^~~~

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