oj.uz

Submission #571033

# Submission time Handle Problem Language Result Execution time Memory
571033 2022-06-01T06:06:31 Z saarang123 Money (IZhO17_money) C++17
0 / 100
 8 ms 8228 KB 
#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++;
    	}
    	upd(a[i], -1);
    }
    cout << ans << '\n';
    return 0;
}

Compilation message

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.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8148 KB Output is correct
2 Correct 6 ms 8148 KB Output is correct
3 Correct 8 ms 8148 KB Output is correct
4 Correct 6 ms 8148 KB Output is correct
5 Correct 7 ms 8148 KB Output is correct
6 Correct 7 ms 8176 KB Output is correct
7 Incorrect 7 ms 8228 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8148 KB Output is correct
2 Correct 6 ms 8148 KB Output is correct
3 Correct 8 ms 8148 KB Output is correct
4 Correct 6 ms 8148 KB Output is correct
5 Correct 7 ms 8148 KB Output is correct
6 Correct 7 ms 8176 KB Output is correct
7 Incorrect 7 ms 8228 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8148 KB Output is correct
2 Correct 6 ms 8148 KB Output is correct
3 Correct 8 ms 8148 KB Output is correct
4 Correct 6 ms 8148 KB Output is correct
5 Correct 7 ms 8148 KB Output is correct
6 Correct 7 ms 8176 KB Output is correct
7 Incorrect 7 ms 8228 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8148 KB Output is correct
2 Correct 6 ms 8148 KB Output is correct
3 Correct 8 ms 8148 KB Output is correct
4 Correct 6 ms 8148 KB Output is correct
5 Correct 7 ms 8148 KB Output is correct
6 Correct 7 ms 8176 KB Output is correct
7 Incorrect 7 ms 8228 KB Output isn't correct
8 Halted 0 ms 0 KB -