oj.uz

Submission #73763

# Submission time Handle Problem Language Result Execution time Memory
73763 2018-08-28T23:34:23 Z shoemakerjo Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 2204 ms 165656 KB 
#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

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3576 KB Output is correct
2 Correct 8 ms 3824 KB Output is correct
3 Correct 8 ms 4096 KB Output is correct
4 Correct 7 ms 4192 KB Output is correct
5 Correct 8 ms 4224 KB Output is correct
6 Correct 8 ms 4256 KB Output is correct
7 Correct 9 ms 4420 KB Output is correct
8 Correct 10 ms 4420 KB Output is correct
9 Correct 9 ms 4424 KB Output is correct
10 Correct 6 ms 4424 KB Output is correct
11 Correct 7 ms 4424 KB Output is correct
12 Correct 9 ms 4424 KB Output is correct
13 Correct 9 ms 4456 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3576 KB Output is correct
2 Correct 8 ms 3824 KB Output is correct
3 Correct 8 ms 4096 KB Output is correct
4 Correct 7 ms 4192 KB Output is correct
5 Correct 8 ms 4224 KB Output is correct
6 Correct 8 ms 4256 KB Output is correct
7 Correct 9 ms 4420 KB Output is correct
8 Correct 10 ms 4420 KB Output is correct
9 Correct 9 ms 4424 KB Output is correct
10 Correct 6 ms 4424 KB Output is correct
11 Correct 7 ms 4424 KB Output is correct
12 Correct 9 ms 4424 KB Output is correct
13 Correct 9 ms 4456 KB Output is correct
14 Correct 59 ms 8124 KB Output is correct
15 Correct 113 ms 12332 KB Output is correct
16 Correct 181 ms 16480 KB Output is correct
17 Correct 283 ms 21452 KB Output is correct
18 Correct 261 ms 22556 KB Output is correct
19 Correct 317 ms 23744 KB Output is correct
20 Correct 312 ms 24912 KB Output is correct
21 Correct 286 ms 26016 KB Output is correct
22 Correct 145 ms 26700 KB Output is correct
23 Correct 140 ms 26700 KB Output is correct
24 Correct 120 ms 26700 KB Output is correct
25 Correct 158 ms 28704 KB Output is correct
26 Correct 129 ms 28704 KB Output is correct
27 Correct 176 ms 28704 KB Output is correct
28 Correct 148 ms 28704 KB Output is correct
29 Correct 216 ms 30580 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3576 KB Output is correct
2 Correct 8 ms 3824 KB Output is correct
3 Correct 8 ms 4096 KB Output is correct
4 Correct 7 ms 4192 KB Output is correct
5 Correct 8 ms 4224 KB Output is correct
6 Correct 8 ms 4256 KB Output is correct
7 Correct 9 ms 4420 KB Output is correct
8 Correct 10 ms 4420 KB Output is correct
9 Correct 9 ms 4424 KB Output is correct
10 Correct 6 ms 4424 KB Output is correct
11 Correct 7 ms 4424 KB Output is correct
12 Correct 9 ms 4424 KB Output is correct
13 Correct 9 ms 4456 KB Output is correct
14 Correct 59 ms 8124 KB Output is correct
15 Correct 113 ms 12332 KB Output is correct
16 Correct 181 ms 16480 KB Output is correct
17 Correct 283 ms 21452 KB Output is correct
18 Correct 261 ms 22556 KB Output is correct
19 Correct 317 ms 23744 KB Output is correct
20 Correct 312 ms 24912 KB Output is correct
21 Correct 286 ms 26016 KB Output is correct
22 Correct 145 ms 26700 KB Output is correct
23 Correct 140 ms 26700 KB Output is correct
24 Correct 120 ms 26700 KB Output is correct
25 Correct 158 ms 28704 KB Output is correct
26 Correct 129 ms 28704 KB Output is correct
27 Correct 176 ms 28704 KB Output is correct
28 Correct 148 ms 28704 KB Output is correct
29 Correct 216 ms 30580 KB Output is correct
30 Correct 229 ms 30580 KB Output is correct
31 Correct 543 ms 44848 KB Output is correct
32 Correct 900 ms 66704 KB Output is correct
33 Correct 1911 ms 102228 KB Output is correct
34 Correct 94 ms 102228 KB Output is correct
35 Correct 1980 ms 109856 KB Output is correct
36 Correct 2204 ms 115980 KB Output is correct
37 Correct 2110 ms 121716 KB Output is correct
38 Correct 2110 ms 127500 KB Output is correct
39 Correct 2095 ms 133184 KB Output is correct
40 Correct 2056 ms 138864 KB Output is correct
41 Correct 1974 ms 144512 KB Output is correct
42 Correct 2112 ms 150700 KB Output is correct
43 Correct 904 ms 155596 KB Output is correct
44 Correct 867 ms 160916 KB Output is correct
45 Correct 796 ms 165656 KB Output is correct
46 Correct 742 ms 165656 KB Output is correct
47 Correct 599 ms 165656 KB Output is correct
48 Correct 1118 ms 165656 KB Output is correct
49 Correct 1089 ms 165656 KB Output is correct