#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct segTree{
struct Node{
ll cnt, sum, lazy;
Node(){}
Node(ll cnt, ll sum, ll lazy): cnt(cnt), sum(sum), lazy(lazy){}
} tree[800002];
void init(int i, int l, int r){
tree[i] = Node(0, 0, 0);
if(l==r) return;
int m = (l+r)>>1;
init(i*2, l, m);
init(i*2+1, m+1, r);
}
void propagate(int i, int l, int r){
if(l==r) tree[i].sum -= tree[i].lazy * tree[i].cnt;
else tree[i*2].lazy += tree[i].lazy, tree[i*2+1].lazy += tree[i].lazy;
tree[i].lazy = 0;
}
void update(int i, int l, int r, int s, int e, ll v){
propagate(i, l, r);
if(r<s || e<l) return;
if(s<=l && r<=e){
tree[i].lazy += v;
propagate(i, l, r);
return;
}
int m = (l+r)>>1;
update(i*2, l, m, s, e, v);
update(i*2+1, m+1, r, s, e, v);
}
void setOne(int i, int l, int r, int x, ll cnt, ll v){
propagate(i, l, r);
if(r<x||x<l) return;
if(l==r){
tree[i] = Node(cnt, v, 0);
return;
}
int m = (l+r)>>1;
setOne(i*2, l, m, x, cnt, v);
setOne(i*2+1, m+1, r, x, cnt, v);
tree[i].cnt = tree[i*2].cnt += tree[i*2+1].cnt;
}
int kth(int i, int l, int r, ll v){
propagate(i, l, r);
if(l==r) return l;
int m = (l+r)>>1;
if(tree[i*2].cnt >= v) return kth(i*2, l, m, v);
else return kth(i*2+1, m+1, r, v-tree[i*2].cnt);
}
ll cntsum(int i, int l, int r, int s, int e){
propagate(i, l, r);
if(r<s||e<l) return 0;
if(s<=l&&r<=e) return tree[i].cnt;
int m = (l+r)>>1;
return cntsum(i*2, l, m, s, e) * cntsum(i*2+1, m+1, r, s, e);
}
ll cntOne(int i, int l, int r, int x){
propagate(i, l, r);
if(l==r) return tree[i].cnt;
int m = (l+r)>>1;
if(x<=m) return cntOne(i*2, l, m, x);
else return cntOne(i*2+1, m+1, r, x);
}
ll sumOne(int i, int l, int r, int x){
propagate(i, l, r);
if(l==r) return tree[i].sum;
int m = (l+r)>>1;
if(x<=m) return sumOne(i*2, l, m, x);
else return sumOne(i*2+1, m+1, r, x);
}
void updateOne(int i, int l, int r, int x, ll v){
propagate(i, l, r);
if(l==r){
tree[i].sum -= v;
return;
}
int m = (l+r)>>1;
if(x<=m) updateOne(i*2, l, m, x, v);
else updateOne(i*2+1, m+1, r, x, v);
}
} tree;
inline ll floorDiv(ll a, ll b){
return a/b;
}
inline ll ceilDiv(ll a, ll b){
return (a+b-1)/b;
}
int n, m;
pair<ll, ll> a[200002];
pair<ll, ll> b[200002];
set<int> st;
void checkMerge(int l, int r){
ll C1 = tree.cntOne(1, 1, m, l), V1 = tree.sumOne(1, 1, m, l);
ll C2 = tree.cntOne(1, 1, m, r), V2 = tree.sumOne(1, 1, m, r);
if((V1+C1-1)/C1 > V2/C2) return;
tree.setOne(1, 1, m, l, C1+C2, V1+V2);
tree.setOne(1, 1, m, r, 0, 0);
st.erase(r);
}
int main(){
scanf("%d", &n);
for(int i=1; i<=n; i++) scanf("%lld %lld", &a[i].first, &a[i].second);
scanf("%d", &m);
for(int i=1; i<=m; i++) scanf("%lld %lld", &b[i].first, &b[i].second);
sort(a+1, a+n+1); /// 짧은 것부터
sort(b+1, b+m+1), reverse(b+1, b+m+1); /// 긴 것부터
tree.init(1, 1, m);
for(int i=1; i<=m; i++){
int j = i; ll len=b[i].second;
while(j<m&&b[i].first==b[j+1].first) len+=b[++j].second;
tree.setOne(1, 1, m, i, len, len*b[i].first);
st.insert(i);
i=j;
}
for(int i=1; i<=n; i++){
ll C = a[i].first, V = a[i].second;
while(V){
int x = tree.kth(1, 1, m, C);
ll weight = C - tree.cntsum(1, 1, m, 1, x-1);
ll C2 = tree.cntOne(1, 1, m, x), V2 = tree.sumOne(1, 1, m, x);
ll C1=-1, V1=-1, C3=-1, V3=-1;
int l=-1, r=-1;
auto it = st.lower_bound(x);
ll tmp = V;
if(it != st.begin()){ /// 왼쪽과 합쳐질 가능성 있음
l = *prev(it);
C1 = tree.cntOne(1, 1, m, l), V1 = tree.sumOne(1, 1, m, l);
tmp = min(tmp, ceilDiv(C2 * floorDiv(V1, C1) - V2, C2-weight));
}
if(next(it) != st.end()){ /// 오른쪽과 합쳐질 가능성이 있음
r = *next(it);
C3 = tree.cntOne(1, 1, m, r), V3 = tree.sumOne(1, 1, m, r);
tmp = min(tmp, ceilDiv((V2+C2-1)*C3 - V3*C2, C3*weight));
}
if(tmp*weight > V2){
puts("0");
return 0;
}
/// 진행함
tree.update(1, 1, n, 1, x-1, tmp);
tree.updateOne(1, 1, n, x, tmp*weight);
V-=tmp;
/// 합칠 수 있는지 봄
if(r!=-1) checkMerge(x, r);
if(l!=-1) checkMerge(l, x);
}
}
puts("1");
}
Compilation message
bodyguards.cpp: In function 'int main()':
bodyguards.cpp:120:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
120 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
bodyguards.cpp:121:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
121 | for(int i=1; i<=n; i++) scanf("%lld %lld", &a[i].first, &a[i].second);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bodyguards.cpp:122:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
122 | scanf("%d", &m);
| ~~~~~^~~~~~~~~~
bodyguards.cpp:123:34: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
123 | for(int i=1; i<=m; i++) scanf("%lld %lld", &b[i].first, &b[i].second);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Incorrect |
0 ms |
304 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1071 ms |
212 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1051 ms |
340 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
2132 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
27 ms |
8904 KB |
Execution killed with signal 8 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1075 ms |
14332 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1062 ms |
17508 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
