Submission #461324

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
461324	2021-08-09T18:35:41 Z	grt	NLO (COCI18_nlo)	C++17	110 / 110	2605 ms	56388 KB

nlo

#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second
#define _ ios_base::sync_with_stdio(0); cin.tie(0);
//mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

using namespace std;

using ll = long long;
using pi = pair<int,int>;
using vi = vector<int>;

const int nax = 1e5 + 10;
int n, m, k;
set<tuple<int,int,int>>seg[nax];

int main() {
	cin >> n >> m >> k;
	ll ans = 0;
	for(int i = 0; i < k; ++i) {
		int x, y, r;
		cin >> x >> y >> r;
		ll sum = 0, sum2 = 0;
		for(int j = y - r; j <= y + r; ++j) {
			int low = 1, high = x, mid;
			while(low <= high) {
				mid = (low + high) / 2;
				if((ll)(mid - x) * (mid - x) + (ll)(j-y)*(j-y) <= (ll) r * r) {
					high = mid - 1;
				} else {
					low = mid + 1;
				}
			}
			int a = high + 1;
			int len = (x - a) * 2 + 1;
			sum2 += (ll)len * (i + 1);
			auto it = seg[j].lower_bound({a, -1, -1});
			auto it2 = it;
			while(it != seg[j].end()) {
				auto [lft, rght,t] = (*it);
				if(lft > a + len - 1) break;
				sum += (min(rght, a + len - 1) - lft + 1) * t;
				if(rght > a + len - 1) {
					seg[j].insert({a + len, rght, t});
				}
				it = next(it);
			}
			seg[j].erase(it2, it);
			it2 = seg[j].lower_bound({a, -1, -1});
			if(it2 != seg[j].begin()) {
				it2 = prev(it2);
				auto [lft, rght, t] = (*it2);
				if(rght >= a) {
					seg[j].erase(it2);
					if(lft < a) {
						seg[j].insert({lft, a - 1, t});
					}
					sum += (min(rght, (a + len - 1)) - a + 1) * t;
					if(rght > a + len - 1) {
						seg[j].insert({a + len, rght, t});
					}
				}
			}
			seg[j].insert({a, a + len - 1, i + 1});
		}
		//cout << sum2 << "\n";
		sum2 -= sum;
		ans += sum2;
	}
	ans = (ll)n * m * k - ans;
	cout << ans;
	
}

Subtask #1

110.0 / 110.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	5324 KB	Output is correct
2	Correct	17 ms	5508 KB	Output is correct
3	Correct	13 ms	6988 KB	Output is correct
4	Correct	85 ms	8796 KB	Output is correct
5	Correct	59 ms	17148 KB	Output is correct
6	Correct	880 ms	23620 KB	Output is correct
7	Correct	200 ms	32996 KB	Output is correct
8	Correct	1847 ms	54496 KB	Output is correct
9	Correct	453 ms	44308 KB	Output is correct
10	Correct	2605 ms	56388 KB	Output is correct