oj.uz

답안 #656693

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
656693 2022-11-08T03:57:39 Z TranGiaHuy1508 운세 보기 2 (JOI14_fortune_telling2) C++17
35 / 100
 480 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

void main_program();

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	main_program();
}

// #define int long long

struct MaxImplicitSegtree{
	int lb, rb;
	MaxImplicitSegtree *leftnode, *rightnode;
	int mx;

	MaxImplicitSegtree(int L, int R): lb(L), rb(R), leftnode(nullptr), rightnode(nullptr), mx(-1) {}

	void extend(){
		if (lb == rb) return;
		if (leftnode) return;
		int mid = (lb + rb) >> 1;
		leftnode = new MaxImplicitSegtree(lb, mid);
		rightnode = new MaxImplicitSegtree(mid+1, rb);
	}

	int get(int l, int r){
		if (l <= lb && rb <= r) return mx;
		if (lb > r || rb < l) return -1;

		extend();
		return max(leftnode->get(l, r), rightnode->get(l, r));
	}

	void update(int x, int val){
		if (lb == x && rb == x) mx = val;
		else{
			extend();
			int mid = (lb + rb) >> 1;
			if (x <= mid) leftnode->update(x, val);
			else rightnode->update(x, val);

			mx = max(leftnode->mx, rightnode->mx);
		}
	}
};

struct SumImplicitSegtree{
	int lb, rb;
	SumImplicitSegtree *leftnode, *rightnode;
	int sum;

	SumImplicitSegtree(int L, int R): lb(L), rb(R), leftnode(nullptr), rightnode(nullptr), sum(0) {}

	void extend(){
		if (lb == rb) return;
		if (leftnode) return;
		int mid = (lb + rb) >> 1;
		leftnode = new SumImplicitSegtree(lb, mid);
		rightnode = new SumImplicitSegtree(mid+1, rb);
	}

	int get(int l, int r){
		if (l <= lb && rb <= r) return sum;
		if (lb > r || rb < l) return 0;

		extend();
		return leftnode->get(l, r) + rightnode->get(l, r);
	}

	void update(int x, int delta){
		if (lb == x && rb == x) sum += delta;
		else{
			extend();
			int mid = (lb + rb) >> 1;
			if (x <= mid) leftnode->update(x, delta);
			else rightnode->update(x, delta);

			sum = leftnode->sum + rightnode->sum;
		}
	}
};

const int inf = 1e9 + 1;
int n, q;
vector<pair<int, int>> cards;
vector<int> MN, MX, qs, lst, inv;

void main_program(){
	cin >> n >> q;
	qs.resize(q);
	cards.resize(n);
	MN.resize(n);
	MX.resize(n);
	lst.assign(n, -1);
	inv.assign(n, 0);

	for (int i = 0; i < n; i++){
		int A, B; cin >> A >> B;
		cards[i] = {A, B};
		MN[i] = min(A, B); MX[i] = max(A, B);
	}

	MaxImplicitSegtree ist(1, inf);
	SumImplicitSegtree sst(1, inf);

	for (int i = 0; i < q; i++){
		cin >> qs[i];
		ist.update(qs[i], i);
	}

	for (int i = 0; i < n; i++){
		if (MX[i] > MN[i]) lst[i] = ist.get(MN[i], MX[i] - 1);
	}

	// for (int i = 0; i < n; i++) cout << lst[i] << " ";
	// cout << "\n";

	vector<vector<int>> radix(q + 1);
	for (int i = 0; i < n; i++)	radix[lst[i] + 1].push_back(i);

	for (int i = q-1; i >= 0; i--){
		sst.update(qs[i], 1);
		for (auto j: radix[i]){
			// cout << j << "\n";
			inv[j] = sst.get(MX[j], inf);
		}
	}

	// for (int i = 0; i < n; i++) cout << inv[i] << " ";
	// cout << "\n";

	long long res = 0;
	for (int i = 0; i < n; i++){
		int crr;
		if (lst[i] >= 0) crr = MX[i];
		else crr = cards[i].first;

		if (inv[i] & 1) crr = cards[i].first + cards[i].second - crr;

		// cout << crr << "\n";
		res += crr;
	}

	cout << res << "\n";
}

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4436 KB Output is correct
2 Correct 6 ms 6100 KB Output is correct
3 Correct 9 ms 8404 KB Output is correct
4 Correct 9 ms 8404 KB Output is correct
5 Correct 10 ms 8532 KB Output is correct
6 Correct 9 ms 8276 KB Output is correct
7 Correct 9 ms 8788 KB Output is correct
8 Correct 7 ms 6996 KB Output is correct
9 Correct 5 ms 4180 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 7 ms 7252 KB Output is correct
12 Correct 7 ms 7040 KB Output is correct
13 Correct 8 ms 7380 KB Output is correct

Subtask #2
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4436 KB Output is correct
2 Correct 6 ms 6100 KB Output is correct
3 Correct 9 ms 8404 KB Output is correct
4 Correct 9 ms 8404 KB Output is correct
5 Correct 10 ms 8532 KB Output is correct
6 Correct 9 ms 8276 KB Output is correct
7 Correct 9 ms 8788 KB Output is correct
8 Correct 7 ms 6996 KB Output is correct
9 Correct 5 ms 4180 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 7 ms 7252 KB Output is correct
12 Correct 7 ms 7040 KB Output is correct
13 Correct 8 ms 7380 KB Output is correct
14 Correct 89 ms 65884 KB Output is correct
15 Correct 185 ms 120884 KB Output is correct
16 Correct 271 ms 172364 KB Output is correct
17 Correct 302 ms 228704 KB Output is correct
18 Correct 309 ms 221816 KB Output is correct
19 Correct 302 ms 224496 KB Output is correct
20 Correct 320 ms 240252 KB Output is correct
21 Correct 329 ms 198028 KB Output is correct
22 Correct 67 ms 16188 KB Output is correct
23 Correct 55 ms 13264 KB Output is correct
24 Correct 57 ms 10896 KB Output is correct
25 Correct 75 ms 20024 KB Output is correct
26 Correct 264 ms 183024 KB Output is correct
27 Correct 264 ms 198744 KB Output is correct
28 Correct 277 ms 190168 KB Output is correct
29 Correct 320 ms 221096 KB Output is correct

Subtask #3
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4436 KB Output is correct
2 Correct 6 ms 6100 KB Output is correct
3 Correct 9 ms 8404 KB Output is correct
4 Correct 9 ms 8404 KB Output is correct
5 Correct 10 ms 8532 KB Output is correct
6 Correct 9 ms 8276 KB Output is correct
7 Correct 9 ms 8788 KB Output is correct
8 Correct 7 ms 6996 KB Output is correct
9 Correct 5 ms 4180 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 7 ms 7252 KB Output is correct
12 Correct 7 ms 7040 KB Output is correct
13 Correct 8 ms 7380 KB Output is correct
14 Correct 89 ms 65884 KB Output is correct
15 Correct 185 ms 120884 KB Output is correct
16 Correct 271 ms 172364 KB Output is correct
17 Correct 302 ms 228704 KB Output is correct
18 Correct 309 ms 221816 KB Output is correct
19 Correct 302 ms 224496 KB Output is correct
20 Correct 320 ms 240252 KB Output is correct
21 Correct 329 ms 198028 KB Output is correct
22 Correct 67 ms 16188 KB Output is correct
23 Correct 55 ms 13264 KB Output is correct
24 Correct 57 ms 10896 KB Output is correct
25 Correct 75 ms 20024 KB Output is correct
26 Correct 264 ms 183024 KB Output is correct
27 Correct 264 ms 198744 KB Output is correct
28 Correct 277 ms 190168 KB Output is correct
29 Correct 320 ms 221096 KB Output is correct
30 Runtime error 480 ms 262144 KB Execution killed with signal 9
31 Halted 0 ms 0 KB -