oj.uz

Submission #366373

# Submission time Handle Problem Language Result Execution time Memory
366373 2021-02-14T05:52:20 Z kshitij_sodani Planine (COCI21_planine) C++14
110 / 110
 1097 ms 102352 KB 
//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'


llo n,aa;
llo xx[1000001];
llo yy[1000001];
vector<pair<llo,llo>> ss;
set<pair<llo,llo>> cur;
set<pair<llo,llo>> cur2;
llo ap[1000001];
llo bp[1000001];
bool clock(pair<llo,llo> aa,pair<llo,llo> bb,pair<llo,llo> cc){
	return aa.a*(bb.b-cc.b)+bb.a*(cc.b-aa.b)+cc.a*(aa.b-bb.b)<0;

}
bool clock2(pair<llo,llo> aa,pair<llo,llo> bb,pair<llo,llo> cc){
	return aa.a*(bb.b-cc.b)+bb.a*(cc.b-aa.b)+cc.a*(aa.b-bb.b)<=0;

}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>aa;
	for(llo i=0;i<n;i++){
		cin>>xx[i]>>yy[i];
	}

	vector<pair<pair<llo,llo>,llo>> sss;
	for(llo i=1;i<n;i+=2){	
		while(sss.size()>=2){
			if(!clock(sss[sss.size()-2].a,sss.back().a,{xx[i],yy[i]})){
				sss.pop_back();
				continue;
			}
			else{
				break;
			}
		}
		sss.pb({{xx[i],yy[i]},i});
		llo ind=0;
		/*llo low=0;
		llo high=sss.size()-1;*/
		/*while(low<high-1){
			llo mid=(low+high)/2;
			if(clock({xx[i+1],yy[i+1]},sss[ind-(1<<j)+1].a,sss[ind-(1<<j)].a)){
				ind-=(1<<j);
			}
		}*/
		for(llo j=19;j>=0;j--){
			if(ind+(1<<j)<sss.size()){
				if(clock2(sss[ind+(1<<j)-1].a,sss[ind+(1<<j)].a,{xx[i+1],yy[i+1]})){
					ind+=(1<<j);
				}
			}
		}
		ap[i+1]=sss[ind].b;
	}
	sss.clear();
	for(llo i=n-2;i>=0;i-=2){	
		while(sss.size()>=2){
			if(!clock({xx[i],yy[i]},sss.back().a,sss[sss.size()-2].a)){
				sss.pop_back();
				continue;
			}
			else{
				break;
			}
		}
		sss.pb({{xx[i],yy[i]},i});
		llo ind=0;
		/*llo low=0;
		llo high=sss.size()-1;*/
		/*while(low<high-1){
			llo mid=(low+high)/2;
			if(clock({xx[i+1],yy[i+1]},sss[ind-(1<<j)+1].a,sss[ind-(1<<j)].a)){
				ind-=(1<<j);
			}
		}*/
		for(llo j=19;j>=0;j--){
			if(ind+(1<<j)<sss.size()){
				if(!clock({xx[i-1],yy[i-1]},sss[ind+(1<<j)-1].a,sss[ind+(1<<j)].a)){
					ind+=(1<<j);
				}
			}
		}
		bp[i-1]=sss[ind].b;
	}
	//return 0;
	for(llo i=2;i<n-1;i+=2){

	/*	double ac=((double)aa-yy[i]);
		ac/=((double)(yy[i+1]-yy[i]));
		ac*=((double)(xx[i+1]-xx[i]));*/
		pair<llo,llo> acc2={(xx[i+1]-xx[i])*(aa-yy[i]),(yy[i+1]-yy[i])};
		acc2.a+=xx[i]*acc2.b;
		//ac+=xx[i];

		pair<llo,llo> bcc2={(xx[i-1]-xx[i])*(aa-yy[i]),(yy[i-1]-yy[i])};
		bcc2.a+=xx[i]*bcc2.b;
		//ac+=xx[i];
	/*	double bc=((double)aa-yy[i]);
		bc/=((double)(yy[i-1]-yy[i]));
		bc*=((double)(xx[i-1]-xx[i]));*/
		//bc+=xx[i];
		//cout<<setprecision(10)<<ac<<":"<<bc<<endl;
		
		/*ac*=1000000;
		bc*=1000000;
		llo acc=round(ac);
		llo bcc=round(bc);*/
		//if(n<=2000){
			for(llo j=ap[i];j<=ap[i];j+=2){
				//if(j<i){
				if(yy[j]==yy[i]){
					continue;
				}
				pair<llo,llo> ccc2={(xx[j]-xx[i])*(aa-yy[i]),(yy[j]-yy[i])};
				ccc2.a+=xx[i]*ccc2.b;
				if(j<i){
					if(bcc2.a*ccc2.b<ccc2.a*bcc2.b){
						bcc2=ccc2;

					}
				//	bcc=max(bcc,ccc);
				}
				//}
			}
			for(llo j=bp[i];j<=bp[i];j+=2){
				//if(j<i){
				if(yy[j]==yy[i]){
					continue;
				}
				pair<llo,llo> ccc2={(xx[j]-xx[i])*(aa-yy[i]),(yy[j]-yy[i])};
				ccc2.a+=xx[i]*ccc2.b;
					if(j>i){
						if(acc2.a*ccc2.b>ccc2.a*acc2.b){
							acc2=ccc2;

						}
						//acc=min(acc,ccc);
					}
					if(j<i){
						if(bcc2.a*ccc2.b<ccc2.a*bcc2.b){
							bcc2=ccc2;

						}
					//	bcc=max(bcc,ccc);
					}
				//}
			}
		//}
		long double ac=((long double)(acc2.a))/((long double)(acc2.b));
		long double bc=((long double)(bcc2.a))/((long double)(bcc2.b));
		ac*=1000000;
		bc*=1000000;
		llo acc=round(ac);
		llo bcc=round(bc);
		swap(acc,bcc);
		ss.pb({acc,bcc});
		//cout<<acc<<","<<bcc<<endl;

	}
	//return 0;
	for(auto j:ss){
		cur.insert(j);
		cur2.insert({j.b,j.a});
	}
//	sort(ss.begin(),ss.end(),cmp);
	llo ans=0;
	while(cur2.size()){
		ans++;
		pair<llo,llo> no=*(cur2.begin());
	//	cout<<no.a<<":"<<no.b<<endl;
		while(cur.size()){
			pair<llo,llo> no2=*(cur.begin());
		//	cout<<no2.a<<",,"<<no2.b<<endl;
			if(no2.a<=no.a){	
				cur.erase(no2);
				cur2.erase({no2.b,no2.a});
			}
			else{
				break;
			}
		}
		//break;
	}



	cout<<ans<<endl;




 
	return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:58:17: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |    if(ind+(1<<j)<sss.size()){
      |       ~~~~~~~~~~^~~~~~~~~~~
Main.cpp:88:17: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |    if(ind+(1<<j)<sss.size()){
      |       ~~~~~~~~~~^~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1388 KB Output is correct
2 Correct 7 ms 1388 KB Output is correct
3 Correct 7 ms 1388 KB Output is correct
4 Correct 59 ms 10600 KB Output is correct
5 Correct 65 ms 10600 KB Output is correct
6 Correct 67 ms 10600 KB Output is correct
7 Correct 609 ms 102112 KB Output is correct
8 Correct 659 ms 102204 KB Output is correct
9 Correct 681 ms 102352 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 620 KB Output is correct
2 Correct 2 ms 620 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 1 ms 364 KB Output is correct

Subtask #3
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1388 KB Output is correct
2 Correct 7 ms 1388 KB Output is correct
3 Correct 7 ms 1388 KB Output is correct
4 Correct 59 ms 10600 KB Output is correct
5 Correct 65 ms 10600 KB Output is correct
6 Correct 67 ms 10600 KB Output is correct
7 Correct 609 ms 102112 KB Output is correct
8 Correct 659 ms 102204 KB Output is correct
9 Correct 681 ms 102352 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 2 ms 620 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 2 ms 620 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 2 ms 620 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 652 ms 102276 KB Output is correct
18 Correct 640 ms 102096 KB Output is correct
19 Correct 64 ms 10600 KB Output is correct
20 Correct 639 ms 102104 KB Output is correct
21 Correct 65 ms 10600 KB Output is correct
22 Correct 790 ms 102096 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 677 ms 102216 KB Output is correct
25 Correct 64 ms 10600 KB Output is correct
26 Correct 1097 ms 102188 KB Output is correct
27 Correct 34 ms 5484 KB Output is correct