Submission #224557

#	Time	Username	Problem	Language	Result	Execution time	Memory
224557		kshitij_sodani	Pilot (NOI19_pilot)	C++17	89 / 100	1096 ms	51824 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;
int par[1000001];
int ss[1000001];
int find(int no){

	if(par[no]==no){
		return no;
	}
	par[no]=find(par[no]);
	return par[no];
}
llo rec[1000001];
llo calc(int no){
	return rec[ss[no]];
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n,q;
	cin>>n>>q;

	for(int i=0;i<n;i++){
		par[i]=i;
		ss[i]=0;
	}
	llo su=0;
	for(llo i=0;i<n+1;i++){
		rec[i]=su;
		su+=(i+1);
	}
	pair<int,int> tt[n];
	int aa;

	for(int i=0;i<n;i++){
		cin>>aa;
		tt[i]={aa,i};
	}
	llo ans2[q];
	pair<int,int> it[q];
	for(int i=0;i<q;i++){
		cin>>aa;

		it[i]={aa,i};
	}
	sort(tt,tt+n);
	sort(it,it+q);

	int ind=0;
	llo ans=0;

	for(int k=0;k<q;k++){
		pair<int,int> nn=it[k];

		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){
						int 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){
						int y=find(tt[ind].b);
						int 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(int 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