#include <bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
vector<vector<long long> > val;
vector<vector<long long> > pref;
int n, m, p, q;
bool swp = 0;
void precalc(){
// cout << "pref: \n";
for(int i = 0; i < n; i++) {
long long s = 0;
for(int j = 0; j < m; j++) {
s += val[i][j];
pref[i][j] = (i == 0 ? 0ll : pref[i-1][j]) + s;
// cout << pref[i][j] << " ";
}
// cout << endl;
}
}
long long getSum(int e1, int s1, int e2, int s2) {
long long ret = 0;
ret += pref[e2][s2];
if(e1 != 0) {
ret -= pref[e1-1][s2];
}
if(s1 != 0){
ret -= pref[e2][s1-1];
}
if(e1 != 0 && s1 != 0) {
ret += pref[e1-1][s1-1];
}
return ret;
}
long long rnd(long long x, long long y) {
long long maz = x / y;
x %= y;
if(2ll*x >= y) maz++;
return maz;
}
void maz () {
for(int h = 0; h < p; h++) {
long long e, s, a, b;
cin >> s >> e >> a >> b; e--; s--;
if(swp) swap(e, s);
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
val[i][j] += max(0ll, 1ll * a - 1ll * b * max(abs(i-e), abs(s-j)));
}
}
}
precalc();
cin >> q;
while(q--) {
int e1, s1, e2, s2;
cin >> s1 >> e1 >> s2 >> e2; s1--; e1--; s2--; e2--;
if(swp) {
swap(e1, s1);
swap(e2, s2);
}
long long sm = getSum(e1, s1, e2, s2);
long long S = sm;
long long pl = (1+abs(e1-e2)) * (abs(s1-s2)+1);
long long ans = rnd(S, pl);
cout << ans << "\n";
}
}
void doEil(int eil, int s, int nutol, long long a, long long b, vector<vector<long long> > &A, vector<vector<long long> > &B){
long long nl = a / b;
long long prm = a % b;
int le = s - nl;
int mid = s;
int ri = s + nl;
le = max(0, le);
ri = min(ri, m-1);
long long vL = a - b * abs(le - s);
long long vR = a - b * abs(ri - s);
A[eil][le] += vL;
A[eil][ri+1] -= vR;
B[eil][le] += b;
B[eil][mid-nutol] -= b;
B[eil][mid+nutol] -= b;
// B[eil][mid] -= 2*b;
B[eil][ri] += b;
}
void h1(){
// vector<long long> A(m+2, 0), B(m+2, 0);
vector<vector<long long> > A(n, vector<long long> (m+2, 0)), B(n, vector<long long> (m+2, 0));
for(int h = 0; h < p; h++) {
long long e, s, a, b;
cin >> s >> e >> a >> b; e--; s--;
if(swp) {
swap(e, s);
}
long long nl = a / b;
for(int i = max(0ll, e-nl); i <= min(1ll*n-1, e+nl); i++) {
doEil(i, s, abs(i-e), a, b, A, B);
}
}
for(int j = 0; j < n; j++){
long long sitas = 0;
long long delta = 0;
for(int i = 0; i < m; i++) {
sitas += A[j][i];
sitas += delta;
val[j][i] = sitas;
delta += B[j][i];
}
}
// cout << "val: \n"; for(int i = 0; i < m; i++) cout << val[0][i] << " ";
// cout << endl << endl;
precalc();
cin >> q;
while(q--) {
int e1, s1, e2, s2;
cin >> s1 >> e1 >> s2 >> e2; s1--; e1--; s2--; e2--;
if(swp) {
swap(e1, s1);
swap(e2, s2);
}
long long sm = getSum(e1, s1, e2, s2);
long long S = sm;
long long pl = (1+abs(e1-e2)) * (abs(s1-s2)+1);
long long ans = rnd(S, pl);
cout << ans << "\n";
}
}
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> m >> n >> p;
// noriu visada eiti per eilutes. t.y., n <= m turi galioti!
if(n > m){
swap(n, m);
swp = 1;
}
vector<vector<long long> > iden(n, vector<long long> (m, 0));
val = iden; pref = iden;
h1();
return 0;
if(n == 1) {
h1();
return 0;
}else if(1ll * m * n * p <= 100000000ll) {
maz();
return 0;
}
return 0;
}
Compilation message
nuclearia.cpp: In function 'void doEil(int, int, int, long long int, long long int, std::vector<std::vector<long long int> >&, std::vector<std::vector<long long int> >&)':
nuclearia.cpp:73:15: warning: unused variable 'prm' [-Wunused-variable]
73 | long long prm = a % b;
| ^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
65 ms |
117628 KB |
Output is correct |
2 |
Correct |
64 ms |
4652 KB |
Output is correct |
3 |
Correct |
56 ms |
3844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
71 ms |
117700 KB |
Output is correct |
2 |
Correct |
74 ms |
4712 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
172 ms |
199120 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
51 ms |
99188 KB |
Output is correct |
2 |
Correct |
79 ms |
4572 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
171 ms |
123580 KB |
Output is correct |
2 |
Correct |
91 ms |
5244 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
115 ms |
53104 KB |
Output is correct |
2 |
Correct |
63 ms |
4612 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
254 ms |
205060 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
121 ms |
49216 KB |
Output is correct |
2 |
Runtime error |
1 ms |
464 KB |
Execution killed with signal 11 |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
264 ms |
127408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
270 ms |
127416 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1096 ms |
100460 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1090 ms |
99724 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1092 ms |
100968 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
1092 ms |
98932 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |