oj.uz

Submission #1114216

# Submission time Handle Problem Language Result Execution time Memory
1114216 2024-11-18T11:28:32 Z farica Bubble Sort 2 (JOI18_bubblesort2) C++17
0 / 100
 21 ms 2896 KB 
#include <bits/stdc++.h>

using namespace std;
using vi = vector<int>;

vi a, segm, lazy;
vector<pair<int,int>>V;

void propagate(int pos, int l, int r) {
    if(l==r) return;
    int m = (l+r)/2, right = pos + 2 * (m-l+1);
    lazy[pos+1] += lazy[pos];
    lazy[right] += lazy[pos];
    segm[pos+1] += lazy[pos];
    segm[right] += lazy[pos];
    lazy[pos] = 0;
}

void upd(int pos, int l, int r, int L, int R, int val) {
    if(l > R or r < L) return;
    propagate(pos, l, r);
    if(l >= L && r <= R) {
        segm[pos] += val;
        lazy[pos] += val;
        return;
    }
    int m = (l+r)/2, right = pos + 2 * (m-l+1);
    if(L <= m) upd(pos+1, l, m, L, R, val);
    if(R >= m+1) upd(right, m+1, r, L, R, val);
    segm[pos] = max(segm[pos+1], segm[right]);
}

void add(int i, int x) {
    int j = lower_bound(V.begin(), V.end(), make_pair(a[i], i)) - V.begin();
    int j2 = lower_bound(V.begin(), V.end(), make_pair(a[i], -1)) - V.begin();
    upd(1, 0, V.size()-1, j, j, x*(i+1));
    upd(1, 0, V.size()-1, j2, V.size()-1, -x);
}

vi countScans(vi A, vi x, vi y) {
    int n = A.size(), q = x.size();
    vi ans;
    segm.assign(8*n, 0);
    lazy.assign(8*n, 0);
    a.assign(n, 0);
    for(int i=0; i<n; ++i) {
        a[i] = A[i];
        V.push_back({A[i], i});
    }
    sort(V.begin(), V.end());
    V.erase(unique(V.begin(), V.end()), V.end());
    for(int i=0; i<n; ++i) add(i, 1);
    for(int i=0; i<q; ++i) {
        add(x[i], -1);
        a[x[i]] = y[i];
        add(x[i], 1);
        ans.push_back(segm[0]);
    }
    return ans;
}

Subtask #1
0 / 17.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 2896 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

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