#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cassert>
using namespace std;
typedef long long ll;
const int Log=22, pot=(1<<Log);
ll range[pot*2];
ll najl[pot*2];
void precompute(){
for(int i=pot; i<pot*2; i++){
range[i]=1;
najl[i]=i-pot;
}
for(int i=pot-1; i>0; i--){
range[i]=range[i*2]*2;
najl[i]=najl[i*2];
}
}
struct tournament{
ll t[pot*2];
pair < ll, ll > prop[pot*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<pot){
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+=pot, d+=pot; 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<pot){
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<pot){
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+=pot, d+=pot; 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<pot*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);
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);
}
printf("%lld\n", (ll)round((double)T.query(b, d)/(d-b+1)));
// 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:150:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
150 | 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 |
177 ms |
302044 KB |
Output is correct |
| 2 |
Correct |
245 ms |
265528 KB |
Output is correct |
| 3 |
Correct |
271 ms |
265064 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
190 ms |
302048 KB |
Output is correct |
| 2 |
Correct |
256 ms |
265548 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
377 ms |
532848 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
455 ms |
532892 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
360 ms |
305172 KB |
Output is correct |
| 2 |
Correct |
300 ms |
266052 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
329 ms |
281884 KB |
Output is correct |
| 2 |
Correct |
258 ms |
265864 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
410 ms |
532988 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
398 ms |
532984 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1091 ms |
306204 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1072 ms |
305912 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
401 ms |
533024 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
435 ms |
533112 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
413 ms |
532980 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
389 ms |
532976 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
