Submission #92218

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
92218	2019-01-02T04:39:38 Z	IvanC	NLO (COCI18_nlo)	C++17	110 / 110	522 ms	476 KB

nlo

#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

#	Verdict	Execution time	Memory	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