Submission #591499

#	Time	Username	Problem	Language	Result	Execution time	Memory
591499		Blagojce	Nuclearia (CEOI15_nuclearia)	C++11	0 / 100	1095 ms	122616 KiB

nuclearia

#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
• Subtask 2: 0 / 2
• Subtask 3: 0 / 3
• Subtask 4: 0 / 2
• Subtask 5: 0 / 6
• Subtask 6: 0 / 4
• Subtask 7: 0 / 6
• Subtask 8: 0 / 4
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10
• Subtask 11: 0 / 15
• Subtask 12: 0 / 10
• Subtask 13: 0 / 12
• Subtask 14: 0 / 8