Submission #239807

#	Time	Username	Problem	Language	Result	Execution time	Memory
239807		arnold518	Pilot (NOI19_pilot)	C++14	100 / 100	854 ms	57296 KiB

pilot

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e6;

int N, Q, A[MAXN+10];
pii B[MAXN+10];

int par[MAXN+10], sz[MAXN+10];
bool vis[MAXN+10];
ll ans[MAXN+10];

int Find(int x)
{
	if(x==par[x]) return x;
	return par[x]=Find(par[x]);
}

ll val=0;

void Union(int x, int y)
{
	x=Find(x); y=Find(y);
	if(x==y) return;
	val-=(ll)sz[x]*(sz[x]+1)/2;
	val-=(ll)sz[y]*(sz[y]+1)/2;
	sz[x]+=sz[y]; par[y]=x;
	val+=(ll)sz[x]*(sz[x]+1)/2;
}

int main()
{
	int i, j;

	scanf("%d%d", &N, &Q);
	for(i=1; i<=N; i++) par[i]=i, sz[i]=1;
	for(i=1; i<=N; i++) scanf("%d", &A[i]);
	for(i=1; i<=Q; i++) scanf("%d", &B[i].first), B[i].second=i;
	sort(B+1, B+Q+1);
	
	vector<pii> V;
	for(i=1; i<=N; i++) V.push_back({A[i], i});
	sort(V.begin(), V.end());	

	for(i=1, j=0; i<=Q; i++)
	{
		for(; j<V.size() && V[j].first<=B[i].first; j++)
		{
			int now=V[j].second;

			vis[now]=true; val++;
			if(now!=1 && vis[now-1]) Union(now, now-1);
			if(now!=N && vis[now+1]) Union(now, now+1);
		}
		ans[B[i].second]=val;
	}
	for(i=1; i<=Q; i++) printf("%lld\n", ans[i]);
}

Compilation message (stderr)

pilot.cpp: In function 'int main()':
pilot.cpp:51:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; j<V.size() && V[j].first<=B[i].first; j++)
         ~^~~~~~~~~
pilot.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &Q);
  ~~~~~^~~~~~~~~~~~~~~~
pilot.cpp:41:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%d", &A[i]);
                      ~~~~~^~~~~~~~~~~~~
pilot.cpp:42:46: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=Q; i++) scanf("%d", &B[i].first), B[i].second=i;
                      ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

• 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