oj.uz

Submission #104025

# Submission time Handle Problem Language Result Execution time Memory
104025 2019-04-03T18:14:03 Z igba Fortune Telling 2 (JOI14_fortune_telling2) C++17
35 / 100
 847 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];
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, t; i <= k; ++i)
		scanf("%d", &t), pseg[i] = upd(pseg[i - 1], t), seg = upd(seg, t, 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(j)
			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:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t), pseg[i] = upd(pseg[i - 1], t), seg = upd(seg, t, i);
   ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2304 KB Output is correct
2 Correct 8 ms 2304 KB Output is correct
3 Correct 9 ms 2304 KB Output is correct
4 Correct 7 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 7 ms 2304 KB Output is correct
8 Correct 8 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 9 ms 2304 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 7 ms 2304 KB Output is correct
2 Correct 8 ms 2304 KB Output is correct
3 Correct 9 ms 2304 KB Output is correct
4 Correct 7 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 7 ms 2304 KB Output is correct
8 Correct 8 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 9 ms 2304 KB Output is correct
13 Correct 7 ms 2304 KB Output is correct
14 Correct 64 ms 19840 KB Output is correct
15 Correct 166 ms 39420 KB Output is correct
16 Correct 218 ms 58996 KB Output is correct
17 Correct 289 ms 78452 KB Output is correct
18 Correct 303 ms 78364 KB Output is correct
19 Correct 270 ms 78376 KB Output is correct
20 Correct 306 ms 78428 KB Output is correct
21 Correct 249 ms 78456 KB Output is correct
22 Correct 215 ms 78456 KB Output is correct
23 Correct 234 ms 78576 KB Output is correct
24 Correct 211 ms 78456 KB Output is correct
25 Correct 233 ms 78584 KB Output is correct
26 Correct 245 ms 78456 KB Output is correct
27 Correct 291 ms 78460 KB Output is correct
28 Correct 261 ms 78456 KB Output is correct
29 Correct 252 ms 78456 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2304 KB Output is correct
2 Correct 8 ms 2304 KB Output is correct
3 Correct 9 ms 2304 KB Output is correct
4 Correct 7 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 7 ms 2304 KB Output is correct
8 Correct 8 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 9 ms 2304 KB Output is correct
13 Correct 7 ms 2304 KB Output is correct
14 Correct 64 ms 19840 KB Output is correct
15 Correct 166 ms 39420 KB Output is correct
16 Correct 218 ms 58996 KB Output is correct
17 Correct 289 ms 78452 KB Output is correct
18 Correct 303 ms 78364 KB Output is correct
19 Correct 270 ms 78376 KB Output is correct
20 Correct 306 ms 78428 KB Output is correct
21 Correct 249 ms 78456 KB Output is correct
22 Correct 215 ms 78456 KB Output is correct
23 Correct 234 ms 78576 KB Output is correct
24 Correct 211 ms 78456 KB Output is correct
25 Correct 233 ms 78584 KB Output is correct
26 Correct 245 ms 78456 KB Output is correct
27 Correct 291 ms 78460 KB Output is correct
28 Correct 261 ms 78456 KB Output is correct
29 Correct 252 ms 78456 KB Output is correct
30 Runtime error 847 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Halted 0 ms 0 KB -