oj.uz

Submission #295400

# Submission time Handle Problem Language Result Execution time Memory
295400 2020-09-09T16:22:45 Z patrikpavic2 Fortune Telling 2 (JOI14_fortune_telling2) C++17
100 / 100
 1079 ms 95116 KB 
#include <cstdio>
#include <vector>
#include <algorithm>

#define PB push_back

using namespace std;

typedef long long ll;
typedef vector < int > vi;

const int N = 6e5 + 500;
const int OFF = (1 << 20);

int n, q, A[N], B[N], Q[N];
int loga[N], l_siz, izb[N];
vi saz, T[2 * OFF];

void add(int x){
	l_siz++;
	for(x += 5 ; x < N ; x += x & -x)
		loga[x]++;
}

int query(int x){
	x--;
	int ret = 0;
	for(x += 5 ; x ; x -= x & -x)
		ret += loga[x];
	return l_siz - ret;
}

ll sol = 0;

void izbaci(int i){
	if(izb[i]) return;
	izb[i] = 1;
	if(query(B[i]) & 1)
		sol += saz[min(A[i], B[i])];
	else
		sol += saz[max(A[i], B[i])];
}

void dodaj(int i, int a, int b, int lo, int hi, int x){
	if(lo <= a && b <= hi){
		T[i].PB(x); return;
	}	
	if(a > hi || b < lo) return;
	dodaj(2 * i, a, (a + b) / 2, lo, hi, x);
	dodaj(2 * i + 1, (a + b) / 2 + 1, b, lo, hi, x);
}

void unisti(int x){
	x += OFF;
	for(; x ; x /= 2){
		for(int y : T[x])
			izbaci(y);
		T[x].clear();
	}
}

int main(){
	scanf("%d%d", &n, &q);
	for(int i = 0;i < n;i++){
		scanf("%d%d", A + i, B + i);
		saz.PB(A[i]), saz.PB(B[i]);
	}
	for(int i = 0;i < q;i++){
		scanf("%d", Q + i);
		saz.PB(Q[i]);
	}
	sort(saz.begin(), saz.end());
	saz.erase(unique(saz.begin(), saz.end()), saz.end());
	for(int i = 0;i < n;i++){
		A[i] = lower_bound(saz.begin(), saz.end(), A[i]) - saz.begin();
		B[i] = lower_bound(saz.begin(), saz.end(), B[i]) - saz.begin();
	}
	for(int i = 0;i < q;i++){
		Q[i] = lower_bound(saz.begin(), saz.end(), Q[i]) - saz.begin();
	}
	for(int i = 0;i < n;i++){
		if(A[i] == B[i]){
			izb[i] = 1;
			sol += saz[A[i]]; continue;
		}
		dodaj(1, 0, OFF - 1, min(A[i], B[i]), max(A[i], B[i]) - 1, i);
	}
	for(int i = q - 1;i >= 0;i--){
		unisti(Q[i]); add(Q[i]);
	}
	for(int i = 0;i < n;i++){
		if(!izb[i]){
			if(query(B[i]) & 1)
				sol += saz[B[i]];
			else
				sol += saz[A[i]];
		}
	}
	printf("%lld\n", sol);
}

Compilation message

fortune_telling2.cpp: In function 'int main()':
fortune_telling2.cpp:63:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~
fortune_telling2.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   65 |   scanf("%d%d", A + i, B + i);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~
fortune_telling2.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   69 |   scanf("%d", Q + i);
      |   ~~~~~^~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 49656 KB Output is correct
2 Correct 32 ms 49664 KB Output is correct
3 Correct 38 ms 49784 KB Output is correct
4 Correct 39 ms 49784 KB Output is correct
5 Correct 38 ms 49792 KB Output is correct
6 Correct 34 ms 49792 KB Output is correct
7 Correct 33 ms 49784 KB Output is correct
8 Correct 34 ms 49784 KB Output is correct
9 Correct 32 ms 49788 KB Output is correct
10 Correct 32 ms 49792 KB Output is correct
11 Correct 33 ms 49664 KB Output is correct
12 Correct 33 ms 49664 KB Output is correct
13 Correct 33 ms 49664 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 49656 KB Output is correct
2 Correct 32 ms 49664 KB Output is correct
3 Correct 38 ms 49784 KB Output is correct
4 Correct 39 ms 49784 KB Output is correct
5 Correct 38 ms 49792 KB Output is correct
6 Correct 34 ms 49792 KB Output is correct
7 Correct 33 ms 49784 KB Output is correct
8 Correct 34 ms 49784 KB Output is correct
9 Correct 32 ms 49788 KB Output is correct
10 Correct 32 ms 49792 KB Output is correct
11 Correct 33 ms 49664 KB Output is correct
12 Correct 33 ms 49664 KB Output is correct
13 Correct 33 ms 49664 KB Output is correct
14 Correct 58 ms 51452 KB Output is correct
15 Correct 94 ms 53236 KB Output is correct
16 Correct 139 ms 55276 KB Output is correct
17 Correct 171 ms 57072 KB Output is correct
18 Correct 169 ms 57072 KB Output is correct
19 Correct 169 ms 57072 KB Output is correct
20 Correct 164 ms 56816 KB Output is correct
21 Correct 158 ms 56128 KB Output is correct
22 Correct 113 ms 55280 KB Output is correct
23 Correct 110 ms 55024 KB Output is correct
24 Correct 108 ms 54636 KB Output is correct
25 Correct 114 ms 55408 KB Output is correct
26 Correct 111 ms 53488 KB Output is correct
27 Correct 126 ms 53744 KB Output is correct
28 Correct 114 ms 54128 KB Output is correct
29 Correct 111 ms 52464 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 49656 KB Output is correct
2 Correct 32 ms 49664 KB Output is correct
3 Correct 38 ms 49784 KB Output is correct
4 Correct 39 ms 49784 KB Output is correct
5 Correct 38 ms 49792 KB Output is correct
6 Correct 34 ms 49792 KB Output is correct
7 Correct 33 ms 49784 KB Output is correct
8 Correct 34 ms 49784 KB Output is correct
9 Correct 32 ms 49788 KB Output is correct
10 Correct 32 ms 49792 KB Output is correct
11 Correct 33 ms 49664 KB Output is correct
12 Correct 33 ms 49664 KB Output is correct
13 Correct 33 ms 49664 KB Output is correct
14 Correct 58 ms 51452 KB Output is correct
15 Correct 94 ms 53236 KB Output is correct
16 Correct 139 ms 55276 KB Output is correct
17 Correct 171 ms 57072 KB Output is correct
18 Correct 169 ms 57072 KB Output is correct
19 Correct 169 ms 57072 KB Output is correct
20 Correct 164 ms 56816 KB Output is correct
21 Correct 158 ms 56128 KB Output is correct
22 Correct 113 ms 55280 KB Output is correct
23 Correct 110 ms 55024 KB Output is correct
24 Correct 108 ms 54636 KB Output is correct
25 Correct 114 ms 55408 KB Output is correct
26 Correct 111 ms 53488 KB Output is correct
27 Correct 126 ms 53744 KB Output is correct
28 Correct 114 ms 54128 KB Output is correct
29 Correct 111 ms 52464 KB Output is correct
30 Correct 202 ms 54376 KB Output is correct
31 Correct 370 ms 62052 KB Output is correct
32 Correct 611 ms 71012 KB Output is correct
33 Correct 1044 ms 89308 KB Output is correct
34 Correct 167 ms 53992 KB Output is correct
35 Correct 1079 ms 95068 KB Output is correct
36 Correct 1046 ms 95000 KB Output is correct
37 Correct 1078 ms 95116 KB Output is correct
38 Correct 1051 ms 94940 KB Output is correct
39 Correct 1020 ms 93916 KB Output is correct
40 Correct 921 ms 88508 KB Output is correct
41 Correct 1025 ms 94628 KB Output is correct
42 Correct 1059 ms 93648 KB Output is correct
43 Correct 488 ms 85980 KB Output is correct
44 Correct 476 ms 86236 KB Output is correct
45 Correct 481 ms 86552 KB Output is correct
46 Correct 520 ms 82652 KB Output is correct
47 Correct 429 ms 74588 KB Output is correct
48 Correct 616 ms 81116 KB Output is correct
49 Correct 605 ms 79584 KB Output is correct