Submission #260717

#	Time	Username	Problem	Language	Result	Execution time	Memory
260717		ChrisT	Exercise Deadlines (CCO20_day1problem2)	C++17	25 / 25	253 ms	18292 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pli = pair<ll,int>;
using pll = pair<ll,ll>;
using ld = long double;
#define all(x) (x).begin(),(x).end()
const int MN = 2e5 + 5, MOD = 1e9 + 7, BASE = 131;
int bit[MN],n; set<int> in;
void inc (int i) {
	for (;i<MN;i+=i&-i)
		++bit[i];
}
void dec (int i) {
	for (;i<MN;i+=i&-i)
		--bit[i];
}
int query (int i) {
	int ret = 0;
	for (;i;i^=i&-i)
		ret += bit[i];
	return ret;
}
int bsearch (int ind) {
	int l = 1, r = n, mid, ans = -1;
	while (l <= r) {
		mid = (l+r)/2;
		if (query(mid) <= ind) l = (ans = mid) + 1;
		else r = mid - 1;
	}
	return ans;
}
int main () {
	scanf ("%d",&n);
	vector<vector<int>> where(n+1);
	vector<int> d(n+1);
	ll ret = 0;
	for (int i = 1; i <= n; i++) scanf ("%d",&d[i]), where[d[i]].push_back(i), inc(i);
	for (int i = n; i >= 1; i--) {
		for (int go : where[i]) in.insert(go);
		int where = bsearch(i);
		auto it = in.upper_bound(where);
		if (it == in.begin()) return !printf ("-1\n");
		--it;
		int pos = *it;
		in.erase(it);
		ret += i - query(pos);
		dec(pos);
	}
	printf ("%lld\n",ret);
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:35:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   35 |  scanf ("%d",&n);
      |  ~~~~~~^~~~~~~~~
Main.cpp:39:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   39 |  for (int i = 1; i <= n; i++) scanf ("%d",&d[i]), where[d[i]].push_back(i), inc(i);
      |                               ~~~~~~^~~~~~~~~~~~

• Subtask 1: 17 / 17
• Subtask 2: 8 / 8