Submission #224567

#	Time	Username	Problem	Language	Result	Execution time	Memory
224567		kshitij_sodani	Pilot (NOI19_pilot)	C++17	89 / 100	1097 ms	111400 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];
vector<llo> it[1000001];
vector<llo> tt[1000001];
llo find(llo no){

	if(par[no]==no){
		return no;
	}
	par[no]=find(par[no]);
	return par[no];
}


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;
	}
	
	llo aa;
	for(llo i=0;i<n;i++){
		cin>>aa;
		it[aa].pb(i);
	}
	llo ans2[q];
	
	for(llo i=0;i<q;i++){
		cin>>aa;
		tt[aa].pb(i);
	}


	llo ans=0;
	for(llo k=0;k<1000001;k++){

		for(llo j=0;j<it[k].size();j++){

			llo ind=it[k][j];
			ss[ind]=1;
			ans+=1;
			if(ind>0){
				if(ss[ind-1]>0){
					llo x=find(ind-1);
					
					ans+=ss[x];
					ss[x]+=ss[ind];
					par[ind]=x;
				}
				
			}
			if(ind<n-1){
				if(ss[ind+1]>0){
					llo y=find(ind);
					llo x=find(ind+1);
					if(ss[x]>ss[y]){
						ans+=ss[x]*ss[y];
						ss[x]+=ss[y];
						par[y]=x;
					}
					else{
					
						ans+=ss[x]*ss[y];
						ss[y]+=ss[x];
						par[x]=y;
					}

				}
			}
		}
		for(int j=0;j<tt[k].size();j++){
			ans2[tt[k][j]]=ans;
		}
	}
	for(llo i=0;i<q;i++){
		cout<<ans2[i]<<endl;
	}




	return 0;
}

Compilation message (stderr)

pilot.cpp: In function 'int main()':
pilot.cpp:48:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(llo j=0;j<it[k].size();j++){
               ~^~~~~~~~~~~~~
pilot.cpp:82:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int j=0;j<tt[k].size();j++){
               ~^~~~~~~~~~~~~

• 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