Submission #776761

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
776761	2023-07-08T08:43:21 Z	vjudge1	NLO (COCI18_nlo)	C++17	0 / 110	186 ms	15344 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=100000000;
				int mx=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++;
					if(it1==st[yy].end() || (*it).se>=r){
						mx=max(mx,(*it).se);
						st[yy].erase(it);
						break;
					}
					//~ cout<<(*it1).fi<<" ()() "<<(*it).se<<endl;
					if((*it1).fi<=r && (*it1).fi-(*it).se>=0)add-=(*it1).fi-(*it).se;
					mx=max(mx,(*it).se);
					st[yy].erase(it);
					it=it1;
				}
				//~ cout<<mn<<" ()() "<<mx<<endl;
				if(mn==100000000 && mx==0){
					mn=l;
					mx=r;
					add-=r-l+1;
				}
				
				if(mn>l){add-=mn-l;mn=l;}
				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;
		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=100000000;
				int mx=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++;
					if(it1==st[yy].end() || (*it).se>=r){
						mx=max(mx,(*it).se);
						st[yy].erase(it);
						break;
					}
					if((*it1).fi<=r && (*it1).fi-(*it).se>=0)add-=(*it1).fi-(*it).se;
					mx=max(mx,(*it).se);
					st[yy].erase(it);
					it=it1;
				}
				//~ cout<<mn<<" [][] "<<mx<<endl;
				if(mn==100000000 && mx==0){
					mn=l;
					mx=r;
					add-=r-l+1;
				}
				if(mn>l){add-=mn-l;mn=l;}
				if(r>mx){add-=r-mx;mx=r;}
				
				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

0 / 110.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	3 ms	5076 KB	Output isn't correct
2	Incorrect	4 ms	5076 KB	Output isn't correct
3	Incorrect	4 ms	5716 KB	Output isn't correct
4	Incorrect	13 ms	5560 KB	Output isn't correct
5	Incorrect	16 ms	7852 KB	Output isn't correct
6	Incorrect	70 ms	8088 KB	Output isn't correct
7	Incorrect	38 ms	11464 KB	Output isn't correct
8	Incorrect	138 ms	11368 KB	Output isn't correct
9	Incorrect	63 ms	15344 KB	Output isn't correct
10	Incorrect	186 ms	12032 KB	Output isn't correct