oj.uz

Submission #130864

# Submission time Handle Problem Language Result Execution time Memory
130864 2019-07-16T07:45:27 Z 윤교준(#3170) Bodyguards (CEOI10_bodyguards) C++14
0 / 100
 311 ms 24844 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].second+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].second+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();
		/*
		for(ll j = 1; j <= n; j++)
			if(f(c+j) < presum + v*j) 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 19064 KB Output is correct
2 Correct 23 ms 19192 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 19196 KB Output is correct
6 Correct 22 ms 19064 KB Output is correct
7 Incorrect 22 ms 19064 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 19192 KB Output is correct
2 Correct 23 ms 19192 KB Output is correct
3 Incorrect 22 ms 19164 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 19192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 19192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 23 ms 19192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 12920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 13176 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 20616 KB Output is correct
2 Incorrect 64 ms 20084 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 173 ms 21956 KB Output is correct
2 Incorrect 145 ms 21156 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 311 ms 24844 KB Output isn't correct
2 Halted 0 ms 0 KB -