Submission #126634

#	Time	Username	Problem	Language	Result	Execution time	Memory
126634		fizzydavid	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	4 / 100	3036 ms	1136 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;
int n, m;
vector<int> pts;
int getid(int x) {return lower_bound(pts.begin(), pts.end(), x+1)-pts.begin();}
pair<int,int>  p[maxn];
int arr[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);
	for (int i=1; i<=m; i++)
	{
		scanf("%d", &arr[i]);
		arr[i] = getid(arr[i]);
	}
//	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;
	ll ans = 0;
	for (int i=1; i<=n; i++)
	{
		int x = p[i].FF, y = p[i].SS;
		bool flip = false;
		if (x>y) flip = true, swap(x, y);
		int lst = -1;
		for (int j=1; j<=m; j++)
		{
			if (arr[j]>=x&&arr[j]<y)
			{
				lst = j;
			}
		}
		if (lst==-1)
		{
			for (int j=1; j<=m; j++) flip ^= arr[j]>=y;
		}
		else
		{
			flip = true;
			for (int j=lst+1; j<=m; j++) flip ^= arr[j]>=y;
		}
		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 'int main()':
fortune_telling2.cpp:17: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:20: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:29: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: 0 / 31
• Subtask 3: 0 / 65