oj.uz

Submission #126643

# Submission time Handle Problem Language Result Execution time Memory
126643 2019-07-08T08:22:41 Z fizzydavid Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 763 ms 54944 KB 
//by yjz
#include<bits/stdc++.h>
#define FF first
#define SS second
#define MP make_pair
#define PB push_back
typedef long long ll;
using namespace std;
const int maxn = 400111;
const int inf = 1e9;
int n, m, arr[maxn];
#define ls p<<1
#define rs p<<1|1
int mn[maxn<<4], cnt[maxn<<4];
void update(int p)
{
	mn[p] = min(mn[ls], mn[rs]);
	cnt[p] = cnt[ls]+cnt[rs];
}
void modify(int x, int v, int l, int r, int p)
{
	if (l==r)
	{
		mn[p] = v;
		cnt[p] = v<inf;
		return;
	}
	int m = l+r>>1;
	if (x<=m) modify(x, v, l, m, ls);
	else modify(x, v, m+1, r, rs);
	update(p);
}
int query_last(int v, int l, int r, int p)
{
	if (mn[p]>=v) return l-1;
	if (l==r) return l;
	int m = l+r>>1;
	int tmp = query_last(v, m+1, r, rs);
	if (tmp==m) return query_last(v, l, m, ls);
	else return tmp;
}
int query_cnt(int x, int y, int l, int r, int p)
{
	if (y<l||r<x) return 0;
	if (x<=l&&r<=y) return cnt[p];
	int m = l+r>>1;
	return query_cnt(x, y, l, m, ls)+query_cnt(x, y, m+1, r, rs);
}
vector<int> pts;
int getid(int x) {return lower_bound(pts.begin(), pts.end(), x+1)-pts.begin();}
pair<int,int>  p[maxn];
vector<int> v_arr[maxn], v_p[maxn], v_qr[maxn];
int lst[maxn];
bool f[maxn];
int main()
{
	scanf("%d%d", &n, &m);
	for (int i=1; i<=n; i++)
	{
		scanf("%d%d", &p[i].FF, &p[i].SS);
		pts.PB(p[i].FF);
		pts.PB(p[i].SS);
	}
	sort(pts.begin(), pts.end());
	pts.erase(unique(pts.begin(), pts.end()), pts.end());
	for (int i=1; i<=n; i++)
	{
		p[i].FF = getid(p[i].FF), p[i].SS = getid(p[i].SS);
		if (p[i].FF>p[i].SS) swap(p[i].FF, p[i].SS), f[i] = true;
		v_p[p[i].FF].PB(i);
		v_qr[p[i].SS].PB(i);
	}
	for (int i=1; i<=m; i++)
	{
		scanf("%d", &arr[i]);
		arr[i] = getid(arr[i]);
		v_arr[arr[i]].PB(i);
		modify(i, arr[i], 1, m, 1);
	}
//	for (int i=1; i<=n; i++) cerr<<p[i].FF<<","<<p[i].SS<<endl;
//	for (int i=1; i<=m; i++) cerr<<arr[i]<<" "; cerr<<endl;
	for (int i=0; i<=pts.size(); i++)
	{
		for (auto t : v_p[i])
		{
			lst[t] = query_last(p[t].SS, 1, m, 1);
			if (lst[t]!=0) f[t] = true;
		}
		for (auto t : v_qr[i])
		{
			f[t] ^= query_cnt(lst[t]+1, m, 1, m, 1)&1;
		}
		for (auto t : v_arr[i])
		{
			modify(t, inf, 1, m, 1);
		}
	}
	ll ans = 0;
	for (int i=1; i<=n; i++)
	{
		int x = p[i].FF, y = p[i].SS;
		bool flip = f[i];
		if (flip) ans += pts[y-1]; else ans += pts[x-1];
	}
	cout<<ans<<endl;
	return 0;
}
/*
5 3
4 6
9 1
8 8
4 2
3 7
8
2
9
 */

Compilation message

fortune_telling2.cpp: In function 'void modify(int, int, int, int, int)':
fortune_telling2.cpp:28:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = l+r>>1;
          ~^~
fortune_telling2.cpp: In function 'int query_last(int, int, int, int)':
fortune_telling2.cpp:37:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = l+r>>1;
          ~^~
fortune_telling2.cpp: In function 'int query_cnt(int, int, int, int, int)':
fortune_telling2.cpp:46:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = l+r>>1;
          ~^~
fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:82:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<=pts.size(); i++)
                ~^~~~~~~~~~~~
fortune_telling2.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
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", &p[i].FF, &p[i].SS);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:75:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &arr[i]);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 28536 KB Output is correct
2 Correct 29 ms 28664 KB Output is correct
3 Correct 34 ms 28664 KB Output is correct
4 Correct 30 ms 28664 KB Output is correct
5 Correct 34 ms 28808 KB Output is correct
6 Correct 30 ms 28664 KB Output is correct
7 Correct 30 ms 28664 KB Output is correct
8 Correct 30 ms 28664 KB Output is correct
9 Correct 35 ms 28664 KB Output is correct
10 Correct 33 ms 28792 KB Output is correct
11 Correct 33 ms 28664 KB Output is correct
12 Correct 29 ms 28668 KB Output is correct
13 Correct 30 ms 28664 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 28536 KB Output is correct
2 Correct 29 ms 28664 KB Output is correct
3 Correct 34 ms 28664 KB Output is correct
4 Correct 30 ms 28664 KB Output is correct
5 Correct 34 ms 28808 KB Output is correct
6 Correct 30 ms 28664 KB Output is correct
7 Correct 30 ms 28664 KB Output is correct
8 Correct 30 ms 28664 KB Output is correct
9 Correct 35 ms 28664 KB Output is correct
10 Correct 33 ms 28792 KB Output is correct
11 Correct 33 ms 28664 KB Output is correct
12 Correct 29 ms 28668 KB Output is correct
13 Correct 30 ms 28664 KB Output is correct
14 Correct 58 ms 30200 KB Output is correct
15 Correct 91 ms 31604 KB Output is correct
16 Correct 100 ms 32600 KB Output is correct
17 Correct 133 ms 34160 KB Output is correct
18 Correct 131 ms 34288 KB Output is correct
19 Correct 130 ms 34096 KB Output is correct
20 Correct 134 ms 34160 KB Output is correct
21 Correct 121 ms 33776 KB Output is correct
22 Correct 94 ms 34288 KB Output is correct
23 Correct 107 ms 34416 KB Output is correct
24 Correct 93 ms 34160 KB Output is correct
25 Correct 88 ms 34164 KB Output is correct
26 Correct 94 ms 32492 KB Output is correct
27 Correct 104 ms 32752 KB Output is correct
28 Correct 100 ms 32880 KB Output is correct
29 Correct 120 ms 33392 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 28536 KB Output is correct
2 Correct 29 ms 28664 KB Output is correct
3 Correct 34 ms 28664 KB Output is correct
4 Correct 30 ms 28664 KB Output is correct
5 Correct 34 ms 28808 KB Output is correct
6 Correct 30 ms 28664 KB Output is correct
7 Correct 30 ms 28664 KB Output is correct
8 Correct 30 ms 28664 KB Output is correct
9 Correct 35 ms 28664 KB Output is correct
10 Correct 33 ms 28792 KB Output is correct
11 Correct 33 ms 28664 KB Output is correct
12 Correct 29 ms 28668 KB Output is correct
13 Correct 30 ms 28664 KB Output is correct
14 Correct 58 ms 30200 KB Output is correct
15 Correct 91 ms 31604 KB Output is correct
16 Correct 100 ms 32600 KB Output is correct
17 Correct 133 ms 34160 KB Output is correct
18 Correct 131 ms 34288 KB Output is correct
19 Correct 130 ms 34096 KB Output is correct
20 Correct 134 ms 34160 KB Output is correct
21 Correct 121 ms 33776 KB Output is correct
22 Correct 94 ms 34288 KB Output is correct
23 Correct 107 ms 34416 KB Output is correct
24 Correct 93 ms 34160 KB Output is correct
25 Correct 88 ms 34164 KB Output is correct
26 Correct 94 ms 32492 KB Output is correct
27 Correct 104 ms 32752 KB Output is correct
28 Correct 100 ms 32880 KB Output is correct
29 Correct 120 ms 33392 KB Output is correct
30 Correct 211 ms 36124 KB Output is correct
31 Correct 347 ms 40220 KB Output is correct
32 Correct 461 ms 45400 KB Output is correct
33 Correct 713 ms 54564 KB Output is correct
34 Correct 131 ms 34668 KB Output is correct
35 Correct 744 ms 54556 KB Output is correct
36 Correct 712 ms 54704 KB Output is correct
37 Correct 724 ms 54524 KB Output is correct
38 Correct 732 ms 54680 KB Output is correct
39 Correct 716 ms 54544 KB Output is correct
40 Correct 591 ms 52456 KB Output is correct
41 Correct 763 ms 54592 KB Output is correct
42 Correct 730 ms 54532 KB Output is correct
43 Correct 279 ms 52124 KB Output is correct
44 Correct 276 ms 52196 KB Output is correct
45 Correct 283 ms 52228 KB Output is correct
46 Correct 441 ms 54944 KB Output is correct
47 Correct 423 ms 54372 KB Output is correct
48 Correct 474 ms 47732 KB Output is correct
49 Correct 454 ms 47832 KB Output is correct