#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
const int MAXN = 115;
const int MAXK = 1e5+10;
const int INF = 1e18+10;
void chmn(int &a, int b){ a = min(a, b); }
int n, m, k;
int x[MAXN], y[MAXN], r[MAXN];
struct seg {
int st[4*MAXK], laz[4*MAXK], ad[4*MAXK];
void bd(int id,int l,int r){
laz[id] = -INF; ad[id] = 0;
if(l==r) return;
bd(lf, l, md); bd(rg, md+1, r);
}
void bnc(int id, int l, int r){
if(laz[id] < 0){
if(ad[id] == 0) return;
if(laz[lf] < 0) ad[lf] += ad[id], st[lf] += (md-l+1) * ad[id];
else laz[lf] += ad[id], st[lf] = (md-l+1) * laz[lf], ad[lf] = 0;
if(laz[rg] < 0) ad[rg] += ad[id], st[rg] += (md-l+1) * ad[id];
else laz[rg] += ad[id], st[rg] = (r-md) * laz[rg], ad[rg] = 0;
laz[id] = -INF; ad[id] = 0;
} else {
laz[lf] = laz[id]; st[lf] = (md-l+1) * laz[id];
laz[rg] = laz[id]; st[rg] = (r-md) * laz[id];
laz[id] = -INF; ad[id] = 0;
}
}
int que(int id, int l, int r, int x, int y){
if(x<=l && r<=y) return st[id];
if(r<x || y<l) return 0;
bnc(id, l, r);
return que(lf,l,md,x,y) + que(rg,md+1,r,x,y);
}
int add(int id, int l, int r, int x, int y){
if(x<=l && r<=y){
if(laz[id] < 0) ad[id]++;
else laz[id]++;
return st[id] += (r-l+1);
}
if(r<x || y<l) return st[id];
bnc(id, l, r);
return st[id] = add(lf,l,md,x,y) + add(rg,md+1,r,x,y);
}
int upd(int id, int l, int r, int x, int y, int p){
if(x<=l && r<=y){
laz[id] = p; ad[id] = 0;
return st[id] = (r-l+1) * p;
}
if(r<x || y<l) return st[id];
bnc(id, l, r);
return st[id] = upd(lf,l,md,x,y,p) + upd(rg,md+1,r,x,y,p);
}
} A;
signed main(){
// ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
cin >> k;
for(int i=1; i<=k; i++) cin >> x[i]>> y[i] >> r[i];
int ans = 0;
A.bd(1,1,n);
for(int i=1; i<=n; i++){
A.upd(1,1,n,1,n,0);
// cout << i << " i\n";
for(int j=1; j<=k; j++){
A.add(1,1,n,1,n);
int te = r[j]*r[j] - (x[j]-i)*(x[j]-i);
if(te<0) continue;
int le = max(1ll, -(int)sqrt(te) + y[j]);
int ri = min(n, (int)sqrt(te) + y[j]);
A.upd(1,1,n,le,ri,0);
// cout << j << ' ' << le << ' ' << ri << " leri\n";
// cout << j << " j\n";
// for(int p=1; p<=n; p++) cout << A.que(1,1,n,p,p) << ' ';
// cout << "xx\n";
}
ans += A.que(1,1,n,1,n);
// cout << i << ' ' << A.que(1,1,n,1,n) << " pp\n";
// for(int p=1; p<=n; p++) cout << A.que(1,1,n,p,p) << ' ';
// cout << "xx\n";
}
cout << ans << '\n';
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
2 ms |
4444 KB |
Output isn't correct |
| 2 |
Incorrect |
7 ms |
4568 KB |
Output isn't correct |
| 3 |
Incorrect |
8 ms |
6652 KB |
Output isn't correct |
| 4 |
Incorrect |
20 ms |
6724 KB |
Output isn't correct |
| 5 |
Incorrect |
10 ms |
8796 KB |
Output isn't correct |
| 6 |
Incorrect |
353 ms |
8540 KB |
Output isn't correct |
| 7 |
Incorrect |
98 ms |
8796 KB |
Output isn't correct |
| 8 |
Incorrect |
604 ms |
8796 KB |
Output isn't correct |
| 9 |
Incorrect |
269 ms |
8796 KB |
Output isn't correct |
| 10 |
Incorrect |
921 ms |
8796 KB |
Output isn't correct |
