Submission #859096

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
859096	2023-10-09T17:00:07 Z	serifefedartar	NLO (COCI18_nlo)	C++17	99 / 110	3000 ms	3668 KB

nlo

#include <bits/stdc++.h>
using namespace std;
 
#define fast ios::sync_with_stdio(0);cin.tie(0);
#define s second
#define f first
typedef long long ll;
const ll MOD = 1e9 + 7;
const ll LOGN = 22; 
const ll MAXN = 1e5 + 5;

struct Circle {
	int x, y, r;
	void read() { cin >> y >> x >> r; }
	Circle() { }
	Circle(int _x, int _y, int _r) : x(_x), y(_y), r(_r) { }
};

vector<Circle> v;
int sg[4*MAXN], lazy[4*MAXN];
void push(int k, int a, int b) {
	if (lazy[k] != -1) {
		sg[k] = (b - a + 1) * lazy[k];
		if (a != b) {
			lazy[2*k] = lazy[k];
			lazy[2*k+1] = lazy[k];
		}
		lazy[k] = -1;
	}
}	

void update(int k, int a, int b, int q_l, int q_r, int v) {
	push(k, a, b);
	if (q_r < a || q_l > b)
		return ;
	if (q_l <= a && b <= q_r) {
		lazy[k] = v;
		push(k, a, b);
		return ;
	}
	update(2*k, a, (a+b)/2, q_l, q_r, v);
	update(2*k+1, (a+b)/2+1, b, q_l, q_r, v);
	sg[k] = sg[2*k] + sg[2*k+1];
}

int query(int k, int a, int b, int q_l, int q_r) {
	push(k, a, b);
	if (b < q_l || a > q_r)
		return 0;
	if (q_l <= a && b <= q_r)
		return sg[k];
	return query(2*k, a, (a+b)/2, q_l, q_r) + query(2*k+1, (a+b)/2 + 1, b, q_l, q_r);
}

int main() {
	fast
	memset(lazy, -1, sizeof(lazy));
	memset(sg, 1, sizeof(sg));
	int N, M, K;
	cin >> N >> M >> K;

	v = vector<Circle>(K);
	for (int i = 0; i < K; i++)
		v[i].read();

	ll ans = 0;
	for (int i = 1; i <= N; i++) {
		update(1, 1, M, 1, M, 1);
		for (int circ = K-1; circ >= 0; circ--) {
			int hei = abs(v[circ].y - i);
			if (hei > v[circ].r)
				continue;
			hei *= hei;

			int sqr = sqrt(v[circ].r * v[circ].r - hei);

			ans += (K-1-circ) * query(1, 1, M, v[circ].x - sqr, v[circ].x + sqr);
			update(1, 1, M, v[circ].x - sqr, v[circ].x + sqr, 0);
		}
		ans += K * query(1, 1, M, 1, M);
	}
	cout << ans << "\n";
}

Subtask #1

99.0 / 110.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	3420 KB	Output is correct
2	Correct	22 ms	3592 KB	Output is correct
3	Correct	20 ms	3420 KB	Output is correct
4	Correct	168 ms	3420 KB	Output is correct
5	Correct	162 ms	3560 KB	Output is correct
6	Correct	1231 ms	3568 KB	Output is correct
7	Correct	501 ms	3668 KB	Output is correct
8	Correct	2636 ms	3564 KB	Output is correct
9	Correct	928 ms	3564 KB	Output is correct
10	Execution timed out	3039 ms	3416 KB	Time limit exceeded