Submission #943210

#	Time	Username	Problem	Language	Result	Execution time	Memory
943210		Lilypad	Pilot (NOI19_pilot)	C++14	100 / 100	451 ms	60500 KiB

pilot

#include<bits/stdc++.h>
using namespace std;
#define ll int
#define pii pair<ll,ll>
#define pb push_back
#define fi first
#define se second

const ll N = 1e6+5;

ll n,q,tmp;
long long ans,ansq[N],sz[N];
ll par[N],a[N];
pii b[N],x[N];

ll root(ll x) {
	if(par[x] == x) return x;
	return par[x] = root(par[x]);
}

void join(ll y, ll z) {
	ll ry = root(y);
	ll rz = root(z);
	if(ry == rz) return;
	par[ry] = rz;
	ans -= (sz[rz] + sz[ry]);
	ans -= (sz[rz]*(sz[rz]-1))/2;
	ans -= (sz[ry]*(sz[ry]-1))/2;
	sz[rz] += sz[ry];
	ans += (sz[rz]*(sz[rz]-1))/2 + sz[rz];
}

int main() {
//	ios_base::sync_with_stdio(0);
//	cin.tie(0);
	scanf("%d %d", &n, &q);
	for(int i=1; i<=n; i++) {
		scanf("%d", &a[i]);
		b[i].fi = a[i]; b[i].se = i;
		par[i] = i;
	}
	sort(b+1,b+n+1);
	for(int i=1; i<=q; i++) {
		scanf("%d", &x[i].fi);
		x[i].se = i;
	}
	sort(x+1,x+q+1);
	ll idx = 1;
	for(int i=1; i<=q; i++) {
		while(idx <= n && b[idx].fi <= x[i].fi) {
			ll var = b[idx].se;
			sz[var] = 1;
			ans++;
			if(var > 1 && sz[var-1] > 0) join(var-1,var);
			if(var < n && sz[var+1] > 0) join(var+1,var);
			idx++;
		}
		ansq[x[i].se] = ans;
	}
	for(int i=1; i<=q; i++) printf("%lld\n", ansq[i]);
}

Compilation message (stderr)

pilot.cpp: In function 'int main()':
pilot.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |  scanf("%d %d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~
pilot.cpp:38:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   38 |   scanf("%d", &a[i]);
      |   ~~~~~^~~~~~~~~~~~~
pilot.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |   scanf("%d", &x[i].fi);
      |   ~~~~~^~~~~~~~~~~~~~~~

• 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