답안 #52270 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
52270	2018-06-25T07:25:52 Z	ics0503	운세 보기 2 (JOI14_fortune_telling2)	C++17	35 / 100	557 ms	33628 KB

fortune_telling2

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
struct xy { long long x, y; }a[212121];
bool sort_x(xy a, xy b) { if (a.x != b.x)return a.x < b.x; return a.y < b.y; }
long long Q[212121], ALL[414141], an, tn, tree[2121212], P[212121];
vector<int>T[212121], R;
long long oper(long long a, long long b, long long tp) {if (tp == 1) { if (a < b)return b; return a; }else return a + b;}
void insert_g(long long w, long long g, long long tp) { for (long long i = w + tn; i > 0; i /= 2)tree[i] = oper(tree[i], g, tp); }
long long search_g(long long ss, long long ee,long long tp) {
	long long s = ss + tn, e = ee + tn, res = tp==1?-1:0;
	while (s <= e) {
		if (s % 2 == 1)res = oper(res, tree[s++],tp);
		if (e % 2 == 0)res = oper(res, tree[e--],tp);
		s /= 2; e /= 2;
	}
	return res;
}
int main() {
	long long n, m, i, j; scanf("%lld%lld", &n, &m);
	for (i = 0; i < n; i++)scanf("%lld%lld", &a[i].x, &a[i].y), ALL[an++] = a[i].x, ALL[an++] = a[i].y;
	for (i = 0; i < m; i++)scanf("%lld", &Q[i]), ALL[an++] = Q[i];
	sort(ALL, ALL + an);
	an = unique(ALL, ALL + an) - ALL;
	for (i = 0; i < n; i++)a[i] = { lower_bound(ALL, ALL + an, a[i].x) - ALL,lower_bound(ALL, ALL + an, a[i].y) - ALL };
	for (i = 0; i < m; i++)Q[i] = lower_bound(ALL, ALL + an, Q[i]) - ALL;
	for (tn = 1; tn < an; tn *= 2);
	for (i = 0; i < tn * 2; i++)tree[i] = -1;
	for (i = 0; i < m; i++)insert_g(Q[i], i,1);
	for (i = 0; i < n; i++) {
		long long s = min(a[i].x, a[i].y), e = max(a[i].x, a[i].y);
		P[i] = search_g(s, e - 1,1);
		if (P[i] == -1)R.push_back(i);
		else T[P[i]].push_back(i);
	}
	for (i = 0; i < tn * 2; i++)tree[i] = 0;
	long long ans = 0;
	for (i = m - 1; i >= 0; i--) {
		for (j = 0; j < T[i].size(); j++) {
			long long now = T[i][j];
			if (search_g(max(a[now].x, a[now].y), an - 1, 0) % 2 == 0)ans += ALL[max(a[now].x, a[now].y)];
			else ans += ALL[min(a[now].x, a[now].y)];
		}
		insert_g(Q[i], 1, 0);
	}
	for (i = 0; i < R.size(); i++) {
		long long now = R[i];
		if (search_g(a[now].x, an - 1, 0) % 2 == 0)ans += ALL[a[now].x];
		else ans += ALL[a[now].y];
	}
	printf("%lld", ans);
	return 0;
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:40:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (j = 0; j < T[i].size(); j++) {
               ~~^~~~~~~~~~~~~
fortune_telling2.cpp:47:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (i = 0; i < R.size(); i++) {
              ~~^~~~~~~~~~
fortune_telling2.cpp:21:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  long long n, m, i, j; scanf("%lld%lld", &n, &m);
                        ~~~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:22:80: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 0; i < n; i++)scanf("%lld%lld", &a[i].x, &a[i].y), ALL[an++] = a[i].x, ALL[an++] = a[i].y;
                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:23:45: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 0; i < m; i++)scanf("%lld", &Q[i]), ALL[an++] = Q[i];
                         ~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5368 KB	Output is correct
2	Correct	6 ms	5368 KB	Output is correct
3	Correct	7 ms	5512 KB	Output is correct
4	Correct	7 ms	5528 KB	Output is correct
5	Correct	7 ms	5588 KB	Output is correct
6	Correct	7 ms	5588 KB	Output is correct
7	Correct	7 ms	5588 KB	Output is correct
8	Correct	8 ms	5664 KB	Output is correct
9	Correct	7 ms	5664 KB	Output is correct
10	Correct	7 ms	5664 KB	Output is correct
11	Correct	7 ms	5664 KB	Output is correct
12	Correct	9 ms	5664 KB	Output is correct
13	Correct	7 ms	5756 KB	Output is correct

Subtask #2
31.0 / 31.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5368 KB	Output is correct
2	Correct	6 ms	5368 KB	Output is correct
3	Correct	7 ms	5512 KB	Output is correct
4	Correct	7 ms	5528 KB	Output is correct
5	Correct	7 ms	5588 KB	Output is correct
6	Correct	7 ms	5588 KB	Output is correct
7	Correct	7 ms	5588 KB	Output is correct
8	Correct	8 ms	5664 KB	Output is correct
9	Correct	7 ms	5664 KB	Output is correct
10	Correct	7 ms	5664 KB	Output is correct
11	Correct	7 ms	5664 KB	Output is correct
12	Correct	9 ms	5664 KB	Output is correct
13	Correct	7 ms	5756 KB	Output is correct
14	Correct	21 ms	6652 KB	Output is correct
15	Correct	43 ms	7836 KB	Output is correct
16	Correct	70 ms	9420 KB	Output is correct
17	Correct	88 ms	10060 KB	Output is correct
18	Correct	89 ms	10068 KB	Output is correct
19	Correct	78 ms	10108 KB	Output is correct
20	Correct	89 ms	10128 KB	Output is correct
21	Correct	88 ms	10236 KB	Output is correct
22	Correct	62 ms	10236 KB	Output is correct
23	Correct	59 ms	10236 KB	Output is correct
24	Correct	59 ms	10236 KB	Output is correct
25	Correct	62 ms	10236 KB	Output is correct
26	Correct	81 ms	10236 KB	Output is correct
27	Correct	81 ms	10236 KB	Output is correct
28	Correct	67 ms	10236 KB	Output is correct
29	Correct	79 ms	10236 KB	Output is correct

Subtask #3
0 / 65.0

#	결과	실행 시간	메모리	Grader output
1	Correct	6 ms	5368 KB	Output is correct
2	Correct	6 ms	5368 KB	Output is correct
3	Correct	7 ms	5512 KB	Output is correct
4	Correct	7 ms	5528 KB	Output is correct
5	Correct	7 ms	5588 KB	Output is correct
6	Correct	7 ms	5588 KB	Output is correct
7	Correct	7 ms	5588 KB	Output is correct
8	Correct	8 ms	5664 KB	Output is correct
9	Correct	7 ms	5664 KB	Output is correct
10	Correct	7 ms	5664 KB	Output is correct
11	Correct	7 ms	5664 KB	Output is correct
12	Correct	9 ms	5664 KB	Output is correct
13	Correct	7 ms	5756 KB	Output is correct
14	Correct	21 ms	6652 KB	Output is correct
15	Correct	43 ms	7836 KB	Output is correct
16	Correct	70 ms	9420 KB	Output is correct
17	Correct	88 ms	10060 KB	Output is correct
18	Correct	89 ms	10068 KB	Output is correct
19	Correct	78 ms	10108 KB	Output is correct
20	Correct	89 ms	10128 KB	Output is correct
21	Correct	88 ms	10236 KB	Output is correct
22	Correct	62 ms	10236 KB	Output is correct
23	Correct	59 ms	10236 KB	Output is correct
24	Correct	59 ms	10236 KB	Output is correct
25	Correct	62 ms	10236 KB	Output is correct
26	Correct	81 ms	10236 KB	Output is correct
27	Correct	81 ms	10236 KB	Output is correct
28	Correct	67 ms	10236 KB	Output is correct
29	Correct	79 ms	10236 KB	Output is correct
30	Correct	161 ms	13308 KB	Output is correct
31	Correct	220 ms	19152 KB	Output is correct
32	Correct	344 ms	21384 KB	Output is correct
33	Incorrect	557 ms	33628 KB	Output isn't correct
34	Halted	0 ms	0 KB	-

답안 #52270

Compilation message

Subtask #1 4.0 / 4.0

Subtask #2 31.0 / 31.0

Subtask #3 0 / 65.0

Subtask #1
4.0 / 4.0

Subtask #2
31.0 / 31.0

Subtask #3
0 / 65.0