oj.uz

Submission #104017

# Submission time Handle Problem Language Result Execution time Memory
104017 2019-04-03T17:05:09 Z igba Fortune Telling 2 (JOI14_fortune_telling2) C++17
35 / 100
 3000 ms 198264 KB 
#include <bits/stdc++.h>

using namespace std;
const int MAXN = 2 * 100100, MAXK = 2 * 100100, MAXA = 1e9 + 1e4;
int n, k, a[MAXN], b[MAXN], t[MAXK];
long long ans = 0;

struct no
{
	int cnt;
	no *l, *r;
	no(int cnt = 0) : cnt(cnt), l(nullptr), r(nullptr)
	{}
};
inline int getcnt(no *n) { return (n ? n->cnt : 0); }

no* upd(no* n, int pos, int val = 1, int beg = 1, int end = MAXA)
{
	if(beg == end)
		return new no(getcnt(n) + val);
	no* ans = (n ? new no(*n) : new no());
	int mid = (beg + end) >> 1;
	if(pos <= mid)
		ans->l = upd(ans->l, pos, val, beg, mid);
	else
		ans->r = upd(ans->r, pos, val, mid + 1, end);
	ans->cnt = getcnt(ans->l) + getcnt(ans->r);
	return ans;
}

int get(no* n, int a, int b, int beg = 1, int end = MAXA)
{
	if(!n || end < a || b < beg)
		return 0;
	int mid = (beg + end) >> 1;
	if(a <= beg && end <= b)
		return getcnt(n);
	return get(n->l, a, b, beg, mid) + get(n->r, a, b, mid + 1, end);
}

no* pseg[MAXK];

int bs(int x, int y)
{
	if(x < y)
		swap(x, y);
	int beg = 0, end = k, mid, p, w;
	w = get(pseg[end], y, x - 1);
	while(beg < end)
	{
		mid = (beg + end + 1) >> 1;
		p = w - get(pseg[mid - 1], y, x - 1);
		if(p > 0)
			beg = mid;			
		else
			end = mid - 1;
	}
	return beg;
}

int main()
{
	pseg[0] = nullptr;
	scanf("%d %d", &n, &k);
	for(int i = 1; i <= n; ++i)
		scanf("%d %d", &a[i], &b[i]);
	for(int i = 1; i <= k; ++i)
		scanf("%d", &t[i]), pseg[i] = upd(pseg[i - 1], t[i]);
	for(int i = 1, swaps, j; i <= n; ++i)
	{
		/*for(j = k, swaps = 0; j >= 1; --j)
			if(min(a[i], b[i]) <= t[j] && t[j] < max(a[i], b[i]))
				break;*/
		j = bs(a[i], b[i]), swaps = 0;
		if(min(a[i], b[i]) <= t[j] && t[j] < max(a[i], b[i]))
			swaps += (a[i] < b[i]);
		swaps += get(pseg[k], max(a[i], b[i]) - 1, MAXA) - get(pseg[j], max(a[i], b[i]) - 1, MAXA);
		ans += (swaps % 2 ? b[i] : a[i]);
	}
	printf("%lld\n", ans);
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:64:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &a[i], &b[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:68:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t[i]), pseg[i] = upd(pseg[i - 1], t[i]);
   ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1280 KB Output is correct
2 Correct 5 ms 1280 KB Output is correct
3 Correct 7 ms 1280 KB Output is correct
4 Correct 7 ms 1408 KB Output is correct
5 Correct 7 ms 1280 KB Output is correct
6 Correct 7 ms 1280 KB Output is correct
7 Correct 8 ms 1388 KB Output is correct
8 Correct 8 ms 1280 KB Output is correct
9 Correct 6 ms 1408 KB Output is correct
10 Correct 8 ms 1408 KB Output is correct
11 Correct 6 ms 1408 KB Output is correct
12 Correct 8 ms 1408 KB Output is correct
13 Correct 7 ms 1276 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1280 KB Output is correct
2 Correct 5 ms 1280 KB Output is correct
3 Correct 7 ms 1280 KB Output is correct
4 Correct 7 ms 1408 KB Output is correct
5 Correct 7 ms 1280 KB Output is correct
6 Correct 7 ms 1280 KB Output is correct
7 Correct 8 ms 1388 KB Output is correct
8 Correct 8 ms 1280 KB Output is correct
9 Correct 6 ms 1408 KB Output is correct
10 Correct 8 ms 1408 KB Output is correct
11 Correct 6 ms 1408 KB Output is correct
12 Correct 8 ms 1408 KB Output is correct
13 Correct 7 ms 1276 KB Output is correct
14 Correct 77 ms 10588 KB Output is correct
15 Correct 200 ms 20728 KB Output is correct
16 Correct 337 ms 30692 KB Output is correct
17 Correct 498 ms 40604 KB Output is correct
18 Correct 440 ms 40536 KB Output is correct
19 Correct 417 ms 40512 KB Output is correct
20 Correct 481 ms 40536 KB Output is correct
21 Correct 407 ms 40440 KB Output is correct
22 Correct 352 ms 40568 KB Output is correct
23 Correct 329 ms 40440 KB Output is correct
24 Correct 316 ms 40668 KB Output is correct
25 Correct 308 ms 40556 KB Output is correct
26 Correct 384 ms 40688 KB Output is correct
27 Correct 379 ms 40568 KB Output is correct
28 Correct 316 ms 40440 KB Output is correct
29 Correct 346 ms 40568 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1280 KB Output is correct
2 Correct 5 ms 1280 KB Output is correct
3 Correct 7 ms 1280 KB Output is correct
4 Correct 7 ms 1408 KB Output is correct
5 Correct 7 ms 1280 KB Output is correct
6 Correct 7 ms 1280 KB Output is correct
7 Correct 8 ms 1388 KB Output is correct
8 Correct 8 ms 1280 KB Output is correct
9 Correct 6 ms 1408 KB Output is correct
10 Correct 8 ms 1408 KB Output is correct
11 Correct 6 ms 1408 KB Output is correct
12 Correct 8 ms 1408 KB Output is correct
13 Correct 7 ms 1276 KB Output is correct
14 Correct 77 ms 10588 KB Output is correct
15 Correct 200 ms 20728 KB Output is correct
16 Correct 337 ms 30692 KB Output is correct
17 Correct 498 ms 40604 KB Output is correct
18 Correct 440 ms 40536 KB Output is correct
19 Correct 417 ms 40512 KB Output is correct
20 Correct 481 ms 40536 KB Output is correct
21 Correct 407 ms 40440 KB Output is correct
22 Correct 352 ms 40568 KB Output is correct
23 Correct 329 ms 40440 KB Output is correct
24 Correct 316 ms 40668 KB Output is correct
25 Correct 308 ms 40556 KB Output is correct
26 Correct 384 ms 40688 KB Output is correct
27 Correct 379 ms 40568 KB Output is correct
28 Correct 316 ms 40440 KB Output is correct
29 Correct 346 ms 40568 KB Output is correct
30 Correct 657 ms 196984 KB Output is correct
31 Correct 1322 ms 197316 KB Output is correct
32 Correct 2379 ms 197788 KB Output is correct
33 Execution timed out 3034 ms 198264 KB Time limit exceeded
34 Halted 0 ms 0 KB -