Submission #366332

#	Time	Username	Problem	Language	Result	Execution time	Memory
366332		kshitij_sodani	Po (COCI21_po)	C++14	0 / 70	25 ms	3816 KiB

Main

//#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;
llo it[100001];
llo par[100001];
llo vis[100001];
llo find(llo no){
	if(par[no]==no){
		return no;
	}

	par[no]=find(par[no]);
	return par[no];
}
llo cur=0;
void merge(llo aa,llo bb){
	if(vis[aa]==0 or vis[bb]==0){
		return;
	}
	llo x=find(aa);
	llo y=find(bb);
	if(x!=y){
		par[x]=y;
		cur--;
	}
}
llo ans=0;
int tree[4*100001];
void build(int no,int l,int r){
	if(l==r){
		tree[no]=it[l];
	}
	else{
		int mid=(l+r)/2;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
		tree[no]=min(tree[no*2+1],tree[no*2+2]);
	}
}
void solve(int l,int r){
	ans++;

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

	map<llo,vector<llo>> ss;
	vector<pair<llo,llo>> tt;

	for(llo i=0;i<n;i++){
		cin>>it[i];
	//	ss[-it[i]].pb(i);
		tt.pb({it[i],i});
	}
	sort(tt.begin(),tt.end());
	//llo ans=0;
	solve(0,n-1);
	/*while(tt.size()){
		int no=tt.back().a;
		vector<int> cc;
		while(tt.size()){
			if(tt.back().a==no){
				cc.pb(tt.back().b);
				tt.pop_back();
			}
			else{
				break;
			}
		}
		set<llo> kk;
		for(auto i:cc){
			cur++;
			vis[i]=1;
			if(i>0){
				merge(i,i-1);
			}
			if(i<n-1){
				merge(i,i+1);
			}
		}
		for(auto i:cc){
			kk.insert(find(i));
		}
		//for(int i=0;i<n;i++){
		//	find(i);
			//cout<<par[i]<<",";
		//}
		//cout<<endl;
		ans+=kk.size();
	}*/
/*	llo ans=0;
	for(auto j:ss){
		set<llo> kk;
		for(auto i:j.b){
			cur++;
			vis[i]=1;
			if(i>0){
				merge(i,i-1);
			}
			if(i<n-1){
				merge(i,i+1);
			}
		}
		for(auto i:j.b){
			kk.insert(find(i));
		}
		for(int i=0;i<n;i++){
			find(i);
			cout<<par[i]<<",";
		}
		cout<<endl;
		ans+=kk.size();
	}
*/
	cout<<ans<<endl;






 
	return 0;
}

• Subtask 1: 0 / 70