#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 long long lll;
//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];
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;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
12792 KB |
Output is correct |
2 |
Correct |
16 ms |
12788 KB |
Output is correct |
3 |
Correct |
7 ms |
6648 KB |
Output is correct |
4 |
Correct |
16 ms |
12792 KB |
Output is correct |
5 |
Correct |
16 ms |
12792 KB |
Output is correct |
6 |
Correct |
15 ms |
12792 KB |
Output is correct |
7 |
Correct |
7 ms |
6652 KB |
Output is correct |
8 |
Correct |
7 ms |
6648 KB |
Output is correct |
9 |
Correct |
16 ms |
12868 KB |
Output is correct |
10 |
Correct |
7 ms |
6648 KB |
Output is correct |
11 |
Correct |
16 ms |
12792 KB |
Output is correct |
12 |
Correct |
15 ms |
12792 KB |
Output is correct |
13 |
Correct |
7 ms |
6640 KB |
Output is correct |
14 |
Correct |
7 ms |
6620 KB |
Output is correct |
15 |
Correct |
7 ms |
6648 KB |
Output is correct |
16 |
Correct |
15 ms |
12792 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
15 ms |
12792 KB |
Output is correct |
2 |
Correct |
16 ms |
12792 KB |
Output is correct |
3 |
Correct |
7 ms |
6648 KB |
Output is correct |
4 |
Correct |
7 ms |
6648 KB |
Output is correct |
5 |
Correct |
7 ms |
6648 KB |
Output is correct |
6 |
Correct |
15 ms |
12792 KB |
Output is correct |
7 |
Correct |
15 ms |
12792 KB |
Output is correct |
8 |
Correct |
7 ms |
6648 KB |
Output is correct |
9 |
Correct |
7 ms |
6648 KB |
Output is correct |
10 |
Correct |
7 ms |
6648 KB |
Output is correct |
11 |
Correct |
7 ms |
6648 KB |
Output is correct |
12 |
Correct |
7 ms |
6648 KB |
Output is correct |
13 |
Correct |
7 ms |
6652 KB |
Output is correct |
14 |
Correct |
16 ms |
12920 KB |
Output is correct |
15 |
Correct |
16 ms |
12920 KB |
Output is correct |
16 |
Correct |
16 ms |
12920 KB |
Output is correct |
17 |
Correct |
15 ms |
12920 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
6624 KB |
Output is correct |
2 |
Correct |
7 ms |
6648 KB |
Output is correct |
3 |
Correct |
15 ms |
12876 KB |
Output is correct |
4 |
Correct |
16 ms |
12796 KB |
Output is correct |
5 |
Correct |
7 ms |
6648 KB |
Output is correct |
6 |
Correct |
16 ms |
12792 KB |
Output is correct |
7 |
Correct |
16 ms |
12792 KB |
Output is correct |
8 |
Correct |
16 ms |
12920 KB |
Output is correct |
9 |
Correct |
7 ms |
6648 KB |
Output is correct |
10 |
Correct |
7 ms |
6648 KB |
Output is correct |
11 |
Correct |
7 ms |
6648 KB |
Output is correct |
12 |
Correct |
7 ms |
6648 KB |
Output is correct |
13 |
Correct |
7 ms |
6648 KB |
Output is correct |
14 |
Correct |
16 ms |
12920 KB |
Output is correct |
15 |
Correct |
16 ms |
12924 KB |
Output is correct |
16 |
Correct |
16 ms |
12840 KB |
Output is correct |
17 |
Correct |
15 ms |
12920 KB |
Output is correct |
18 |
Correct |
16 ms |
12920 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
6648 KB |
Output is correct |
2 |
Correct |
7 ms |
6648 KB |
Output is correct |
3 |
Correct |
7 ms |
6648 KB |
Output is correct |
4 |
Correct |
16 ms |
12920 KB |
Output is correct |
5 |
Correct |
16 ms |
12920 KB |
Output is correct |
6 |
Correct |
16 ms |
12920 KB |
Output is correct |
7 |
Correct |
16 ms |
12920 KB |
Output is correct |
8 |
Correct |
9 ms |
6648 KB |
Output is correct |
9 |
Correct |
8 ms |
6668 KB |
Output is correct |
10 |
Correct |
9 ms |
6648 KB |
Output is correct |
11 |
Correct |
8 ms |
6648 KB |
Output is correct |
12 |
Correct |
8 ms |
6648 KB |
Output is correct |
13 |
Correct |
8 ms |
6648 KB |
Output is correct |
14 |
Correct |
16 ms |
12920 KB |
Output is correct |
15 |
Correct |
16 ms |
12840 KB |
Output is correct |
16 |
Correct |
16 ms |
12920 KB |
Output is correct |
17 |
Correct |
16 ms |
12920 KB |
Output is correct |
18 |
Correct |
16 ms |
12920 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
6648 KB |
Output is correct |
2 |
Correct |
17 ms |
12920 KB |
Output is correct |
3 |
Correct |
8 ms |
6620 KB |
Output is correct |
4 |
Correct |
17 ms |
12920 KB |
Output is correct |
5 |
Correct |
8 ms |
6656 KB |
Output is correct |
6 |
Correct |
17 ms |
12920 KB |
Output is correct |
7 |
Correct |
17 ms |
12920 KB |
Output is correct |
8 |
Correct |
8 ms |
6648 KB |
Output is correct |
9 |
Correct |
8 ms |
6648 KB |
Output is correct |
10 |
Correct |
8 ms |
6648 KB |
Output is correct |
11 |
Correct |
8 ms |
6648 KB |
Output is correct |
12 |
Correct |
8 ms |
6648 KB |
Output is correct |
13 |
Correct |
17 ms |
12920 KB |
Output is correct |
14 |
Correct |
17 ms |
12812 KB |
Output is correct |
15 |
Correct |
17 ms |
12920 KB |
Output is correct |
16 |
Correct |
17 ms |
12920 KB |
Output is correct |
17 |
Correct |
17 ms |
12924 KB |
Output is correct |
18 |
Correct |
17 ms |
12920 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1084 ms |
12892 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1081 ms |
13052 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1081 ms |
9332 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1073 ms |
12204 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Execution timed out |
1077 ms |
17260 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |