oj.uz

Submission #591506

# Submission time Handle Problem Language Result Execution time Memory
591506 2022-07-07T14:14:07 Z Blagojce Nuclearia (CEOI15_nuclearia) C++11
30 / 100
 1000 ms 122572 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;
		
		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){
		fr(j, 0, w){
			if(mat[i][j]<0) cout<<2/0<<endl;
		}
	}
	
	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];
		
		
		
		long double ans = 1.0*SUM/((r2-r1+1)*(c2-c1+1));
		
		cout<<(ll)roundl(ans)<<endl;
	}
}/*
4 3
1
3 2 4 2
*/

Compilation message

nuclearia.cpp: In function 'int main()':
nuclearia.cpp:124:27: warning: division by zero [-Wdiv-by-zero]
  124 |    if(mat[i][j]<0) cout<<2/0<<endl;
      |                          ~^~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 98124 KB Output is correct
2 Correct 408 ms 2720 KB Output is correct
3 Correct 388 ms 2204 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 98172 KB Output is correct
2 Correct 445 ms 2664 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 98252 KB Output is correct
2 Correct 440 ms 2668 KB Output is correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 122572 KB Output is correct
2 Correct 436 ms 2736 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 577 ms 100388 KB Output is correct
2 Correct 453 ms 2960 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 535 ms 41792 KB Output is correct
2 Correct 413 ms 2708 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 558 ms 101464 KB Output is correct
2 Correct 422 ms 2896 KB Output is correct

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 502 ms 41840 KB Output is correct
2 Correct 400 ms 2604 KB Output is correct

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 753 ms 106740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 819 ms 106696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1084 ms 104408 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 1047 ms 104524 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 1090 ms 109016 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 1099 ms 104408 KB Time limit exceeded
2 Halted 0 ms 0 KB -