Submission #408920

#	Time	Username	Problem	Language	Result	Execution time	Memory
408920		doowey	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	4288 ms	61752 KiB

bubblesort2

#include <bits/stdc++.h>
#include "bubblesort2.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

const int N = (int)5e5 + 10;
const int M = N * 2;
const int inf = (int)1e9;

struct Node{
    int maxi;
    int cnt;
    int lzy;
};

vector<pii> cmp;

Node T[M * 4 + 512];

void push(int node, int cl, int cr){
    T[node].maxi -= T[node].lzy;
    T[node].cnt += T[node].lzy;
    if(cl != cr){
        T[node * 2].lzy += T[node].lzy;
        T[node * 2 + 1].lzy += T[node].lzy;
    }
    T[node].lzy = 0;
}

void set_val(int node, int cl, int cr, int id, int v){
    push(node, cl, cr);
    if(cl > id || cr < id) return;
    if(cl == cr){
        T[node].maxi = v;
        return;
    }
    int mid = (cl + cr) / 2;
    set_val(node * 2, cl, mid, id, v);
    set_val(node * 2 + 1, mid + 1, cr, id, v);
    T[node].maxi = max(T[node * 2].maxi, T[node * 2 + 1].maxi);
}

void incr(int node, int cl, int cr, int tl, int tr, int v){
    push(node, cl, cr);
    if(cr < tl || cl > tr) return;
    if(cl >= tl && cr <= tr){
        T[node].lzy = v;
        push(node, cl, cr);
        return;
    }
    int mid = (cl + cr) / 2;
    incr(node * 2, cl, mid, tl, tr, v);
    incr(node * 2 + 1, mid + 1, cr, tl, tr, v);
    T[node].maxi = max(T[node * 2].maxi, T[node * 2 + 1].maxi);
}

int get(int node, int cl, int cr, int tl, int tr){
    push(node, cl, cr);
    if(cr < tl) return 0;
    if(cl > tr) return 0;
    if(cl >= tl && cr <= tr){
        return T[node].cnt;
    }
    int mid = (cl + cr) / 2;
    return get(node * 2, cl, mid, tl, tr) + get(node * 2 + 1, mid + 1, cr, tl, tr);
}

void build(int node, int cl, int cr){
    T[node].maxi = -inf;
    if(cl == cr){
        return;
    }
    int mid = (cl + cr) / 2;
    build(node * 2, cl, mid);
    build(node * 2 + 1, mid + 1, cr);
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
	vector<int> outp;
    int n = A.size();
    int q = X.size();
    int sol;
    for(int i = 0 ; i < n; i ++ ){
        cmp.push_back(mp(A[i], i));
    }
    for(int iq = 0; iq < q; iq ++ ){
        cmp.push_back(mp(V[iq], X[iq]));
    }
    sort(cmp.begin(), cmp.end());
    cmp.resize(unique(cmp.begin(), cmp.end()) - cmp.begin());
    int m = cmp.size();
    build(1, 0, m - 1);
    int idx;
    for(int i = 0 ; i < n; i ++ ){
        idx = lower_bound(cmp.begin(), cmp.end(), mp(A[i], i)) - cmp.begin();
        incr(1, 0, m - 1, idx + 1, m - 1, +1);
    }
    int vv;
    for(int i = 0 ; i < n; i ++ ){
        idx = lower_bound(cmp.begin(), cmp.end(), mp(A[i], i)) - cmp.begin();
        vv = get(1, 0, m - 1, idx, idx);
        set_val(1, 0, m - 1, idx, i - vv);
    }
    for(int iq = 0; iq < q; iq ++ ){
        idx = lower_bound(cmp.begin(), cmp.end(), mp(A[X[iq]], X[iq])) - cmp.begin();
        vv = get(1, 0, m - 1, idx, idx);
        set_val(1, 0, m - 1, idx, -inf);
        incr(1, 0, m - 1, idx + 1, m - 1, -1);

        A[X[iq]] = V[iq];
        idx = lower_bound(cmp.begin(), cmp.end(), mp(A[X[iq]], X[iq])) - cmp.begin();
        vv = get(1, 0, m - 1, idx, idx);
        set_val(1, 0, m - 1, idx, X[iq] - vv);
        incr(1, 0, m - 1, idx + 1, m - 1, +1);
        outp.push_back(T[1].maxi);
    }
    return outp;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:89:9: warning: unused variable 'sol' [-Wunused-variable]
   89 |     int sol;
      |         ^~~

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 40 / 40