oj.uz

Submission #676232

# Submission time Handle Problem Language Result Execution time Memory
676232 2022-12-29T22:02:46 Z stevancv Money (IZhO17_money) C++14
0 / 100
 1500 ms 340 KB 
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define sp ' '
#define en '\n'
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
using namespace std;
const int N = 1e6 + 2;
const ll linf = 1e18;
struct fenwick {
    ll bit[N];
    void Add(int x, int y) {
        if (x == 0) return;
        for (;x < N; x += x & (-x)) bit[x] += y;
    }
    ll Get(int x) {
        ll ans = 0;
        for (; x > 0; x -= x & (-x)) ans += bit[x];
        return ans;
    }
    ll Val(int x) {
        return Get(x) - Get(x - 1);
    }
}f;
int a[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n; cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<int> id(n + 1);
    iota(id.begin(), id.end(), 0);
    sort(id.begin(), id.end(), [&] (int i, int j) {
        return a[i] < a[j];
    });
    for (int i = 1; i <= n; i++) f.Add(i, i);
    int ans = 0;
    for (int i = n; i >= 1; ) {
        int j = i - 1;
        while (j >= 0 && f.Val(id[j]) == id[i] - i + j) j--;
        ans++;
        f.Add(id[j + 1] - 1, i - j);
        i = j;
    }
    cout << ans << en;
    return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Execution timed out 1580 ms 340 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Execution timed out 1580 ms 340 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Execution timed out 1580 ms 340 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Execution timed out 1580 ms 340 KB Time limit exceeded
3 Halted 0 ms 0 KB -