oj.uz

Submission #1113508

# Submission time Handle Problem Language Result Execution time Memory
1113508 2024-11-16T17:05:17 Z jkb_gryz Bubble Sort 2 (JOI18_bubblesort2) C++14
0 / 100
 101 ms 98900 KB 
#include <bits/stdc++.h>
#include "bubblesort2.h"

using namespace std;
#define ll long long

const int base = 1<<20;
const ll INF = 1e18+7;
const ll MAXN = 1e6+7;

ll tree[base<<1];
set<int> pozycje[MAXN];
ll lazy[base<<1];
int n;

void build(ll v, ll l, ll r){
    if(l == r){
        if(l > n){
            tree[v] = -INF;
            return;
        }
        auto tmp = pozycje[l].end();
        --tmp;
        tree[v] = -(n - *tmp - 1);
    }
    else{
        ll mid = (l + r)/2;
        build(2*v, l, mid);
        build(2*v+1, mid+1, r);

        tree[v] = max(tree[2*v], tree[2*v+1]);
    }
}

void push(ll v){
    lazy[2*v] += lazy[v];
    lazy[2*v+1] += lazy[v];
    
    tree[2*v] += lazy[v];
    tree[2*v+1] += lazy[v];

    lazy[v] = 0;
}

ll p, k;
ll val;

void update(ll v, ll l, ll r){
    if(l > k || r < p) return;
    if(p <= l && r <= k){
        tree[v] += val;
        lazy[v] += val;
    }
    else{
        ll mid = (l+r)/2;

        push(v);

        update(2*v, l, mid);
        update(2*v+1, mid+1, r);

        tree[v] = max(tree[2*v], tree[2*v+1]);
    }
}

ll query(ll v, ll l, ll r){
    if(l > k || r < p) return -INF;
    if(p <= l && r <= k){
        return tree[v];
    }
    else{
        ll mid = (l+r)/2;

        push(v);

        auto lQ = query(2*v, l, mid);
        auto rQ = query(2*v+1, mid+1, r);
        return max(lQ, rQ);
    }
}


vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
    n = A.size();
	int Q = X.size();
	vector<int> res(Q);

    map<long long, int> skalowanie;
    for(auto i : A){
        skalowanie[i] = 0;
    }
    for(auto i : V){
        skalowanie[i] = 0;
    }
    int id = 0;

    for(auto &i : skalowanie) i.second = ++id, pozycje[i.second].insert(-1);

    for(ll i = 0; i < n; ++i){ 
        auto vi = A[i];
        pozycje[skalowanie[vi]].insert(i);
    }

    build(1, 1, n);
    // for(int i = 0; i <= id; ++i){
    //     p = k = i;
    //     cerr << query(1, 1, n) << " ";
    // }
    // cerr << "\n";
    for(int i = 0; i < n; ++i){
        auto vi = A[i];
        p = 0, k = skalowanie[vi]-1;
        val = 1;
        update(1, 1, n);
    }
    // for(int i = 0; i <= id; ++i){
    //     p = k = i;
    //     cerr << query(1, 1, n) << " ";
    // }
    // cerr << "\n";
    for(int i = 0; i < Q; ++i){
        p = 0, k = skalowanie[A[X[i]]]-1;
        val = -1;
        update(1, 1, n);

        pozycje[skalowanie[A[X[i]]]].erase(X[i]);
        auto tmp = pozycje[skalowanie[A[X[i]]]].end();
        --tmp;
        p = k = skalowanie[A[X[i]]];
        val = max(*tmp, 0) - X[i];
        if(*tmp == -1) val -= INF;
        // cerr << A[X[i]] << " " << *tmp << ": " << val << "\n";
        update(1, 1, n);

        // for(int i = 0; i <= id; ++i){
        //     p = k = i;
        //     cerr << query(1, 1, n) << " ";
        // }
        // cerr << "\n";

        A[X[i]] = V[i];

        p = 0, k = skalowanie[A[X[i]]]-1;
        val = 1;
        update(1, 1, n);

        tmp = pozycje[skalowanie[A[X[i]]]].end();
        --tmp;
        p = k = skalowanie[A[X[i]]];
        if(X[i] > *tmp){
            // cerr << V[i] << ": " << *tmp << "\n";
            val = X[i] - max(*tmp, 0);
            if(*tmp == -1) val += INF;
            update(1, 1, n);
        }
        pozycje[skalowanie[A[X[i]]]].insert(X[i]);
        
        // for(int i = 0; i <= id; ++i){
        //     p = k = i;
        //     cerr << query(1, 1, n) << " ";
        // }
        // cerr << "\n";

        p = 0, k = id;
        res[i] = query(1, 1, n);
    }

	return res;
}

Subtask #1
0 / 17.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 101 ms 98900 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

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