#include<bits/stdc++.h>
typedef long long ll;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pbds tree<pair<ll, ll>, null_type, less<pair<ll,ll>>,rb_tree_tag, tree_order_statistics_node_update>
using namespace __gnu_pbds;
#define speed ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
////////////////////Only Clear Code//////////////////////////
#define int ll
void usaco_problem(){
freopen("milkvisits.in", "r", stdin);
freopen("milkvisits.out", "w", stdout);
}
void init(){
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE
}
const int mx = (1e5+5)*4;
const int LOG = 25;
const ll inf = 1e18;
const ll mod = 1e8;
ll obstacles[mx];
int m;
vector<ll> pf[mx];
vector<pair<ll, ll>> segtree[mx];
vector<pair<ll, ll>> v;
void merge(int node){
int a = node*2;
int b = a+1;
int i = 0, j = 0;
int n = segtree[a].size();
int m = segtree[b].size();
while(i < n && j < m){
if(segtree[a][i] < segtree[b][j]){
segtree[node].push_back(segtree[a][i]);
i++;
}
else{
segtree[node].push_back(segtree[b][j]);
j++;
}
}
while(i < n){
segtree[node].push_back(segtree[a][i]);
i++;
}
while(j < m){
segtree[node].push_back(segtree[b][j]);
j++;
}
pf[node].push_back(segtree[node][0].second);
for(ll i = 1; i < segtree[node].size();i++){
pf[node].push_back(pf[node].back() + segtree[node][i].second);
}
}
void build(ll node, ll l, ll r) {
if (l == r){
pf[node].push_back(v[l].first);
segtree[node] = vector<pair<ll, ll>>(1, {v[l].second, v[l].first});
return;
}
ll md = (l + r) / 2;
build(node*2, l, md);
build(node*2+1, md+1, r);
merge(node);
}
ll bn(vector<pair<ll, ll>> &v, pair<ll, ll> p){
ll l = 0, r = v.size()-1;
ll ans = v.size();
while(l <= r){
int md = (l+r)/2;
if(v[md] >= p){
ans = md;
r = md-1;
}
else{
l = md+1;
}
}
return ans;
}
ll query(ll node, ll qlow, ll qhigh, ll l, ll r, ll silver){
if(node >= m){
ll ind1 = bn(segtree[node], {qlow, (ll)0});
ll ind2 = bn(segtree[node], {qhigh, (ll)1e9});
if(ind2 == segtree[node].size() || segtree[node][ind2].first > qhigh)ind2--;
ll sum = 0;
if(ind1<=ind2)sum = pf[node][ind2] - (ind1 == 0 ? 0 : pf[node][ind1-1]);
ll sz = ind2-ind1+1;
if(ind1>ind2)sz = 0;
if(silver >= sum){
return sz;
}
return 0;
}
ll md = (l+r)/2;
// sum on left
ll ind1 = bn(segtree[node*2], {qlow, 0});
ll ind2 = bn(segtree[node*2], {qhigh, 1e9});
if(ind2 == segtree[node*2].size() || segtree[node*2][ind2].first > qhigh)ind2--;
ll suml = 0;
//cout << node << " " << ind1 << " " << ind2 << endl;
if(ind1<=ind2)suml = pf[node*2][ind2] - (ind1 == 0 ? 0 : pf[node*2][ind1-1]);
//cout << node << " " << suml << " " << silver << endl;
if(suml >= silver){
return query(node*2, qlow, qhigh, l, md, silver);
}
ll sz = ind2-ind1+1;
if(ind1>ind2)sz = 0;
return sz + query(node*2+1, qlow, qhigh, md+1, r, silver-suml);
}
int _count(int n){
int c = 0;
while(n > 0){
c+= (n&1);
n/=2;
}
return c;
}
void run_case(){
int n, q;cin >> n >> m >> q;
for(int i = 0; i < n-1;i++){
ll a, b;cin >> a >> b;
}
for(int i = 0; i < m;i++){
ll a, b;cin >> a >> b;a--;
v.push_back({b, a});
obstacles[a]++;
}
for(int i = 1; i < n;i++){
obstacles[i] += obstacles[i-1];
}
sort(v.begin(), v.end());
while(_count(m) != 1){
m++;
v.push_back({1e9, 1e9});
}
build(1, 0, m-1);
for(int i = 0; i < q;i++){
ll a, b, gold, silver;cin >> a >> b >> gold >> silver;
a--;b--;
if(b < a)swap(a, b);
b--;
if(b < a){
cout << gold << endl;
continue;
}
ll x = query(1, a, b, 0, m-1, silver);
ll tot = obstacles[b] - (a == 0 ? 0 : obstacles[a-1]);
gold -= max(tot - x, (ll)0);
//cout << x << " " << tot << endl;
cout << max(gold, (ll)-1) << endl;
}
}
int32_t main(){
speed;
int t = 1;
//cin >> t;
while(t--){
run_case();
}
}
/*
NEVER GIVE UP!
DOING SMTHNG IS BETTER THAN DOING NTHNG!!!
Your Guide when stuck:
- Continue keyword only after reading the whole input
- Don't use memset with testcases
- Check for corner cases(n=1, n=0)
- Check where you declare n(Be careful of declaring it globally and in main)
*/
Compilation message
currencies.cpp: In function 'void merge(ll)':
currencies.cpp:62:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(ll i = 1; i < segtree[node].size();i++){
| ~~^~~~~~~~~~~~~~~~~~~~~~
currencies.cpp: In function 'll query(ll, ll, ll, ll, ll, ll)':
currencies.cpp:99:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
99 | if(ind2 == segtree[node].size() || segtree[node][ind2].first > qhigh)ind2--;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:114:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | if(ind2 == segtree[node*2].size() || segtree[node*2][ind2].first > qhigh)ind2--;
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp: In function 'void usaco_problem()':
currencies.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | freopen("milkvisits.in", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | freopen("milkvisits.out", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp: In function 'void init()':
currencies.cpp:19:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
19 | freopen("input.txt", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
currencies.cpp:21:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
21 | freopen("output.txt", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
19028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
19028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
19028 KB |
Output is correct |
| 2 |
Correct |
15 ms |
19796 KB |
Output is correct |
| 3 |
Correct |
15 ms |
19924 KB |
Output is correct |
| 4 |
Correct |
16 ms |
19924 KB |
Output is correct |
| 5 |
Correct |
370 ms |
56808 KB |
Output is correct |
| 6 |
Correct |
385 ms |
56648 KB |
Output is correct |
| 7 |
Correct |
610 ms |
92836 KB |
Output is correct |
| 8 |
Correct |
813 ms |
93848 KB |
Output is correct |
| 9 |
Correct |
795 ms |
93888 KB |
Output is correct |
| 10 |
Correct |
832 ms |
93840 KB |
Output is correct |
| 11 |
Correct |
708 ms |
93872 KB |
Output is correct |
| 12 |
Correct |
711 ms |
93816 KB |
Output is correct |
| 13 |
Correct |
678 ms |
93820 KB |
Output is correct |
| 14 |
Correct |
483 ms |
93752 KB |
Output is correct |
| 15 |
Correct |
477 ms |
93580 KB |
Output is correct |
| 16 |
Correct |
547 ms |
93808 KB |
Output is correct |
| 17 |
Correct |
553 ms |
93840 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
19028 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
