oj.uz

답안 #130875

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
130875 2019-07-16T07:57:27 Z 윤교준(#3170) Bodyguards (CEOI10_bodyguards) C++14
100 / 100
 410 ms 30408 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define befv(V) ((V)[sz(V)-2])
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define rb(x) ((x)&(-(x)))
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef __int128_t lll;
typedef pair<ll, ll> pll;
inline void fuk() { puts("0"); exit(0); }

const int MAXN = 200055;
const int MAXM = 200055;
const int MAXK = 400055;

struct BIT {
	vector<ll> V;
	lll d[MAXK];
	int n;

	void init() { memset(d, 0, MAXK * sizeof(lll)); n = 0; V.clear(); }
	void add(ll x) { V.eb(x); }
	void precal() {
		sorv(V); univ(V);
		n = sz(V);
	}
	void upd(ll x, lll r) {
		int i = int(lower_bound(allv(V), x) - V.begin()) + 1;
		for(; i <= n; i += rb(i))
			d[i] += r;
	}
	lll get(ll x) {
		lll r = 0;
		int i = int(upper_bound(allv(V), x) - V.begin());
		for(; i; i -= rb(i))
			r += d[i];
		return r;
	}
} bita, bitb;

pll A[MAXN], B[MAXM];

int N, M;

lll f(ll X) { return bita.get(X) * X + bitb.get(X); }

void solve() {
	bita.init(); bitb.init();

	for(int i = 1; i <= N; i++) {
		bita.add(1);
		bita.add(A[i].first+1);
		bitb.add(A[i].first+1);
	}
	bita.precal(); bitb.precal();
	for(int i = 1; i <= N; i++) {
		bita.upd(1, A[i].second);
		bita.upd(A[i].first+1, -A[i].second);
		bitb.upd(A[i].first+1, A[i].first * A[i].second);
	}

	ll presum = 0, c = 0;
	for(int i = 1; i <= M; i++) {
		ll v, n; tie(v, n) = B[i];
		if(f(c+1) < presum + v) fuk();
		if(f(c+n) < presum + v*n) fuk();
		presum += v*n;
		c += n;
	}
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N;
	for(int i = 1; i <= N; i++) cin >> A[i].first >> A[i].second;
	cin >> M;
	for(int i = 1; i <= M; i++) cin >> B[i].first >> B[i].second;

	sort(A+1, A+N+1); reverse(A+1, A+N+1);
	sort(B+1, B+M+1); reverse(B+1, B+M+1);

	solve();

	swap(N, M);
	swap(A, B);

	solve();

	puts("1");
	return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 19064 KB Output is correct
2 Correct 22 ms 19064 KB Output is correct
3 Correct 12 ms 12920 KB Output is correct
4 Correct 22 ms 19064 KB Output is correct
5 Correct 22 ms 19064 KB Output is correct
6 Correct 22 ms 19192 KB Output is correct
7 Correct 12 ms 12920 KB Output is correct
8 Correct 12 ms 12920 KB Output is correct
9 Correct 22 ms 19064 KB Output is correct
10 Correct 12 ms 12920 KB Output is correct
11 Correct 23 ms 19064 KB Output is correct
12 Correct 22 ms 19196 KB Output is correct
13 Correct 12 ms 12796 KB Output is correct
14 Correct 12 ms 12920 KB Output is correct
15 Correct 12 ms 12920 KB Output is correct
16 Correct 21 ms 19064 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 19192 KB Output is correct
2 Correct 22 ms 19192 KB Output is correct
3 Correct 12 ms 12920 KB Output is correct
4 Correct 13 ms 12920 KB Output is correct
5 Correct 12 ms 12924 KB Output is correct
6 Correct 26 ms 19164 KB Output is correct
7 Correct 22 ms 19064 KB Output is correct
8 Correct 12 ms 12920 KB Output is correct
9 Correct 12 ms 12920 KB Output is correct
10 Correct 14 ms 12884 KB Output is correct
11 Correct 12 ms 12924 KB Output is correct
12 Correct 12 ms 12920 KB Output is correct
13 Correct 12 ms 12920 KB Output is correct
14 Correct 22 ms 19068 KB Output is correct
15 Correct 22 ms 19064 KB Output is correct
16 Correct 22 ms 19192 KB Output is correct
17 Correct 22 ms 19196 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 12920 KB Output is correct
2 Correct 12 ms 12920 KB Output is correct
3 Correct 22 ms 19192 KB Output is correct
4 Correct 22 ms 19192 KB Output is correct
5 Correct 12 ms 12888 KB Output is correct
6 Correct 23 ms 19192 KB Output is correct
7 Correct 22 ms 19192 KB Output is correct
8 Correct 23 ms 19192 KB Output is correct
9 Correct 12 ms 12920 KB Output is correct
10 Correct 12 ms 12920 KB Output is correct
11 Correct 12 ms 12924 KB Output is correct
12 Correct 12 ms 12920 KB Output is correct
13 Correct 12 ms 12920 KB Output is correct
14 Correct 22 ms 19192 KB Output is correct
15 Correct 22 ms 19064 KB Output is correct
16 Correct 22 ms 19192 KB Output is correct
17 Correct 22 ms 19192 KB Output is correct
18 Correct 22 ms 19192 KB Output is correct

Subtask #4
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 12920 KB Output is correct
2 Correct 12 ms 12920 KB Output is correct
3 Correct 12 ms 12920 KB Output is correct
4 Correct 22 ms 19192 KB Output is correct
5 Correct 27 ms 19192 KB Output is correct
6 Correct 22 ms 19192 KB Output is correct
7 Correct 22 ms 19192 KB Output is correct
8 Correct 12 ms 12920 KB Output is correct
9 Correct 13 ms 12920 KB Output is correct
10 Correct 13 ms 12924 KB Output is correct
11 Correct 13 ms 13048 KB Output is correct
12 Correct 13 ms 12884 KB Output is correct
13 Correct 13 ms 12920 KB Output is correct
14 Correct 23 ms 19192 KB Output is correct
15 Correct 23 ms 19192 KB Output is correct
16 Correct 27 ms 19192 KB Output is correct
17 Correct 27 ms 19192 KB Output is correct
18 Correct 24 ms 19192 KB Output is correct

Subtask #5
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 12920 KB Output is correct
2 Correct 23 ms 19192 KB Output is correct
3 Correct 13 ms 12920 KB Output is correct
4 Correct 23 ms 19196 KB Output is correct
5 Correct 13 ms 12936 KB Output is correct
6 Correct 23 ms 19192 KB Output is correct
7 Correct 23 ms 19192 KB Output is correct
8 Correct 13 ms 12920 KB Output is correct
9 Correct 13 ms 12920 KB Output is correct
10 Correct 13 ms 13048 KB Output is correct
11 Correct 13 ms 12920 KB Output is correct
12 Correct 13 ms 12920 KB Output is correct
13 Correct 23 ms 19192 KB Output is correct
14 Correct 23 ms 19196 KB Output is correct
15 Correct 23 ms 19192 KB Output is correct
16 Correct 23 ms 19192 KB Output is correct
17 Correct 23 ms 19192 KB Output is correct
18 Correct 24 ms 19192 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 19192 KB Output is correct
2 Correct 22 ms 19192 KB Output is correct
3 Correct 22 ms 19108 KB Output is correct
4 Correct 22 ms 19164 KB Output is correct
5 Correct 12 ms 12892 KB Output is correct
6 Correct 12 ms 12920 KB Output is correct
7 Correct 12 ms 12920 KB Output is correct
8 Correct 12 ms 12920 KB Output is correct
9 Correct 12 ms 12920 KB Output is correct
10 Correct 12 ms 12920 KB Output is correct
11 Correct 12 ms 12920 KB Output is correct
12 Correct 12 ms 12920 KB Output is correct
13 Correct 12 ms 12920 KB Output is correct
14 Correct 22 ms 19064 KB Output is correct
15 Correct 22 ms 19192 KB Output is correct
16 Correct 22 ms 19064 KB Output is correct
17 Correct 22 ms 19192 KB Output is correct
18 Correct 22 ms 19064 KB Output is correct

Subtask #7
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 30 ms 19320 KB Output is correct
2 Correct 14 ms 13048 KB Output is correct
3 Correct 27 ms 19320 KB Output is correct
4 Correct 18 ms 13304 KB Output is correct
5 Correct 30 ms 19320 KB Output is correct
6 Correct 17 ms 13176 KB Output is correct
7 Correct 29 ms 19320 KB Output is correct
8 Correct 16 ms 13176 KB Output is correct
9 Correct 17 ms 13304 KB Output is correct
10 Correct 18 ms 13176 KB Output is correct
11 Correct 17 ms 13176 KB Output is correct
12 Correct 17 ms 13176 KB Output is correct
13 Correct 17 ms 13240 KB Output is correct
14 Correct 29 ms 19320 KB Output is correct
15 Correct 29 ms 19292 KB Output is correct
16 Correct 30 ms 19320 KB Output is correct
17 Correct 29 ms 19320 KB Output is correct
18 Correct 30 ms 19320 KB Output is correct

Subtask #8
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 79 ms 20592 KB Output is correct
2 Correct 35 ms 14396 KB Output is correct
3 Correct 97 ms 20820 KB Output is correct
4 Correct 59 ms 15836 KB Output is correct
5 Correct 96 ms 20916 KB Output is correct
6 Correct 67 ms 16088 KB Output is correct
7 Correct 79 ms 20588 KB Output is correct
8 Correct 63 ms 16148 KB Output is correct
9 Correct 58 ms 15860 KB Output is correct
10 Correct 58 ms 15808 KB Output is correct
11 Correct 60 ms 15860 KB Output is correct
12 Correct 73 ms 16108 KB Output is correct
13 Correct 58 ms 15860 KB Output is correct
14 Correct 105 ms 20876 KB Output is correct
15 Correct 103 ms 20868 KB Output is correct
16 Correct 103 ms 20848 KB Output is correct
17 Correct 108 ms 20844 KB Output is correct
18 Correct 107 ms 20932 KB Output is correct

Subtask #9
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 165 ms 21964 KB Output is correct
2 Correct 78 ms 17008 KB Output is correct
3 Correct 187 ms 22428 KB Output is correct
4 Correct 25 ms 13816 KB Output is correct
5 Correct 208 ms 22748 KB Output is correct
6 Correct 94 ms 18416 KB Output is correct
7 Correct 192 ms 22504 KB Output is correct
8 Correct 27 ms 13688 KB Output is correct
9 Correct 146 ms 19560 KB Output is correct
10 Correct 109 ms 18932 KB Output is correct
11 Correct 106 ms 18876 KB Output is correct
12 Correct 108 ms 19120 KB Output is correct
13 Correct 143 ms 19432 KB Output is correct
14 Correct 195 ms 22588 KB Output is correct
15 Correct 196 ms 22732 KB Output is correct
16 Correct 196 ms 22608 KB Output is correct
17 Correct 197 ms 22632 KB Output is correct
18 Correct 195 ms 22540 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 193 ms 23424 KB Output is correct
2 Correct 187 ms 23476 KB Output is correct
3 Correct 137 ms 20608 KB Output is correct
4 Correct 97 ms 21232 KB Output is correct
5 Correct 306 ms 25224 KB Output is correct
6 Correct 181 ms 27728 KB Output is correct
7 Correct 215 ms 26088 KB Output is correct
8 Correct 161 ms 26984 KB Output is correct
9 Correct 205 ms 28016 KB Output is correct
10 Correct 203 ms 28124 KB Output is correct
11 Correct 202 ms 29088 KB Output is correct
12 Correct 203 ms 29144 KB Output is correct
13 Correct 213 ms 29196 KB Output is correct
14 Correct 31 ms 14840 KB Output is correct
15 Correct 410 ms 30408 KB Output is correct
16 Correct 408 ms 30304 KB Output is correct
17 Correct 407 ms 30264 KB Output is correct
18 Correct 402 ms 30276 KB Output is correct