Submission #776754

# Submission time Handle Problem Language Result Execution time Memory
776754 2023-07-08T08:35:03 Z vjudge1 NLO (COCI18_nlo) C++17
0 / 110
485 ms 44844 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;
				//~ 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(min(r,(*it1).fi)-max(l,(*it).se)>=0)add-=min(r,(*it1).fi)-max(l,(*it).se);
					mx=max(mx,(*it).se);
					st[yy].erase(it);
					it=it1;
				}
				if(mn==100000000 && mx==0){
					mn=l;
					mx=r;
					add-=r-l+1;
				}
				cout<<mn<<" ()() "<<mx<<endl;
				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;
		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});
				yy++;
				continue;
			}
			else{
				auto it=st[yy].begin();
				int mn=0;
				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(min(r,(*it1).fi)-max(l,(*it).se)>=0)add-=min(r,(*it1).fi)-max(l,(*it).se);
					mx=max(mx,(*it).se);
					st[yy].erase(it);
					it=it1;
				}
				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;}
				//~ cout<<mn<<" ()() "<<mx<<endl;
				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]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5076 KB Output isn't correct
2 Incorrect 7 ms 5260 KB Output isn't correct
3 Incorrect 7 ms 5900 KB Output isn't correct
4 Incorrect 31 ms 7272 KB Output isn't correct
5 Incorrect 32 ms 8868 KB Output isn't correct
6 Incorrect 230 ms 20604 KB Output isn't correct
7 Incorrect 85 ms 15948 KB Output isn't correct
8 Incorrect 367 ms 35116 KB Output isn't correct
9 Incorrect 147 ms 22992 KB Output isn't correct
10 Incorrect 485 ms 44844 KB Output isn't correct