Submission #126643

#	Time	Username	Problem	Language	Result	Execution time	Memory
126643		fizzydavid	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	100 / 100	763 ms	54944 KiB

fortune_telling2

//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 (stderr)

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 / 4
• Subtask 2: 31 / 31
• Subtask 3: 65 / 65