답안 #73763 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
73763	2018-08-28T23:34:23 Z	shoemakerjo	운세 보기 2 (JOI14_fortune_telling2)	C++14	100 / 100	2204 ms	165656 KB

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

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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #73763

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 31.0 / 31.0

Subtask #3 65.0 / 65.0

Subtask #1
4.0 / 4.0

Subtask #2
31.0 / 31.0

Subtask #3
65.0 / 65.0