oj.uz

답안 #591503

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
591503 2022-07-07T14:13:05 Z Blagojce Nuclearia (CEOI15_nuclearia) C++11
30 / 100
 1000 ms 122632 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];
		if(SUM < 0) cout<<2/0<<endl;
		
		
		
		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:144:22: warning: division by zero [-Wdiv-by-zero]
  144 |   if(SUM < 0) cout<<2/0<<endl;
      |                     ~^~

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 59 ms 98080 KB Output is correct
2 Correct 363 ms 2688 KB Output is correct
3 Correct 374 ms 2344 KB Output is correct

Subtask #2
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 98068 KB Output is correct
2 Correct 375 ms 2724 KB Output is correct

Subtask #3
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 66 ms 98160 KB Output is correct
2 Correct 433 ms 2688 KB Output is correct

Subtask #4
2.0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 173 ms 122632 KB Output is correct
2 Correct 388 ms 2632 KB Output is correct

Subtask #5
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 540 ms 100384 KB Output is correct
2 Correct 378 ms 2880 KB Output is correct

Subtask #6
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 469 ms 41792 KB Output is correct
2 Correct 382 ms 2756 KB Output is correct

Subtask #7
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 530 ms 101572 KB Output is correct
2 Correct 394 ms 2912 KB Output is correct

Subtask #8
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 483 ms 41812 KB Output is correct
2 Correct 409 ms 2696 KB Output is correct

Subtask #9
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 702 ms 106808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 697 ms 106780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1100 ms 104396 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1075 ms 104480 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1089 ms 109052 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #14
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1099 ms 104396 KB Time limit exceeded
2 Halted 0 ms 0 KB -