oj.uz

Submission #104023

# Submission time Handle Problem Language Result Execution time Memory
104023 2019-04-03T18:03:54 Z igba Fortune Telling 2 (JOI14_fortune_telling2) C++17
35 / 100
 723 ms 263168 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, 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 8 ms 2304 KB Output is correct
3 Correct 7 ms 2304 KB Output is correct
4 Correct 8 ms 2304 KB Output is correct
5 Correct 7 ms 2304 KB Output is correct
6 Correct 7 ms 2304 KB Output is correct
7 Correct 8 ms 2304 KB Output is correct
8 Correct 7 ms 2304 KB Output is correct
9 Correct 7 ms 2304 KB Output is correct
10 Correct 6 ms 2304 KB Output is correct
11 Correct 7 ms 2304 KB Output is correct
12 Correct 7 ms 2432 KB Output is correct
13 Correct 7 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 8 ms 2304 KB Output is correct
3 Correct 7 ms 2304 KB Output is correct
4 Correct 8 ms 2304 KB Output is correct
5 Correct 7 ms 2304 KB Output is correct
6 Correct 7 ms 2304 KB Output is correct
7 Correct 8 ms 2304 KB Output is correct
8 Correct 7 ms 2304 KB Output is correct
9 Correct 7 ms 2304 KB Output is correct
10 Correct 6 ms 2304 KB Output is correct
11 Correct 7 ms 2304 KB Output is correct
12 Correct 7 ms 2432 KB Output is correct
13 Correct 7 ms 2304 KB Output is correct
14 Correct 59 ms 19916 KB Output is correct
15 Correct 119 ms 39544 KB Output is correct
16 Correct 189 ms 59004 KB Output is correct
17 Correct 301 ms 78684 KB Output is correct
18 Correct 278 ms 78592 KB Output is correct
19 Correct 289 ms 78556 KB Output is correct
20 Correct 268 ms 78568 KB Output is correct
21 Correct 273 ms 78656 KB Output is correct
22 Correct 241 ms 78840 KB Output is correct
23 Correct 215 ms 78712 KB Output is correct
24 Correct 244 ms 78608 KB Output is correct
25 Correct 264 ms 78756 KB Output is correct
26 Correct 258 ms 78584 KB Output is correct
27 Correct 280 ms 78584 KB Output is correct
28 Correct 263 ms 78676 KB Output is correct
29 Correct 273 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 8 ms 2304 KB Output is correct
3 Correct 7 ms 2304 KB Output is correct
4 Correct 8 ms 2304 KB Output is correct
5 Correct 7 ms 2304 KB Output is correct
6 Correct 7 ms 2304 KB Output is correct
7 Correct 8 ms 2304 KB Output is correct
8 Correct 7 ms 2304 KB Output is correct
9 Correct 7 ms 2304 KB Output is correct
10 Correct 6 ms 2304 KB Output is correct
11 Correct 7 ms 2304 KB Output is correct
12 Correct 7 ms 2432 KB Output is correct
13 Correct 7 ms 2304 KB Output is correct
14 Correct 59 ms 19916 KB Output is correct
15 Correct 119 ms 39544 KB Output is correct
16 Correct 189 ms 59004 KB Output is correct
17 Correct 301 ms 78684 KB Output is correct
18 Correct 278 ms 78592 KB Output is correct
19 Correct 289 ms 78556 KB Output is correct
20 Correct 268 ms 78568 KB Output is correct
21 Correct 273 ms 78656 KB Output is correct
22 Correct 241 ms 78840 KB Output is correct
23 Correct 215 ms 78712 KB Output is correct
24 Correct 244 ms 78608 KB Output is correct
25 Correct 264 ms 78756 KB Output is correct
26 Correct 258 ms 78584 KB Output is correct
27 Correct 280 ms 78584 KB Output is correct
28 Correct 263 ms 78676 KB Output is correct
29 Correct 273 ms 78584 KB Output is correct
30 Runtime error 723 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Halted 0 ms 0 KB -