Submission #142774

#	Time	Username	Problem	Language	Result	Execution time	Memory
142774		Lawliet	Fortune Telling 2 (JOI14_fortune_telling2)	C++14	0 / 100	5 ms	1496 KiB

fortune_telling2

#include <bits/stdc++.h>

#define MAX 200010
#define MAXC 1000000010

using namespace std;
typedef pair<int,int> pii;
typedef long long int lli;

class SparseSegmentTree
{
	public:

		void createNode()
		{
			e.push_back( 0 );
			d.push_back( 0 );

			mx.push_back( 0 );
			sum.push_back( 0 );
		}

		int getLeft(int node)
		{
			if(e[node] == 0)
			{
				e[node] = ++curNode;
				createNode();
			}

			return e[node];
		}

		int getRight(int node)
		{
			if(d[node] == 0)
			{
				d[node] = ++curNode;
				createNode();
			}

			return d[node];
		}

		void update(int node, int l, int r, int i, int v)
		{
			if(l == r)
			{
				mx[ node ] = v;
				sum[ node ]++;
				return;
			}

			int m = (l + r)/2;

			if(i <= m) update(getLeft(node) , l , m , i , v);
			else update(getRight(node) , m + 1 , r , i , v);

			sum[ node ] = sum[ e[node] ] + sum[ d[node] ];
			mx[ node ] = max(mx[ e[node] ] , mx[ d[node] ]);
		}

		int queryMax(int node, int l, int r, int i, int j)
		{
			if(i > j) return 0;
			if(node == 0 || j < l || r < i) return 0;
			if(i <= l && r <= j) return mx[ node ];

			int m = (l + r)/2;

			int maxLeft = queryMax(e[node] , l , m , i , j);
			int maxRight = queryMax(d[node] , m + 1 , r , i , j);

			return max(maxLeft , maxRight);
		}

		int querySum(int node, int l, int r, int i, int j)
		{
			if(node == 0 || j < l || r < i) return 0;
			if(i <= l && r <= j) return sum[ node ];

			int m = (l + r)/2;

			int sumLeft = querySum(e[node] , l , m , i , j);
			int sumRight = querySum(d[node] , m + 1 , r , i , j);

			return sumLeft + sumRight;
		}

		SparseSegmentTree() : curNode( 1 ) { createNode(); createNode(); }

	private:

		int curNode;

		vector<int> e, d;
		vector<int> mx, sum;
};

int n, k;
int n1, n2;

int isSwaped[MAX];
int turnQuery[MAX];

lli ans;

pii cards[MAX];

vector<pii> sweep;

SparseSegmentTree SEG;
SparseSegmentTree sweepSEG;

int main()
{
	scanf("%d %d",&n,&k);

	for(int g = 1 ; g <= n ; g++)
	{
		scanf("%d %d",&n1,&n2);

		if(n1 < n2)
		{
			isSwaped[ g ] = 1;
			swap(n1 , n2);
		}

		cards[ g ] = {n1 , n2};
	}

	for(int g = 1 ; g <= k ; g++)
	{
		scanf("%d",&turnQuery[g]);

		SEG.update(1 , 0 , MAXC , turnQuery[g] , g);

		sweep.push_back({ -g , -1 });
	}

	for(int g = 1 ; g <= n ; g++)
	{
		int l = cards[ g ].second;
		int r = cards[ g ].first;

		int lastQuery = SEG.queryMax(1 , 0 , MAXC , l , r - 1);

		sweep.push_back({ -lastQuery , g });
	}

	sort(sweep.begin() , sweep.end());

	for(int g = 0 ; g < sweep.size() ; g++)
	{
		int ind = -sweep[ g ].first;

		if(sweep[ g ].second != -1)
		{
			ind = sweep[ g ].second;

			lli sum = sweepSEG.querySum(1 , 0 , MAXC , cards[ ind ].first , MAXC);
			lli aux = sum + isSwaped[ind];

			if(aux%2 == 0) ans += cards[ind].first;
			else ans += cards[ind].second;
		} 
		else sweepSEG.update(1 , 0 , MAXC , turnQuery[ ind ] , 0);
	}

	printf("%lld\n",ans);
}

Compilation message (stderr)

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:153:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int g = 0 ; g < sweep.size() ; g++)
                  ~~^~~~~~~~~~~~~~
fortune_telling2.cpp:117: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:121:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&n1,&n2);
   ~~~~~^~~~~~~~~~~~~~~~~
fortune_telling2.cpp:134:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&turnQuery[g]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 0 / 31
• Subtask 3: 0 / 65