oj.uz

답안 #92218

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
92218 2019-01-02T04:39:38 Z IvanC NLO (COCI18_nlo) C++17
110 / 110
 522 ms 476 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef tuple<int,int,int> trinca;

int N,M,K,lastx;
ll somatorio;
set<int> pq;
vector<trinca> circulos,sweep;

void build_sweep(int X){

	lastx = 0;
	sweep.clear();
	pq.clear();

	for(int i = 0;i<K;i++){
		int x = get<0>(circulos[i]), y = get<1>(circulos[i]),r = get<2>(circulos[i]);
		if(abs(X - x) > r) continue;
		int sobra = (int)floor(sqrt(1LL*r*r - 1LL*(X-x)*(X-x)));
		int y0 = max(1,y - sobra), y1 = min(M,y + sobra) + 1;
		sweep.push_back(make_tuple(y0,1,i+1));
		sweep.push_back(make_tuple(y1,-1,i+1));
	}

	sort(sweep.begin(),sweep.end());

}

void sweepline(){

	somatorio += 1LL*M*K;

	for(int i = 0;i<sweep.size();i++){
		int y = get<0>(sweep[i]), delta = get<1>(sweep[i]),idx = get<2>(sweep[i]);
		if(!pq.empty()) somatorio += 1LL*(y - lastx)*(*pq.begin());
		lastx = y;
		if(delta == 1) pq.insert(-idx);
		else pq.erase(-idx);
	}

}

int main(){

	scanf("%d %d",&N,&M);
	scanf("%d",&K);
	for(int i = 0;i<K;i++){
		int x,y,r;
		scanf("%d %d %d",&x,&y,&r);
		circulos.push_back(make_tuple(x,y,r));
	}

	for(int i = 1;i<=N;i++){
		build_sweep(i);
		sweepline();
	}

	printf("%lld\n",somatorio);

	return 0;

}

Compilation message

nlo.cpp: In function 'void sweepline()':
nlo.cpp:35:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0;i<sweep.size();i++){
                ~^~~~~~~~~~~~~
nlo.cpp: In function 'int main()':
nlo.cpp:47:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&N,&M);
  ~~~~~^~~~~~~~~~~~~~~
nlo.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&K);
  ~~~~~^~~~~~~~~
nlo.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&x,&y,&r);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
110.0 / 110.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 12 ms 256 KB Output is correct
3 Correct 7 ms 256 KB Output is correct
4 Correct 39 ms 256 KB Output is correct
5 Correct 27 ms 376 KB Output is correct
6 Correct 210 ms 476 KB Output is correct
7 Correct 81 ms 364 KB Output is correct
8 Correct 396 ms 400 KB Output is correct
9 Correct 147 ms 376 KB Output is correct
10 Correct 522 ms 380 KB Output is correct