답안 #776966

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
776966	2023-07-08T12:36:50 Z	blacktulip	NLO (COCI18_nlo)	C++17	110 / 110	201 ms	15352 KB

nlo

#include <bits/stdc++.h>

using namespace std;

typedef long long lo; 

#define fi first
#define se second
#define int long long
#define endl "\n"
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)

const lo inf = 1000000000;
const lo li = 100005;
const lo mod = 1000000007;

int n,m,a[li],k,flag,t,x[li],y[li],r[li];
int cev;
string s;
vector<int> v;
set<pair<int,int>> st[li];

int32_t main(void){
	scanf("%lld %lld",&n,&m);
	scanf("%lld",&k);
	for(int i=1;i<=k;i++){
		scanf("%lld %lld %lld",&x[i],&y[i],&r[i]);
	}
	int add=n*m;
	cev=0;
	for(int i=k;i>=1;i--){
		int yy=x[i];
		while(yy>=1){
			int at=r[i]*r[i]-((yy-x[i])*(yy-x[i]));
			if(at<0)break;
			int kat=sqrt(at);
			int l=y[i]-kat;
			int r=y[i]+kat;
			if(st[yy].empty()){
				add-=r-l+1;
				//~ cout<<yy<<" () AA "<<l<<" AA "<<r<<endl;
				st[yy].insert({l,r});
				yy--;
				continue;
				//~ cout<<yy<<" DEBUGDEBUG \n";
			}
			else{
				auto it=st[yy].begin();
				int mn=l;
				int mx=r;
				int say=0;
				while(it!=st[yy].end()){
					if((*it).fi>r)break;
					if((*it).se<l){it++;continue;}
					mn=min(mn,(*it).fi);
					auto it1=it;
					it1++;
					say+=min(r,(*it).se)-max(l,(*it).fi)+1;
					mx=max(mx,(*it).se);
					st[yy].erase(it);
					it=it1;
				}
				add-=r-l+1-say;
				st[yy].insert({mn,mx});
			}
			//~ cout<<add<<" ()() "<<yy<<" ()() "<<rr<<endl;
			yy--;
			//~ rr--;
		}
		//~ cout<<add<<" tmp_add \n";
		////////////////////////////////////////////////////////////////
		////////////////////////////////////////////////////////////////
		////////////////////////////////////////////////////////////////
		yy=x[i]+1;
		while(yy<=n){
			int at=r[i]*r[i]-((yy-x[i])*(yy-x[i]));
			if(at<0)break;
			int kat=sqrt(at);
			int l=y[i]-kat;
			int r=y[i]+kat;
			if(st[yy].empty()){
				add-=r-l+1;
				st[yy].insert({l,r});
				yy++;
				continue;
			}
			else{
				auto it=st[yy].begin();
				int mn=l;
				int mx=r;
				int say=0;
				while(it!=st[yy].end()){
					if((*it).fi>r)break;
					if((*it).se<l){it++;continue;}
					mn=min(mn,(*it).fi);
					auto it1=it;
					it1++;
					say+=min(r,(*it).se)-max(l,(*it).fi)+1;
					mx=max(mx,(*it).se);
					st[yy].erase(it);
					it=it1;
				}
				add-=r-l+1-say;
				st[yy].insert({mn,mx});
			}
			yy++;
			//~ rr--;
		}
		cev+=add;
		//~ cout<<add<<endl;
	}
	printf("%lld\n",cev);
	return 0;
}

Compilation message

nlo.cpp: In function 'int32_t main()':
nlo.cpp:28:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |  scanf("%lld %lld",&n,&m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~
nlo.cpp:29:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   29 |  scanf("%lld",&k);
      |  ~~~~~^~~~~~~~~~~
nlo.cpp:31:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |   scanf("%lld %lld %lld",&x[i],&y[i],&r[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

110.0 / 110.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	5076 KB	Output is correct
2	Correct	4 ms	5004 KB	Output is correct
3	Correct	5 ms	5648 KB	Output is correct
4	Correct	13 ms	5460 KB	Output is correct
5	Correct	20 ms	7820 KB	Output is correct
6	Correct	80 ms	8068 KB	Output is correct
7	Correct	45 ms	11468 KB	Output is correct
8	Correct	147 ms	11368 KB	Output is correct
9	Correct	72 ms	15352 KB	Output is correct
10	Correct	201 ms	12044 KB	Output is correct