oj.uz

답안 #676237

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
676237 2022-12-29T22:18:13 Z stevancv Money (IZhO17_money) C++14
0 / 100
 1 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> iid(n + 1);
    iota(iid.begin(), iid.end(), 0);
    sort(iid.begin(), iid.end(), [&] (int i, int j) {
        return a[i] < a[j];
    });
    vector<int> id(n + 1);
    for (int i = 1; i <= n; i++) id[iid[i]] = i;
    for (int i = 1; i <= n; i++) f.Add(i, i);
    int ans = 0;
    for (int i = n; i >= 1; ) {
        int j = i - 1;
        int sta = f.Val(id[i]);
        while (j > 0 && f.Val(id[j]) == sta - i + j) j--;
        ans++;
        f.Add(id[j + 1] - 1, i - j);
        i = j;
    }
    cout << ans << en;
    return 0;
}

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -