oj.uz

Submission #142775

# Submission time Handle Problem Language Result Execution time Memory
142775 2019-08-10T22:56:58 Z Lawliet Fortune Telling 2 (JOI14_fortune_telling2) C++14
100 / 100
 1433 ms 134420 KB 
#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 , -g });
	}

	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 ].second;

		if(ind < 0)
		{
			ind = -ind;

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

			if(sweep[g].first == 0)
			{
				if(aux%2 == 0) ans += cards[ind].first;
				else ans += cards[ind].second;
			}
			else
			{
				if(sum%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

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
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1240 KB Output is correct
2 Correct 5 ms 1368 KB Output is correct
3 Correct 6 ms 1368 KB Output is correct
4 Correct 6 ms 1364 KB Output is correct
5 Correct 6 ms 1368 KB Output is correct
6 Correct 5 ms 1240 KB Output is correct
7 Correct 6 ms 1368 KB Output is correct
8 Correct 5 ms 1308 KB Output is correct
9 Correct 5 ms 1368 KB Output is correct
10 Correct 4 ms 504 KB Output is correct
11 Correct 6 ms 1340 KB Output is correct
12 Correct 6 ms 1368 KB Output is correct
13 Correct 6 ms 1372 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1240 KB Output is correct
2 Correct 5 ms 1368 KB Output is correct
3 Correct 6 ms 1368 KB Output is correct
4 Correct 6 ms 1364 KB Output is correct
5 Correct 6 ms 1368 KB Output is correct
6 Correct 5 ms 1240 KB Output is correct
7 Correct 6 ms 1368 KB Output is correct
8 Correct 5 ms 1308 KB Output is correct
9 Correct 5 ms 1368 KB Output is correct
10 Correct 4 ms 504 KB Output is correct
11 Correct 6 ms 1340 KB Output is correct
12 Correct 6 ms 1368 KB Output is correct
13 Correct 6 ms 1372 KB Output is correct
14 Correct 40 ms 8880 KB Output is correct
15 Correct 83 ms 16796 KB Output is correct
16 Correct 129 ms 21468 KB Output is correct
17 Correct 211 ms 32184 KB Output is correct
18 Correct 190 ms 32148 KB Output is correct
19 Correct 180 ms 32124 KB Output is correct
20 Correct 186 ms 32024 KB Output is correct
21 Correct 170 ms 32124 KB Output is correct
22 Correct 88 ms 6392 KB Output is correct
23 Correct 84 ms 6100 KB Output is correct
24 Correct 89 ms 5596 KB Output is correct
25 Correct 86 ms 7004 KB Output is correct
26 Correct 149 ms 31764 KB Output is correct
27 Correct 165 ms 31996 KB Output is correct
28 Correct 156 ms 31484 KB Output is correct
29 Correct 176 ms 32124 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1240 KB Output is correct
2 Correct 5 ms 1368 KB Output is correct
3 Correct 6 ms 1368 KB Output is correct
4 Correct 6 ms 1364 KB Output is correct
5 Correct 6 ms 1368 KB Output is correct
6 Correct 5 ms 1240 KB Output is correct
7 Correct 6 ms 1368 KB Output is correct
8 Correct 5 ms 1308 KB Output is correct
9 Correct 5 ms 1368 KB Output is correct
10 Correct 4 ms 504 KB Output is correct
11 Correct 6 ms 1340 KB Output is correct
12 Correct 6 ms 1368 KB Output is correct
13 Correct 6 ms 1372 KB Output is correct
14 Correct 40 ms 8880 KB Output is correct
15 Correct 83 ms 16796 KB Output is correct
16 Correct 129 ms 21468 KB Output is correct
17 Correct 211 ms 32184 KB Output is correct
18 Correct 190 ms 32148 KB Output is correct
19 Correct 180 ms 32124 KB Output is correct
20 Correct 186 ms 32024 KB Output is correct
21 Correct 170 ms 32124 KB Output is correct
22 Correct 88 ms 6392 KB Output is correct
23 Correct 84 ms 6100 KB Output is correct
24 Correct 89 ms 5596 KB Output is correct
25 Correct 86 ms 7004 KB Output is correct
26 Correct 149 ms 31764 KB Output is correct
27 Correct 165 ms 31996 KB Output is correct
28 Correct 156 ms 31484 KB Output is correct
29 Correct 176 ms 32124 KB Output is correct
30 Correct 757 ms 127532 KB Output is correct
31 Correct 820 ms 128948 KB Output is correct
32 Correct 1016 ms 130428 KB Output is correct
33 Correct 1134 ms 134372 KB Output is correct
34 Correct 732 ms 126840 KB Output is correct
35 Correct 1177 ms 134212 KB Output is correct
36 Correct 1140 ms 134220 KB Output is correct
37 Correct 1138 ms 134112 KB Output is correct
38 Correct 1144 ms 134240 KB Output is correct
39 Correct 1137 ms 134416 KB Output is correct
40 Correct 1060 ms 134136 KB Output is correct
41 Correct 1433 ms 134136 KB Output is correct
42 Correct 1111 ms 134420 KB Output is correct
43 Correct 828 ms 132016 KB Output is correct
44 Correct 847 ms 128132 KB Output is correct
45 Correct 800 ms 120804 KB Output is correct
46 Correct 503 ms 27820 KB Output is correct
47 Correct 515 ms 25196 KB Output is correct
48 Correct 915 ms 133504 KB Output is correct
49 Correct 889 ms 131196 KB Output is correct