답안 #776715

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
776715 2023-07-08T07:45:55 Z vjudge1 NLO (COCI18_nlo) C++17
0 / 110
197 ms 14564 KB
#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];
		//~ r[i]++;
		int rr=r[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;
				st[yy].insert({l,r});
				//~ cout<<yy<<" DEBUGDEBUG \n";
			}
			else{
				auto it=st[yy].upper_bound({l,1000000});
				int mn=0;
				int mx=0;
				if(it==st[yy].begin()){
					if((*it).fi<=r){
						mn=l;
						add-=(*it).fi-l;
					}
					else{mn=l;mx=r;add-=(r-l+1);}
				}
				else{
					it--;
					if((*it).se<l){
						it++;
						if(it!=st[yy].end() && (*it).fi<=r){
							mn=l;
							add-=(*it).fi-l;
						}
						else{mn=l;mx=r;add-=(r-l+1);}
					}
					else mn=(*it).fi;
				}
				if(it!=st[yy].end())mx=max(mx,(*it).se);
				//~ cout<<add<<" AA "<<yy<<" AA "<<rr<<endl;
				while(it!=st[yy].end()){
					if((*it).fi>r)break;
					auto it1=it;
					it1++;
					if(it1==st[yy].end() || (*it).se>=r){
						mx=max(mx,(*it).se);
						st[yy].erase(it);
						break;
					}
					add-=min(r,(*it1).fi)-max(l,(*it).se);
					mx=max(mx,(*it).se);
					st[yy].erase(it);
					it=it1;
				}
				if(r>=mx){add-=r-mx;mx=r;}
				st[yy].insert({mn,mx});
			}
			//~ cout<<add<<" ()() "<<yy<<" ()() "<<rr<<endl;
			yy--;
			rr--;
		}
		//~ cout<<add<<" tmp_add \n";
		////////////////////////////////////////////////////////////////
		////////////////////////////////////////////////////////////////
		////////////////////////////////////////////////////////////////
		yy=x[i]+1;
		rr=r[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});
			}
			else{
				auto it=st[yy].upper_bound({l,1000000});
				int mn=0;
				int mx=0;
				if(it==st[yy].begin()){
					if((*it).fi<=r){
						mn=l;
						add-=(*it).fi-l;
					}
				}
				else{
					it--;
					if((*it).se<l){
						it++;
						if(it!=st[yy].end() && (*it).fi<=r){
							mn=l;
							add-=(*it).fi-l;
						}
					}
					else mn=(*it).fi;
				}
				if(it!=st[yy].end())mx=max(mx,(*it).se);
				while(it!=st[yy].end()){
					if((*it).fi>r)break;
					auto it1=it;
					it1++;
					if(it1==st[yy].end() || (*it).se>=r){
						mx=max(mx,(*it).se);
						st[yy].erase(it);
						break;
					}
					add-=min(r,(*it1).fi)-max(l,(*it).se);
					mx=max(mx,(*it).se);
					st[yy].erase(it);
					it=it1;
				}
				if(r>=mx){add-=r-mx;mx=r;}
				st[yy].insert({mn,mx});
			}
			yy++;
			rr--;
		}
		cev+=add;
		//~ cout<<add<<endl;
	}
	printf("%lld",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]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 5076 KB Output isn't correct
2 Incorrect 4 ms 5084 KB Output isn't correct
3 Incorrect 4 ms 5716 KB Output isn't correct
4 Incorrect 15 ms 5844 KB Output isn't correct
5 Incorrect 16 ms 7672 KB Output isn't correct
6 Incorrect 75 ms 8080 KB Output isn't correct
7 Incorrect 42 ms 13844 KB Output isn't correct
8 Incorrect 167 ms 11292 KB Output isn't correct
9 Incorrect 66 ms 14564 KB Output isn't correct
10 Incorrect 197 ms 12140 KB Output isn't correct