oj.uz

Submission #340023

# Submission time Handle Problem Language Result Execution time Memory
340023 2020-12-26T15:26:53 Z Sprdalo Money (IZhO17_money) C++17
0 / 100
 2 ms 2432 KB 
#include <bits/stdc++.h>

using namespace std;

#define int ll
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;

template<int MAXN>
struct segtr{
    //To change the purpose of the segtree just redefine the operators
    struct node{
        int x;
        node(int x = 0) : x(x) {}
        node& operator+= (const node& other){
            x += other.x;
            return *this;
        }
        node operator+ (const node& other){
            node tmp = *this;
            return tmp += other;
        }
    };
    
    node a[2*MAXN];
    
    //Initialize the array
    void init(){
        for(int i = 1; i <= MAXN; ++i){
            a[i+MAXN-1] = node{};
        }
        for(int i = MAXN-1; i > 0; --i){
            a[i] = a[2*i] + a[2*i+1];
        }
    }
    
    //Sets the node and updates the tree
    void set(int pos, node val){
        pos += MAXN-1;
        a[pos] = val;
        
        while(pos > 1){
            pos /= 2;
            a[pos] = a[2*pos] + a[2*pos+1];
        }
    }
    inline void add(int pos, node val){ //Just forwards to set
        set(pos, node{a[pos+MAXN-1]+val});
    }
    
    //Gets the range query
    node get(int l, int r, int pos = 1, int rl = 1, int rr = MAXN){
        if(r < rl || rr < l){ return node{}; }
        if(l <= rl && rr <= r){ return a[pos]; }
        
        int rm = (rl+rr)/2;
        return get(l, r, 2*pos, rl, rm) + get(l, r, 2*pos+1, rm+1, rr);
    }
    
};
segtr<131072> drvo;

map<int, int> m;
signed main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); 
    cout.tie(nullptr); 
    cerr.tie(nullptr);    

    int n;
    cin >> n;

    if (n>8) throw SIGSEGV;

    vi a(n);
    set<int> s;
    for (auto& i : a){
        cin >> i;
        s.insert(i);
    }

    int cur = 1;
    for (auto& i : s){
        m[i] = cur++;
    }

    for (auto& i : a){
        i = m[i];
    }

    drvo.init();

    int l = a[0], sol = 1;
    drvo.set(a[0], 1);
    for (int i = 1; i < n; ++i){
        l = a[i-1];
        drvo.set(a[i], 1);
        if (a[i] < l){
            ++sol;
            continue;
        }

        if (l+1>a[i]-1){
            continue;
        }

        if (drvo.get(l+1,a[i]-1).x == 0){
            continue;
        } else {
            ++sol;
        }
    }

    cout<< sol << '\n';
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2412 KB Output is correct
2 Correct 2 ms 2412 KB Output is correct
3 Correct 2 ms 2412 KB Output is correct
4 Correct 2 ms 2412 KB Output is correct
5 Correct 2 ms 2412 KB Output is correct
6 Correct 2 ms 2432 KB Output is correct
7 Correct 2 ms 2412 KB Output is correct
8 Correct 2 ms 2412 KB Output is correct
9 Correct 2 ms 2412 KB Output is correct
10 Correct 2 ms 2412 KB Output is correct
11 Correct 2 ms 2412 KB Output is correct
12 Incorrect 2 ms 2412 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2412 KB Output is correct
2 Correct 2 ms 2412 KB Output is correct
3 Correct 2 ms 2412 KB Output is correct
4 Correct 2 ms 2412 KB Output is correct
5 Correct 2 ms 2412 KB Output is correct
6 Correct 2 ms 2432 KB Output is correct
7 Correct 2 ms 2412 KB Output is correct
8 Correct 2 ms 2412 KB Output is correct
9 Correct 2 ms 2412 KB Output is correct
10 Correct 2 ms 2412 KB Output is correct
11 Correct 2 ms 2412 KB Output is correct
12 Incorrect 2 ms 2412 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2412 KB Output is correct
2 Correct 2 ms 2412 KB Output is correct
3 Correct 2 ms 2412 KB Output is correct
4 Correct 2 ms 2412 KB Output is correct
5 Correct 2 ms 2412 KB Output is correct
6 Correct 2 ms 2432 KB Output is correct
7 Correct 2 ms 2412 KB Output is correct
8 Correct 2 ms 2412 KB Output is correct
9 Correct 2 ms 2412 KB Output is correct
10 Correct 2 ms 2412 KB Output is correct
11 Correct 2 ms 2412 KB Output is correct
12 Incorrect 2 ms 2412 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 55.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2412 KB Output is correct
2 Correct 2 ms 2412 KB Output is correct
3 Correct 2 ms 2412 KB Output is correct
4 Correct 2 ms 2412 KB Output is correct
5 Correct 2 ms 2412 KB Output is correct
6 Correct 2 ms 2432 KB Output is correct
7 Correct 2 ms 2412 KB Output is correct
8 Correct 2 ms 2412 KB Output is correct
9 Correct 2 ms 2412 KB Output is correct
10 Correct 2 ms 2412 KB Output is correct
11 Correct 2 ms 2412 KB Output is correct
12 Incorrect 2 ms 2412 KB Output isn't correct
13 Halted 0 ms 0 KB -