Submission #571032

#	Time	Username	Problem	Language	Result	Execution time	Memory
571032		saarang123	Money (IZhO17_money)	C++17	0 / 100	7 ms	8148 KiB

money

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

const int MXN = 1000 * 1000 + 3;
int bit[MXN], mn[MXN], mx[MXN], a[MXN], b[MXN], p[MXN];

void upd(int x, int v) {
	for(; x < MXN; x += (x & -x))
		bit[x] += v;
}

int qry(int x) {
	int res = 0;
	for(; x > 0; x -= (x & -x))
		res += bit[x];
	return res;
}

int qry(int l, int r) { return qry(r) - qry(l - 1); }

signed main() {
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n; cin >> n;
    for(int i = 1; i <= n; i++) {
    	cin >> a[i];
    	b[i] = a[i];
    	p[a[i]]++;
    	upd(a[i], 1);
    }
    for(int i = 1; i < MXN; i++)
    	p[i] += p[i - 1];
    memset(mn, 0x0f, sizeof mn);
    sort(b + 1, b + n + 1);
    for(int i = 1; i <= n; i++) {
    	mn[b[i]] = min(mn[b[i]], i);
    	mx[b[i]] = i;
    }

    int ans = 1;
    bool last = false;
    for(int i = 1; i <= n; i++) {
    	if(mx[a[i - 1]] + 1 == mn[a[i]] || mx[a[i - 1]] == mn[a[i]])
    		last = true;
    	else {
    		if(a[i - 1] < a[i] && qry(a[i - 1] + 1, a[i]) == p[a[i]] - p[a[i - 1]])
    			last = true;
    		else
    			ans++;
    	}
    }
    cout << ans << '\n';
    return 0;
}

Compilation message (stderr)

money.cpp: In function 'int main()':
money.cpp:42:10: warning: variable 'last' set but not used [-Wunused-but-set-variable]
   42 |     bool last = false;
      |          ^~~~

• Subtask 1: 0 / 9
• Subtask 2: 0 / 16
• Subtask 3: 0 / 20
• Subtask 4: 0 / 55