Submission #776703

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
776703	2023-07-08T07:30:39 Z	vjudge1	NLO (COCI18_nlo)	C++17	110 / 110	2873 ms	5496 KB

nlo

#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 100005
#define LOGN 17
#define L(node) node * 2
#define R(node) node * 2 + 1 
#define int long long

int tree[4 * N], lazy[4 * N];

inline void push(int node, int l, int r){
	if (lazy[node] == -1) return;
	tree[node] = lazy[node] * (r - l + 1);
	if (l != r){
		lazy[L(node)] = lazy[node];
		lazy[R(node)] = lazy[node];
	} 
	lazy[node] = -1;
}

inline void update(int node, int l, int r, int sl, int sr, int val){
	push(node, l, r);
	if (l > sr || r < sl || r < l) return;

	if (l >= sl && r <= sr){
		lazy[node] = val;
		push(node, l, r);
		return;
	}
	int mid = (l + r) / 2;
	update(L(node), l, mid, sl, sr, val);
	update(R(node), mid + 1, r, sl, sr, val);
	tree[node] = tree[L(node)] + tree[R(node)];
}

inline int query(int node, int l, int r, int sl, int sr){
	push(node, l, r);
	if (l > r || l > sr || r < sl) return 0;
	if (l >= sl && r <= sr) return tree[node];

	int mid = (l + r) / 2;
	return query(L(node), l, mid, sl, sr) + query(R(node), mid + 1, r, sl, sr);
}

inline int sq(int x){
	int ans = 0;
	for (int i = LOGN; i >= 0; i--){
		int tmp = ans + (1<<i);
		if (tmp * tmp <= x) ans = tmp;
	}
	return ans;
}

int32_t main(){
	#ifndef ONLINE_JUDGE
	//fileio();
	#endif
	fastio();

	memset(lazy, -1, sizeof(lazy));

	int n, m;
	cin>>n>>m;
	int k;
	cin>>k;
	vector<array<int, 4>> v;
	for (int i = 1; i <= k; i++){
		int x, y, r;
		cin>>x>>y>>r;
		v.pb({x, y, r, i});
	}
	reverse(v.begin(), v.end());

	int res = 0;
	for (int i = 1; i <= n; i++){
		update(1, 1, m, 1, m, 1);
		for (auto j : v){
			int x = j[0], y = j[1], r = j[2], timee = j[3];
			if ((x - i) * (x - i) > r * r) 
			{
				continue;
			}
			int a = (x - i) * (x - i);
			int b = r * r;
			int t = sq(b - a);
			int k = query(1, 1, m, y - t, y + t);
			res += k * timee;
			update(1, 1, m, y - t, y + t, 0);
		}
	}

	cout<<n * m * k - res<<endl;

	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

Subtask #1

110.0 / 110.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	3412 KB	Output is correct
2	Correct	19 ms	3460 KB	Output is correct
3	Correct	17 ms	3500 KB	Output is correct
4	Correct	137 ms	3664 KB	Output is correct
5	Correct	133 ms	4484 KB	Output is correct
6	Correct	988 ms	4476 KB	Output is correct
7	Correct	405 ms	5396 KB	Output is correct
8	Correct	2115 ms	5484 KB	Output is correct
9	Correct	789 ms	5496 KB	Output is correct
10	Correct	2873 ms	5480 KB	Output is correct