oj.uz

Submission #603328

# Submission time Handle Problem Language Result Execution time Memory
603328 2022-07-24T03:00:43 Z tamthegod Money (IZhO17_money) C++14
0 / 100
 25 ms 8148 KB 
#include<bits/stdc++.h>

#define int long long
#define pb push_back
#define fi first
#define se second
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxN = 1e6 + 5;
const int mod = 1e9 + 7;
const ll oo = 1e18;
int n, a[maxN];
int bit[maxN];
void update(int pos, int val)
{
    while(pos < maxN)
    {
        bit[pos] += val;
        pos += (pos & (-pos));
    }
}
int get(int pos)
{
    int res = 0;
    while(pos)
    {
        res += bit[pos];
        pos -= (pos & (-pos));
    }
    return res;
}
void ReadInput()
{
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i];
}
void Solve()
{
    for(int i=1; i<maxN; i++) update(i, 1);
    int res = 1;
    for(int i=1; i<=n; i++)
    {
        update(a[i], -1);
        if(a[i] < a[i - 1])
        {
            res++;
            continue;
        }
        if(a[i] == a[i - 1]) continue;
        if(get(a[i] - 1) - get(a[i - 1]) != (a[i] - a[i - 1] - 1)) res++;
    }
    cout << res;
}
int32_t main()
{
   // freopen("x.inp", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ReadInput();
    Solve();
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8148 KB Output is correct
2 Correct 20 ms 8080 KB Output is correct
3 Correct 18 ms 8040 KB Output is correct
4 Correct 18 ms 8076 KB Output is correct
5 Correct 19 ms 8068 KB Output is correct
6 Correct 18 ms 8148 KB Output is correct
7 Correct 25 ms 8108 KB Output is correct
8 Correct 20 ms 8144 KB Output is correct
9 Correct 19 ms 8148 KB Output is correct
10 Correct 19 ms 8040 KB Output is correct
11 Correct 20 ms 8148 KB Output is correct
12 Incorrect 19 ms 8116 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8148 KB Output is correct
2 Correct 20 ms 8080 KB Output is correct
3 Correct 18 ms 8040 KB Output is correct
4 Correct 18 ms 8076 KB Output is correct
5 Correct 19 ms 8068 KB Output is correct
6 Correct 18 ms 8148 KB Output is correct
7 Correct 25 ms 8108 KB Output is correct
8 Correct 20 ms 8144 KB Output is correct
9 Correct 19 ms 8148 KB Output is correct
10 Correct 19 ms 8040 KB Output is correct
11 Correct 20 ms 8148 KB Output is correct
12 Incorrect 19 ms 8116 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8148 KB Output is correct
2 Correct 20 ms 8080 KB Output is correct
3 Correct 18 ms 8040 KB Output is correct
4 Correct 18 ms 8076 KB Output is correct
5 Correct 19 ms 8068 KB Output is correct
6 Correct 18 ms 8148 KB Output is correct
7 Correct 25 ms 8108 KB Output is correct
8 Correct 20 ms 8144 KB Output is correct
9 Correct 19 ms 8148 KB Output is correct
10 Correct 19 ms 8040 KB Output is correct
11 Correct 20 ms 8148 KB Output is correct
12 Incorrect 19 ms 8116 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 8148 KB Output is correct
2 Correct 20 ms 8080 KB Output is correct
3 Correct 18 ms 8040 KB Output is correct
4 Correct 18 ms 8076 KB Output is correct
5 Correct 19 ms 8068 KB Output is correct
6 Correct 18 ms 8148 KB Output is correct
7 Correct 25 ms 8108 KB Output is correct
8 Correct 20 ms 8144 KB Output is correct
9 Correct 19 ms 8148 KB Output is correct
10 Correct 19 ms 8040 KB Output is correct
11 Correct 20 ms 8148 KB Output is correct
12 Incorrect 19 ms 8116 KB Output isn't correct
13 Halted 0 ms 0 KB -