oj.uz

Submission #340401

# Submission time Handle Problem Language Result Execution time Memory
340401 2020-12-27T14:09:14 Z balanda Money (IZhO17_money) C++17
0 / 100
 1500 ms 31596 KB 
/*
             _   _                    _           _                 _         __   _____ _____ _
            | | | |               _  | |         | |               | |       /  | |____ |  ___(_)
  __ _ _   _| |_| |__   ___  _ __(_) | |__   __ _| | __ _ _ __   __| | __ _  `| |     / /___ \ _  __ _
 / _` | | | | __| '_ \ / _ \| '__|   | '_ \ / _` | |/ _` | '_ \ / _` |/ _` |  | |     \ \   \ \ |/ _` |
| (_| | |_| | |_| | | | (_) | |   _  | |_) | (_| | | (_| | | | | (_| | (_| | _| |_.___/ /\__/ / | (_| |
 \__,_|\__,_|\__|_| |_|\___/|_|  (_) |_.__/ \__,_|_|\__,_|_| |_|\__,_|\__,_| \___/\____/\____/|_|\__, |
                                                                                                    | |
                                                                                                    |_|
  __ _  __ _   _ __ ___   __ ___   _________  ___
 / _` |/ _` | | '_ ` _ \ / _` \ \ / /_  / _ \/ __|
| (_| | (_| | | | | | | | (_| |\ V / / /  __/\__ \
 \__, |\__, | |_| |_| |_|\__,_| \_/ /___\___||___/
    | |   | |
    |_|   |_|
 * */
#include <bits/stdc++.h>

using namespace std;
#define endl '\n'
#define int long long

template<class T>
istream& operator>>(istream &in, vector<T> &v){
    for(auto &to: v) in >> to;
    return in;
}

template<class T>
ostream& operator<<(ostream &out, const vector<T> &v){
    for(auto &to: v) out << v << ' ';
    return out;
}


template<class U, class V>
istream& operator>>(istream &in, pair<U, V> &v){
    in >> v.first >> v.second;
    return in;
}

template<class U, class V>
ostream& operator<<(ostream &out, const pair<U, V> &v){
    out << v.first << ' ' << v.second;
    return out;
}

#ifdef DEBUG
#define dbg(x) cout << "debug:" << __LINE__ << ' ' << #x << "=" << x
#else
#define dbg(x) 42
#endif

vector<int> tree;

void upd(int v, int tl, int tr, int ind){
    if(tl + 1 == tr) {
        tree[v] += 1;
        return;
    }
    int tm = tl + tr >> 1;
    if(ind >= tm)
        upd(2 * v + 2, tm, tr, ind);
    else upd(2 * v + 1, tl, tm, ind);
    tree[v] = tree[2 * v + 1] + tree[2 * v + 2];
}

int get(int v, int tl, int tr, int l, int r){
    if(l >= r) return 0;
    if(tl == l && tr == r) return tree[v];
    int tm = tl + tr >> 1;
    return  get(2 * v + 1, tl, tm, l, min(r, tm)) +
            get(2 * v + 2, tm, tr, max(l, tm), r);
}

int solve(){
    int n;
    cin >> n;
    vector<int> v(n);
    cin >> v;
    tree.resize((int)4e6, 0);
    for(int i = 0; i < n; i++) v[i]--;
    int l = 0;
    int ans = 0;
    int r = 1;
    while(l < n){
        if(r == n){
            ans++;
            break;
        }
        if(v[r] < v[r - 1]){
            for(int i = l; i < r; i++)
                upd(0, 0, n, v[i]);
            l = r;
            r = l + 1;
            ans++;
        } else {
            if(get(0, 0, n, v[l] + 1, v[r])){
                for(int i = l; i < r; i++)
                    upd(0, 0, n, v[i]);
                l = r;
                r = l + 1;
                ans++;
            } else{
                r++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}
signed main() {
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
//        freopen("output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
//    cin >> t;
    while(t  --> 0){
        assert(solve() == 0);
        cout << endl;
    }
    return 0;
}

Compilation message

money.cpp: In function 'void upd(long long int, long long int, long long int, long long int)':
money.cpp:61:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   61 |     int tm = tl + tr >> 1;
      |              ~~~^~~~
money.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int)':
money.cpp:71:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |     int tm = tl + tr >> 1;
      |              ~~~^~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31596 KB Output is correct
2 Correct 19 ms 31596 KB Output is correct
3 Correct 20 ms 31596 KB Output is correct
4 Correct 20 ms 31596 KB Output is correct
5 Correct 17 ms 31596 KB Output is correct
6 Correct 17 ms 31596 KB Output is correct
7 Execution timed out 1586 ms 31596 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31596 KB Output is correct
2 Correct 19 ms 31596 KB Output is correct
3 Correct 20 ms 31596 KB Output is correct
4 Correct 20 ms 31596 KB Output is correct
5 Correct 17 ms 31596 KB Output is correct
6 Correct 17 ms 31596 KB Output is correct
7 Execution timed out 1586 ms 31596 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31596 KB Output is correct
2 Correct 19 ms 31596 KB Output is correct
3 Correct 20 ms 31596 KB Output is correct
4 Correct 20 ms 31596 KB Output is correct
5 Correct 17 ms 31596 KB Output is correct
6 Correct 17 ms 31596 KB Output is correct
7 Execution timed out 1586 ms 31596 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 31596 KB Output is correct
2 Correct 19 ms 31596 KB Output is correct
3 Correct 20 ms 31596 KB Output is correct
4 Correct 20 ms 31596 KB Output is correct
5 Correct 17 ms 31596 KB Output is correct
6 Correct 17 ms 31596 KB Output is correct
7 Execution timed out 1586 ms 31596 KB Time limit exceeded
8 Halted 0 ms 0 KB -