oj.uz

Submission #102473

# Submission time Handle Problem Language Result Execution time Memory
102473 2019-03-25T07:52:58 Z minhtung0404 Bubble Sort 2 (JOI18_bubblesort2) C++14
0 / 100
 191 ms 131380 KB 
//https://oj.uz/problem/view/JOI18_bubblesort2

#include "bubblesort2.h"
#include<bits/stdc++.h>
const int N = 1e5 + 5;
const int MAX = 1e6 + 5;
const int inf = 1e9;
using namespace std;

map <int, int> mp;
typedef vector <int> vi;
multiset <int> ms[MAX];

int n, q, cnt, it[MAX << 2], lazy[MAX << 2], bit[MAX], offset[MAX];

void updateBIT(int i, int v){
    while (i < MAX){
        bit[i] += v;
        i += i&(-i);
    }
}

int getBIT(int i){
    int ans = 0;
    while (i > 0){
        ans += bit[i];
        i -= i&(-i);
    }
    return ans;
}

void dolazy(int i, int l, int r){
    if (!lazy[i]) return;
    if (l != r){
        lazy[i << 1] += lazy[i];
        lazy[i << 1 | 1] += lazy[i];
    }
    else{
        offset[l] += lazy[i];
    }
    it[i] += lazy[i];
    lazy[i] = 0;
}

void update(int i, int l, int r, int pos, int val){
    dolazy(i, l, r);
    if (l > pos || pos > r) return;
    if (l == r){
        ms[l].insert(val - offset[l]);
        if (ms[l].size()) it[i] = *ms[l].rbegin() + offset[l];
        else it[i] = -inf;
        return;
    }
    int mid = (l + r) >> 1;
    update(i << 1, l, mid, pos, val); update(i << 1 | 1, mid+1, r, pos, val);
    it[i] = max(it[i << 1], it[i << 1 | 1]);
}

void Erase(int i, int l, int r, int pos, int val){
    dolazy(i, l, r);
    if (l > pos || pos > r) return;
    if (l == r){
        ms[l].erase(ms[l].lower_bound(val - offset[l]));
        if (ms[l].size()) it[i] = *ms[l].rbegin() + offset[l];
        else it[i] = -inf;
        return;
    }
    int mid = (l + r) >> 1;
    Erase(i << 1, l, mid, pos, val); Erase(i << 1 | 1, mid+1, r, pos, val);
    it[i] = max(it[i << 1], it[i << 1 | 1]);
}

void update(int i, int l, int r, int L, int R, int v){
    dolazy(i, l, r);
    if (L > r || l > R) return;
    if (L <= l && r <= R){
        lazy[i] = v;
        dolazy(i, l, r);
        return;
    }
    int mid = (l + r) >> 1;
    update(i << 1, l, mid, L, R, v); update(i << 1 | 1, mid+1, r, L, R, v);
    it[i] = max(it[i << 1], it[i << 1 | 1]);
}

vi countScans(vi a, vi x, vi y){
    n = a.size(), q = x.size();
    vi ans(q);
    for (auto val : a) mp[val] = true;
    for (auto val : y) mp[val] = true;
    for (auto& p : mp) p.second = ++cnt;
    for (auto& val : a) val = mp[val], updateBIT(val, +1);
    for (auto& val : y) val = mp[val];
    for (int i = 0; i < MAX << 2; i++) it[i] = -inf;
    for (int i = 0; i < n; i++) update(1, 1, cnt, a[i], i+1-getBIT(a[i]));

    for (int i = 0; i < q; i++){
        Erase(1, 1, cnt, a[x[i]], x[i]+1-getBIT(a[x[i]]));
        update(1, 1, cnt, a[x[i]], cnt, +1);

        updateBIT(a[x[i]], -1);
        a[x[i]] = y[i];
        updateBIT(a[x[i]], +1);

        update(1, 1, cnt, a[x[i]], x[i]+1-getBIT(a[x[i]]));
        update(1, 1, cnt, a[x[i]], cnt, -1);
        ans[i] = it[1];
    }
    return ans;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 164 ms 126328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 164 ms 126328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 94 ms 64508 KB Output is correct
2 Runtime error 191 ms 131380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Runtime error 164 ms 126328 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -