oj.uz

답안 #702455

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
702455 2023-02-24T06:00:16 Z chenyan NLO (COCI18_nlo) C++17
110 / 110
 974 ms 1924 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define pb push_back
#define N 200010
int ans,x[N],y[N],r[N],sq[N];
struct A{
	int l,r,w;
};
vector<A>v;
vector<int>u;
int a[1010],res;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,m,i,j,k;
	cin>>n>>m>>k;
	for(i=0;i<N;i++)sq[i]=i*i;
	for(i=1;i<=k;i++) cin>>x[i]>>y[i]>>r[i];
	for(j=1;j<=n;j++){
		vector<int>().swap(u);
		vector<A>().swap(v);
		for(i=1;i<=k;i++){
			int xx=r[i]*r[i]-(j-x[i])*(j-x[i]);
			if(xx<0)continue;
			int p=upper_bound(sq,sq+N,xx)-sq-1;
			v.pb({y[i]-p,y[i]+p+1,i});
			u.pb(v.back().l);
			u.pb(v.back().r);
		}
		sort(all(u)),u.resize(unique(all(u))-u.begin());
		for(auto&[l,r,w]:v){
			l=lower_bound(all(u),l)-u.begin();
			r=lower_bound(all(u),r)-u.begin();
		}
		sort(all(v),[](A u,A v){return u.l<v.l;});
		priority_queue<pii>pq;
		pq.push({0,1e9});
		int l=1,x;
		for(i=0,x=0;i<u.size();i++){
			ans+=(u[i]-l)*pq.top().ff;
			l=u[i];
			while(x<v.size()&&v[x].l==i)pq.push({v[x].w,v[x].r}),x++;
			while(pq.top().ss<=i)pq.pop();
		}
	}
	cout<<n*m*k-ans<<'\n';
}

Compilation message

nlo.cpp: In function 'int main()':
nlo.cpp:44:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for(i=0,x=0;i<u.size();i++){
      |               ~^~~~~~~~~
nlo.cpp:47:11: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<A>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |    while(x<v.size()&&v[x].l==i)pq.push({v[x].w,v[x].r}),x++;
      |          ~^~~~~~~~~

Subtask #1
110.0 / 110.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1876 KB Output is correct
2 Correct 15 ms 1924 KB Output is correct
3 Correct 10 ms 1876 KB Output is correct
4 Correct 71 ms 1920 KB Output is correct
5 Correct 49 ms 1876 KB Output is correct
6 Correct 378 ms 1904 KB Output is correct
7 Correct 132 ms 1896 KB Output is correct
8 Correct 741 ms 1920 KB Output is correct
9 Correct 246 ms 1896 KB Output is correct
10 Correct 974 ms 1912 KB Output is correct