Submission #224510

#	Time	Username	Problem	Language	Result	Execution time	Memory
224510		kshitij_sodani	Pilot (NOI19_pilot)	C++17	89 / 100	1092 ms	55144 KiB

pilot

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
llo par[1000001];
llo ss[1000001];
llo find(llo no){
	if(par[no]==no){
		return no;
	}
	par[no]=find(par[no]);
	return par[no];
}
llo calc(llo no){
	return (ss[no]*(ss[no]+1))/2;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	llo n,q;
	cin>>n>>q;
	for(llo i=0;i<n;i++){
		par[i]=i;
		ss[i]=0;
	}
	vector<pair<llo,llo>> tt;
	llo aa;
	for(llo i=0;i<n;i++){
		cin>>aa;
		tt.pb({aa,i});
	}
	llo ans2[q];
	vector<pair<llo,llo>> it;
	for(llo i=0;i<q;i++){
		cin>>aa;
		it.pb({aa,i});
	}
	sort(tt.begin(),tt.end());
	sort(it.begin(),it.end());
	llo ind=0;
	llo ans=0;
	for(auto nn:it){
		while(ind<n){
			if(tt[ind].a<=nn.a){
				ss[tt[ind].b]=1;
				ans+=calc(tt[ind].b);
				if(tt[ind].b>0){
					if(ss[tt[ind].b-1]>0){
						llo x=find(tt[ind].b-1);
						ans-=calc(x);
						ans-=calc(tt[ind].b);
						ss[x]+=ss[tt[ind].b];
						par[tt[ind].b]=x;
						ans+=calc(x);
					}
					
				}
				if(tt[ind].b<n-1){
					if(ss[tt[ind].b+1]>0){
						llo y=find(tt[ind].b);
						llo x=find(tt[ind].b+1);
						if(ss[x]>ss[y]){
							ans-=calc(x);
							ans-=calc(y);
							ss[x]+=ss[y];
							par[y]=x;
							ans+=calc(x);
						}
						else{
							ans-=calc(x);
							ans-=calc(y);
							ss[y]+=ss[x];
							par[x]=y;
							ans+=calc(y);
						}

					}
				}
				ind+=1;
			}
			else{
				break;
			}
		}
	//	cout<<nn.b<<" "<<ans<<endl;
		ans2[nn.b]=ans;
	}
	for(llo i=0;i<q;i++){
		cout<<ans2[i]<<endl;
	}




	return 0;
}

• Subtask 1: 3 / 3
• Subtask 2: 10 / 10
• Subtask 3: 12 / 12
• Subtask 4: 15 / 15
• Subtask 5: 5 / 5
• Subtask 6: 9 / 9
• Subtask 7: 14 / 14
• Subtask 8: 10 / 10
• Subtask 9: 11 / 11
• Subtask 10: 0 / 11