oj.uz

Submission #180265

# Submission time Handle Problem Language Result Execution time Memory
180265 2020-01-08T13:08:03 Z mat_v Money (IZhO17_money) C++14
0 / 100
 3 ms 376 KB 
#include <bits/stdc++.h>

using namespace std;


int n;
int niz[1000005];
int bit[1000005];
int upit(int x){
    int res = 0;
    while(x > 0){
        res += bit[x];
        x -= (x&-x);
    }
    return res;
}
void add(int x){
    while(x <= 1000000){
        bit[x]++;
        x += (x&-x);
    }
}
int query(int l, int r){
    return upit(r) - upit(l - 1);
}
void ubaci(int l, int r){
    for(int i=l; i<=r; i++){
        add(niz[l]);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin >> n;
    for(int i=1; i<=n; i++)cin >> niz[i];
    int br = 1;
    int last = 1;
    int res = 1;
    while(br <= n){
        if(niz[br] < niz[br - 1]){
            ubaci(last, br - 1);
            last = br;
            br++;
            res++;
            continue;
        }
        if(query(niz[last], niz[br]) >= 1){
            ubaci(last, br - 1);
            last = br;
            br++;
            res++;
        }
        else br++;
    }
    cout << res << endl;
    return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -