oj.uz

Submission #384362

# Submission time Handle Problem Language Result Execution time Memory
384362 2021-04-01T13:05:54 Z Sorting Nuclearia (CEOI15_nuclearia) C++17
100 / 100
 667 ms 323516 KB 
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long lint;
  
int w, h, n, q;
lint **dx1, **low1, **low2;
lint *low3, *low4;
 
void Trace1(int depth, int px, int py, int d){
	if(depth == 0) return;
	if(px == 1 && py == 1){
		dx1[1][1] += 1ll * depth * d;
		return;
	}
	if(px == 1){
		int dx = min(py-1, depth);
		low4[py - dx + 1] += d;
		low4[py + 1] -= d;
		Trace1(depth - dx, 1, py - dx, d);
		return;
	}
	if(py == 1){
		int dx = min(px-1, depth);
		low3[px - dx + 1] += d;
		low3[px + 1] -= d;
		Trace1(depth - dx, px - dx, 1, d);
		return;
	}
	int dx = min(px-1, min(py-1, depth));
	low1[px - dx + 1][py - dx + 1] += d;
	low1[px + 1][py + 1] -= d;
	Trace1(depth - dx, px - dx, py - dx, d);
}
  
void Trace2(int depth, int px, int py, int d){
	if(depth == 0) return;
	if(px == 1){
		int dx = min(h + 1 - py, depth);
		low4[py] += d;
		low4[py + dx] -= d;
		return;
	}
	if(py == h+1) return;
	int dx = min(depth, min(h + 1 - py, px - 1));
	low2[px - dx + 1][py + dx - 1] += d;
	low2[px+1][py -1] -= d;
	Trace2(depth - dx, px - dx, py + dx, d);
}
  
void Trace3(int depth, int px, int py, int d){
	if(depth == 0) return;
	if(px == w+1) return;
	if(py == 1){
		int dx = min(w + 1 - px, depth);
		low3[px] += d;
		low3[px + dx] -= d;
		return;
	}
	int dx = min(depth, min(w + 1 - px, py - 1));
	low2[px][py] += d;
	low2[px + dx][py - dx] -= d;
	Trace3(depth - dx, px + dx, py - dx, d);
}
  
void Trace4(int depth, int px, int py, int d){
	if(depth == 0) return;
	if(px == w+1 || py == h+1) return;
	int dx = min(depth, min(h + 1 - py, w + 1 - px));
	low1[px][py] += d;
	low1[px + dx][py + dx] -= d;
	Trace4(depth - dx, px + dx, py + dx, d);
}
 
 
static char _buffer[1024];
static int _currentChar = 0;
static int _charsNumber = 0;
 
static inline int _read() {
	if (_charsNumber < 0) {
		exit(1);
	}
	if (!_charsNumber || _currentChar == _charsNumber) {
		_charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), stdin);
		_currentChar = 0;
	}
	if (_charsNumber <= 0) {
		return -1;
	}
	return _buffer[_currentChar++];
}
 
static inline int _readInt() {
	int c, x, s;
	c = _read();
	while (c <= 32) c = _read();
	x = 0;
	s = 1;
	if (c == '-') {
		s = -1;
		c = _read();
	}
	while (c > 32) {
		x *= 10;
		x += c - '0';
		c = _read();
	}
	if (s < 0) x = -x;
	return x;
}
  
int main(){
	w = _readInt();
	h = _readInt();
	n = _readInt();
	dx1 = (lint**) calloc(w+2, sizeof(lint*));
	low1 = (lint**) calloc(w+2, sizeof(lint*));
	low2 = (lint**) calloc(w+2, sizeof(lint*));
	low3 = (lint*) calloc(w+2, sizeof(lint));
	low4 = (lint*) calloc(h+2, sizeof(lint));
	for(int i=0; i<=w+1; i++){
		dx1[i] = (lint*)calloc(h+2, sizeof(lint));
		low1[i] = (lint*)calloc(h+2, sizeof(lint));
		low2[i] = (lint*)calloc(h+2, sizeof(lint));
	}
	for(int i=0; i<n; i++){
		int x, y, a, b;
		x = _readInt();
		y = _readInt();
		a = _readInt();
		b = _readInt();
		int rad = a / b;
		int radx = max(w-x,x) + 1;
		int rady = max(h-y,y) + 1;
		int mrad = max(radx, rady);
		lint tmp1 = a % b + 1ll * max(0,rad - mrad) * b;
		int tmp2 = min(rad, mrad);
		dx1[max(1,x-rad)][max(1,y-rad)] += tmp1;
		dx1[max(1,x-rad)][min(h+1,y+rad+1)] -= tmp1;
		dx1[min(w+1,x+rad+1)][max(1,y-rad)] -= tmp1;
		dx1[min(w+1,x+rad+1)][min(h+1,y+rad+1)] += tmp1;
		Trace1(tmp2, x, y, b);
		Trace2(tmp2, x, y+1, -b);
		Trace3(tmp2, x+1, y, -b);
		Trace4(tmp2, x+1, y+1, b);
	}
	for(int i=1; i<=w; i++){
		for(int j=1; j<=h; j++){
			low1[i][j] += low1[i-1][j-1];
			low2[i][j] += low2[i-1][j+1];
		}
	}
	for(int i=1; i<=w; i++){
		low3[i] += low3[i-1];
		dx1[i][1] += low3[i];
	}
	for(int i=1; i<=h; i++){
		low4[i] += low4[i-1];
		dx1[1][i] += low4[i];
	}
	for(int i=1; i<=w; i++){
		for(int j=1; j<=h; j++){
			dx1[i][j] += dx1[i][j-1] + dx1[i-1][j] - dx1[i-1][j-1];
			dx1[i][j] += low1[i][j] + low2[i][j];
		}
	}
	for(int i=1; i<=w; i++){
		for(int j=1; j<=h; j++){
			dx1[i][j] = dx1[i-1][j] + dx1[i][j-1] - dx1[i-1][j-1] + dx1[i][j];
		}
	}
	int q = _readInt();
	while(q--){
		int sx = _readInt();
		int sy = _readInt();
		int ex = _readInt();
		int ey = _readInt();
		lint res = dx1[ex][ey] - dx1[sx-1][ey] - dx1[ex][sy-1] + dx1[sx-1][sy-1];
		res += (ex - sx + 1) * (ey - sy + 1) / 2;
		res /= 1ll * (ex - sx + 1) * (ey - sy + 1);
		printf("%lld\n",res);
	}
}

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 453 ms 313452 KB Output is correct
2 Correct 42 ms 4588 KB Output is correct
3 Correct 34 ms 3820 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 456 ms 313708 KB Output is correct
2 Correct 38 ms 4588 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 59756 KB Output is correct
2 Correct 37 ms 4332 KB Output is correct

Subtask #4
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 60680 KB Output is correct
2 Correct 37 ms 4588 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 319452 KB Output is correct
2 Correct 40 ms 5356 KB Output is correct

Subtask #6
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 131632 KB Output is correct
2 Correct 37 ms 4588 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 65152 KB Output is correct
2 Correct 39 ms 4972 KB Output is correct

Subtask #8
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 92396 KB Output is correct
2 Correct 38 ms 4480 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 653 ms 323224 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 667 ms 323516 KB Output is correct

Subtask #11
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 69108 KB Output is correct
2 Correct 224 ms 69100 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 232 ms 68844 KB Output is correct
2 Correct 224 ms 68844 KB Output is correct

Subtask #13
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 70508 KB Output is correct
2 Correct 241 ms 69672 KB Output is correct

Subtask #14
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 236 ms 69144 KB Output is correct
2 Correct 248 ms 108140 KB Output is correct