oj.uz

Submission #104024

# Submission time Handle Problem Language Result Execution time Memory
104024 2019-04-03T18:06:35 Z igba Fortune Telling 2 (JOI14_fortune_telling2) C++17
35 / 100
 789 ms 263168 KB 
#include <bits/stdc++.h>
 
using namespace std;
const int MAXN = 2 * 100100, MAXK = 2 * 100100, MAXA = 1e9 + 1e2;
int n, k, a[MAXN], b[MAXN], t[MAXK];
long long ans = 0;
 
struct no
{
	int cnt, mx;
	no *l, *r;
	no(int cnt = 0, int mx = 0) : cnt(cnt), mx(mx), l(nullptr), r(nullptr)
	{}
};
inline int getcnt(no *n) { return (n ? n->cnt : 0); }
inline int getmx(no *n) { return (n ? n->mx : 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, max(getmx(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);
	ans->mx = max(getmx(ans->l), getmx(ans->r));
	return ans;
}
 
int getcnt(no* n, int pos, int beg = 1, int end = MAXA)
{
	if(!n)
		return 0;
	int mid = (beg + end) >> 1;
	if(pos <= mid)
		return getcnt(n->l, pos, beg, mid) + getcnt(n->r);
	return getcnt(n->r, pos, mid + 1, end);
}

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

no *pseg[MAXK], *seg;
 
int main()
{
	pseg[0] = seg = 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]), seg = upd(seg, t[i], i);
	for(int i = 1, swaps, j; i <= n; ++i)
	{
		j = getmx(seg, min(a[i], b[i]), max(a[i], b[i]) - 1), swaps = 0;
		if(min(a[i], b[i]) <= t[j] && t[j] < max(a[i], b[i]))
			swaps += (a[i] < b[i]);
		swaps += getcnt(pseg[k], max(a[i], b[i]) - 1) - getcnt(pseg[j], max(a[i], b[i]) - 1);
		ans += (swaps % 2 ? b[i] : a[i]);
	}
	printf("%lld\n", ans);
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:58: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:60: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:62:55: 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]), seg = upd(seg, t[i], i);
   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2304 KB Output is correct
2 Correct 6 ms 2304 KB Output is correct
3 Correct 6 ms 2304 KB Output is correct
4 Correct 6 ms 2304 KB Output is correct
5 Correct 6 ms 2304 KB Output is correct
6 Correct 7 ms 2304 KB Output is correct
7 Correct 7 ms 2304 KB Output is correct
8 Correct 6 ms 2304 KB Output is correct
9 Correct 9 ms 2304 KB Output is correct
10 Correct 7 ms 2304 KB Output is correct
11 Correct 7 ms 2304 KB Output is correct
12 Correct 8 ms 2304 KB Output is correct
13 Correct 9 ms 2304 KB Output is correct
14 Correct 75 ms 19832 KB Output is correct
15 Correct 137 ms 39476 KB Output is correct
16 Correct 216 ms 59000 KB Output is correct
17 Correct 308 ms 78616 KB Output is correct
18 Correct 292 ms 78584 KB Output is correct
19 Correct 306 ms 78712 KB Output is correct
20 Correct 327 ms 78684 KB Output is correct
21 Correct 264 ms 78584 KB Output is correct
22 Correct 222 ms 78584 KB Output is correct
23 Correct 256 ms 78584 KB Output is correct
24 Correct 216 ms 78712 KB Output is correct
25 Correct 217 ms 78712 KB Output is correct
26 Correct 232 ms 78676 KB Output is correct
27 Correct 273 ms 78740 KB Output is correct
28 Correct 256 ms 78732 KB Output is correct
29 Correct 287 ms 78584 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2304 KB Output is correct
2 Correct 6 ms 2304 KB Output is correct
3 Correct 6 ms 2304 KB Output is correct
4 Correct 6 ms 2304 KB Output is correct
5 Correct 6 ms 2304 KB Output is correct
6 Correct 7 ms 2304 KB Output is correct
7 Correct 7 ms 2304 KB Output is correct
8 Correct 6 ms 2304 KB Output is correct
9 Correct 9 ms 2304 KB Output is correct
10 Correct 7 ms 2304 KB Output is correct
11 Correct 7 ms 2304 KB Output is correct
12 Correct 8 ms 2304 KB Output is correct
13 Correct 9 ms 2304 KB Output is correct
14 Correct 75 ms 19832 KB Output is correct
15 Correct 137 ms 39476 KB Output is correct
16 Correct 216 ms 59000 KB Output is correct
17 Correct 308 ms 78616 KB Output is correct
18 Correct 292 ms 78584 KB Output is correct
19 Correct 306 ms 78712 KB Output is correct
20 Correct 327 ms 78684 KB Output is correct
21 Correct 264 ms 78584 KB Output is correct
22 Correct 222 ms 78584 KB Output is correct
23 Correct 256 ms 78584 KB Output is correct
24 Correct 216 ms 78712 KB Output is correct
25 Correct 217 ms 78712 KB Output is correct
26 Correct 232 ms 78676 KB Output is correct
27 Correct 273 ms 78740 KB Output is correct
28 Correct 256 ms 78732 KB Output is correct
29 Correct 287 ms 78584 KB Output is correct
30 Runtime error 789 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Halted 0 ms 0 KB -