oj.uz

Submission #591500

# Submission time Handle Problem Language Result Execution time Memory
591500 2022-07-07T14:09:53 Z Blagojce Nuclearia (CEOI15_nuclearia) C++11
0 / 100
 1000 ms 122636 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){
		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)round(ans)-1<<endl;
	}
}/*
4 3
1
3 2 4 2
*/

Subtask #1
0 / 3.0

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

Subtask #2
0 / 2.0

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

Subtask #3
0 / 3.0

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

Subtask #4
0 / 2.0

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

Subtask #5
0 / 6.0

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

Subtask #6
0 / 4.0

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

Subtask #7
0 / 6.0

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

Subtask #8
0 / 4.0

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

Subtask #9
0 / 15.0

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

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 736 ms 106740 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 1098 ms 104500 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 1097 ms 104508 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 1095 ms 108996 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 1094 ms 104480 KB Time limit exceeded
2 Halted 0 ms 0 KB -