#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <cassert>
using namespace std;
typedef long long ll;
const int maxn=2500000;
ll range[maxn*2];
ll najl[maxn*2];
ll pref[maxn+1];
void precompute(){
for(int i=maxn; i<maxn*2; i++){
range[i]=1;
najl[i]=i-maxn;
}
for(int i=maxn-1; i>0; i--){
range[i]=range[i*2]*2;
najl[i]=najl[i*2];
}
}
struct tournament{
ll t[maxn*2];
pair < ll, ll > prop[maxn*2];
void propagate(int &x){
if(!prop[x].first && !prop[x].second){
return;
}
t[x]+=prop[x].first*range[x]+prop[x].second*(range[x]*(range[x]-1)/2);
if(x<maxn){
prop[x*2].first+=prop[x].first;
prop[x*2].second+=prop[x].second;
prop[x*2+1].first+=prop[x].first+prop[x].second*(range[x]/2);
prop[x*2+1].second+=prop[x].second;
}
prop[x].first=0;
prop[x].second=0;
}
void update(int x, ll val){
for(; x; x>>=1){
t[x]+=val;
}
}
void update2(int l, int d, pair < ll, ll > val){
ll L=l;
d++;
int x;
ll val1;
for(l+=maxn, d+=maxn; l<d; l>>=1, d>>=1){
if(l&1){
x=l++;
val1=val.first+val.second*(najl[x]-L);
update(x, val1*range[x]+val.second*(range[x]*(range[x]-1)/2));
if(x<maxn){
prop[x*2].first+=val1;
prop[x*2].second+=val.second;
prop[x*2+1].first+=val1+val.second*(range[x]/2);
prop[x*2+1].second+=val.second;
}
}
if(d&1){
x=--d;
val1=val.first+val.second*(najl[x]-L);
update(x, val1*range[x]+val.second*(range[x]*(range[x]-1)/2));
if(x<maxn){
prop[x*2].first+=val1;
prop[x*2].second+=val.second;
prop[x*2+1].first+=val1+val.second*(range[x]/2);
prop[x*2+1].second+=val.second;
}
}
}
}
ll query(int l, int d){
d++;
ll sol=0;
for(l+=maxn, d+=maxn; l<d; l>>=1, d>>=1){
if(l&1){
sol+=t[l++];
}
if(d&1){
sol+=t[--d];
}
}
return sol;
}
void resi(){
for(int i=1; i<maxn*2; i++){
propagate(i);
}
}
};
tournament T;
int main(){
precompute();
int h, w;
scanf("%d%d", &w, &h);
bool p=0;
if(h>w){
swap(h, w);
}
assert(h==1);
int n, q;
scanf("%d", &n);
int a, b, c, d;
int kol;
int l, r;
pair < ll, ll > val;
for(int i=0; i<n; i++){
scanf("%d%d%d%d", &a, &b, &c, &d);
a--;
b--;
if(!p){
swap(a, b);
}
kol=c/d;
l=b-kol;
r=b;
if(l>-1){
val={c%d, d};
}
else{
val={c%d-l*d, d};
l=0;
}
// cout << "upd " << val.first << ' ' << val.second << endl;
T.update2(l, r, val);
l=b+1;
r=b+kol;
r=min(r, w-1);
val={c-d, -d};
if(l<=r){
T.update2(l, r, val);
}
}
T.resi();
for(int i=0; i<w; i++){
pref[i+1]=pref[i]+T.t[i+maxn];
}
/* for(int i=0; i<w; i++){
cout << T.query(i, i) << ' ';
}
cout << endl;*/
scanf("%d", &q);
ll sol, dij, res;
for(int i=0; i<q; i++){
scanf("%d%d%d%d", &a, &b, &c, &d);
if(!p){
swap(a, b);
swap(c, d);
}
sol=pref[d]-pref[b-1];
dij=d-b+1;
res=sol/dij;
if(sol%dij>=(dij+1)/2){
res++;
}
printf("%lld\n", res);
// printf("%lld\n", (ll)T.query(0, pot-1, 1, b, d));
}
return 0;
}
Compilation message
nuclearia.cpp: In function 'int main()':
nuclearia.cpp:106:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
106 | scanf("%d%d", &w, &h);
| ~~~~~^~~~~~~~~~~~~~~~
nuclearia.cpp:113:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
113 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
nuclearia.cpp:119:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
119 | scanf("%d%d%d%d", &a, &b, &c, &d);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
nuclearia.cpp:153:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
153 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
nuclearia.cpp:156:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
156 | scanf("%d%d%d%d", &a, &b, &c, &d);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
125 ms |
215464 KB |
Output is correct |
| 2 |
Correct |
166 ms |
159296 KB |
Output is correct |
| 3 |
Correct |
160 ms |
158900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
125 ms |
215460 KB |
Output is correct |
| 2 |
Correct |
168 ms |
159256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
232 ms |
317848 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
232 ms |
317868 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
258 ms |
217668 KB |
Output is correct |
| 2 |
Correct |
178 ms |
159556 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
219 ms |
182788 KB |
Output is correct |
| 2 |
Correct |
212 ms |
159256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
229 ms |
317844 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
236 ms |
317872 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
948 ms |
217928 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
922 ms |
217900 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
230 ms |
317940 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
225 ms |
317872 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
234 ms |
317880 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
246 ms |
317780 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
