Submission #253207

#	Time	Username	Problem	Language	Result	Execution time	Memory
253207		nandonathaniel	Pilot (NOI19_pilot)	C++14	100 / 100	597 ms	60920 KiB

pilot

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> pii;
const LL MAXN=1000005;
pii arr[MAXN];
bool ada[MAXN];
LL par[MAXN],sz[MAXN],ans[MAXN];

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

void join(LL u,LL v){
	LL repu=find(u),repv=find(v);
	par[repu]=repv;
	sz[repv]+=sz[repu];
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	LL n,q,h;
	cin >> n >> q;
	for(LL i=1;i<=n;i++){
		cin >> h;
		arr[i]={h,i};
		par[i]=i;
		sz[i]=1;
	}
	sort(arr+1,arr+n+1);
	for(LL i=1;i<=n;i++){
		pii isi=arr[i];
		LL kiri=0,kanan=0;
		if(ada[isi.second-1]){
			kiri=sz[find(isi.second-1)];
			join(isi.second,isi.second-1);
		}
		if(ada[isi.second+1]){
			kanan=sz[find(isi.second+1)];
			join(isi.second,isi.second+1);
		}
		ada[isi.second]=true;
		ans[isi.first]+=(kiri+1)*(kanan+1);
	}
	for(LL i=1;i<=MAXN;i++)ans[i]+=ans[i-1];
	while(q--){
		cin >> h;
		cout << ans[h] << '\n';
	}
	return 0;
}

Compilation message (stderr)

pilot.cpp: In function 'int main()':
pilot.cpp:46:31: warning: iteration 1000004 invokes undefined behavior [-Waggressive-loop-optimizations]
  for(LL i=1;i<=MAXN;i++)ans[i]+=ans[i-1];
                         ~~~~~~^~~~~~~~~~
pilot.cpp:46:14: note: within this loop
  for(LL i=1;i<=MAXN;i++)ans[i]+=ans[i-1];
             ~^~~~~~

• 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: 11 / 11