oj.uz

Submission #591520

# Submission time Handle Problem Language Result Execution time Memory
591520 2022-07-07T14:31:20 Z Blagojce Nuclearia (CEOI15_nuclearia) C++11
55 / 100
 1000 ms 122592 KB 
#include <bits/stdc++.h>
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define st first
#define nd second
#define pb push_back
#define pq priority_queue
#define all(x) begin(x), end(x)

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int mxn = 2e5+5;


ll w, h;
ll n;
ll q;

ll x[mxn], y[mxn], a[mxn], b[mxn];


vector<vector<ll> > mat;
vector<vector<ll> > del1;
vector<vector<ll> > del2;

vector<vector<ll> > D1;
vector<vector<ll> > D2;



int main(){
	cin >> w >> h;
	
	mat.resize(h);
	fr(i, 0, h) mat[i].resize(w+1);
	
	del1.resize(h);
	fr(i, 0, h) del1[i].resize(w+1);
	
	del2.resize(h);
	fr(i, 0, h) del2[i].resize(w+1);
	
	
	D1.resize(h);
	fr(i, 0, h) D1[i].resize(w+1);
	
	D2.resize(h);
	fr(i, 0, h) D2[i].resize(w+1);
	
	
	fr(i, 0, h) fr(j, 0, w+1) mat[i][j] = 0;
	fr(i, 0, h) fr(j, 0, w+1) del1[i][j] = 0;
	fr(i, 0, h) fr(j, 0, w+1) del2[i][j] = 0;
	fr(i, 0, h) fr(j, 0, w+1) D1[i][j] = 0;
	fr(i, 0, h) fr(j, 0, w+1) D2[i][j] = 0;
	
	
	cin >> n;
	fr(i, 0, n){
		cin >> x[i] >> y[i] >> a[i] >> b[i];
		x[i] --, y[i] --;
	}
	fr(i, 0, h){
		fr(j, 0, n){
			ll dist = abs(y[j] - i);
			ll val = a[j] - b[j]*dist;
			if(val <= 0) continue;
			
			ll p1 = max(x[j] - dist, 0LL);
			ll p2 = min(x[j] + dist, w-1);
			
			ll d = val/b[j];
			
			ll mxL = max(0LL, p1 - d);
			ll mxR = min(w-1, p2 + d);
			
			mat[i][mxL]   += val;
			mat[i][mxR+1] -= val;
			
			if(mxL < p1){
				del2[i][p1]  -= b[j];
				del2[i][mxL] += b[j];
				D2[i][mxL]   += d*b[j];
				
			}
			if(mxR > p2){
				del1[i][p2]  -= b[j];
				del1[i][mxR] += b[j];
				D1[i][mxR]   += d*b[j];
			}
		}
	}
	fr(i, 0, h){
		ll sum = 0;
		fr(j, 0, w){
			sum += mat[i][j];
			mat[i][j] = sum;
		}
	}
	fr(i, 0, h){
		ll delta=0;
		ll sum = 0;
		
		
		for(int j = 0; j < w;    j ++){
			sum += delta;
			mat[i][j] += sum;
			sum += D1[i][j];
			delta += del1[i][j];
		}
		
		delta = 0;
		sum = 0;
		for(int j = w-1; j >= 0; j --){
			sum += delta;
			mat[i][j] += sum;
			sum += D2[i][j];
			delta += del2[i][j];
		}
	}
	
	
	
	fr(i, 0, h){
		ll sum = 0;
		fr(j, 0, w){
			ll tot = sum + mat[i][j];
			if(i > 0) tot += mat[i-1][j];
			sum += mat[i][j];
			
			mat[i][j] = tot;
		}
	}
	
	
	cin >> q;
	fr(i, 0, q){
		ll r1, c1, r2, c2;
		cin >> c1 >> r1 >> c2 >> r2;
		--r1, --c1, r2--, c2--;
		ll SUM = mat[r2][c2];
		if(r1 > 0) SUM -= mat[r1-1][c2];
		if(c1 > 0) SUM -= mat[r2][c1-1];
		if(r1 > 0 && c1 > 0) SUM += mat[r1-1][c1-1];
		
		
		ll tot = (r2-r1+1)*(c2-c1+1);
		cout<<(SUM + (tot/2))/tot<<endl;
	}
}/*
4 3
1
3 2 4 2
*/

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 98064 KB Output is correct
2 Correct 363 ms 2888 KB Output is correct
3 Correct 355 ms 2436 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 75 ms 98060 KB Output is correct
2 Correct 366 ms 2816 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 98228 KB Output is correct
2 Correct 431 ms 2800 KB Output is correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 122592 KB Output is correct
2 Correct 379 ms 2880 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 100300 KB Output is correct
2 Correct 382 ms 3012 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 528 ms 41788 KB Output is correct
2 Correct 394 ms 2820 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 527 ms 101524 KB Output is correct
2 Correct 404 ms 3036 KB Output is correct

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 496 ms 41828 KB Output is correct
2 Correct 349 ms 2852 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 741 ms 106820 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 695 ms 106816 KB Output is correct

Subtask #11
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1095 ms 104396 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1103 ms 104548 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 12.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1105 ms 109068 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1105 ms 104464 KB Time limit exceeded
2 Halted 0 ms 0 KB -