#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];
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++){
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);
a--;
b--;
c--;
d--;
if(!p){
swap(a, b);
swap(c, d);
}
sol=T.query(b, d);
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:105:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
105 | scanf("%d%d", &w, &h);
| ~~~~~^~~~~~~~~~~~~~~~
nuclearia.cpp:112:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
112 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
nuclearia.cpp:118:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
118 | scanf("%d%d%d%d", &a, &b, &c, &d);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
nuclearia.cpp:149:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
149 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
nuclearia.cpp:152:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
152 | scanf("%d%d%d%d", &a, &b, &c, &d);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
113 ms |
195900 KB |
Output is correct |
| 2 |
Correct |
174 ms |
159324 KB |
Output is correct |
| 3 |
Correct |
155 ms |
158920 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
113 ms |
195984 KB |
Output is correct |
| 2 |
Correct |
174 ms |
159200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
225 ms |
317848 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
229 ms |
317772 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
271 ms |
198072 KB |
Output is correct |
| 2 |
Correct |
190 ms |
159452 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
247 ms |
174920 KB |
Output is correct |
| 2 |
Correct |
180 ms |
159300 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
225 ms |
317816 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
221 ms |
317844 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
965 ms |
198268 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
965 ms |
198268 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
241 ms |
317948 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
226 ms |
317752 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
234 ms |
317848 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
230 ms |
317796 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
