oj.uz

Submission #366358

# Submission time Handle Problem Language Result Execution time Memory
366358 2021-02-14T05:11:49 Z kshitij_sodani Planine (COCI21_planine) C++14
50 / 110
 568 ms 94488 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=sss.size()-1;
		/*llo low=0;
		llo high=sss.size()-1;*/
		/*while(low<high-1){
			int 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)>=0){
				if(clock2({xx[i+1],yy[i+1]},sss[ind-(1<<j)+1].a,sss[ind-(1<<j)].a)){
					ind-=(1<<j);
				}
			}
		}
		ap[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=i+1;j<n;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;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1260 KB Output is correct
2 Correct 6 ms 1260 KB Output is correct
3 Correct 6 ms 1260 KB Output is correct
4 Correct 50 ms 9704 KB Output is correct
5 Correct 55 ms 9704 KB Output is correct
6 Correct 56 ms 9832 KB Output is correct
7 Correct 530 ms 94368 KB Output is correct
8 Correct 540 ms 94240 KB Output is correct
9 Correct 568 ms 94488 KB Output is correct

Subtask #2
30.0 / 30.0

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

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1260 KB Output is correct
2 Correct 6 ms 1260 KB Output is correct
3 Correct 6 ms 1260 KB Output is correct
4 Correct 50 ms 9704 KB Output is correct
5 Correct 55 ms 9704 KB Output is correct
6 Correct 56 ms 9832 KB Output is correct
7 Correct 530 ms 94368 KB Output is correct
8 Correct 540 ms 94240 KB Output is correct
9 Correct 568 ms 94488 KB Output is correct
10 Correct 3 ms 620 KB Output is correct
11 Correct 3 ms 620 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 3 ms 620 KB Output is correct
14 Correct 0 ms 364 KB Output is correct
15 Correct 3 ms 620 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 540 ms 94288 KB Output is correct
18 Incorrect 548 ms 94288 KB Output isn't correct
19 Halted 0 ms 0 KB -