Submission #291771

#	Time	Username	Problem	Language	Result	Execution time	Memory
291771		alexandra_udristoiu	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	1807 ms	63352 KiB

bubblesort2

#include "bubblesort2.h"
#include<vector>
#include<algorithm>
#define DIM 1000005
#define f first
#define s second
using namespace std;
static vector<int> sol;
struct str{
    int p, val, ind, inds;
};
static str v[DIM];
static int lst[DIM];
static pair<int, int> aint[4 * DIM];
static int cmp1(str a, str b){
    if(a.val == b.val){
        return a.p < b.p;
    }
    return a.val < b.val;
}
static int cmp2(str a, str b){
    return a.ind < b.ind;
}
static void update(int nod, int st, int dr, int p, int u, int val){
    if(p <= st && dr <= u){
        aint[nod].s += val;
    }
    else{
        int mid = (st + dr) / 2;
        aint[2 * nod].s += aint[nod].s;
        aint[2 * nod + 1].s += aint[nod].s;
        aint[nod].s = 0;
        if(p <= mid){
            update(2 * nod, st, mid, p, u, val);
        }
        if(u > mid){
            update(2 * nod + 1, mid + 1, dr, p, u, val);
        }
        aint[nod].f = max(aint[2 * nod].f + aint[2 * nod].s, aint[2 * nod + 1].f + aint[2 * nod + 1].s);
    }
}

vector<int> countScans(vector<int> a, vector<int> xq, vector<int> yq){
    int n, q, i;
    n = a.size();
    q = xq.size();
    sol.resize(q);
    for(i = 1; i <= n; i++){
        v[i] = {i, a[i - 1], i, 0};
    }
    for(i = 1; i <= q; i++){
        v[i + n] = {xq[i - 1] + 1, yq[i - 1], i + n, 0};
    }
    sort(v + 1, v + n + q + 1, cmp1);
    for(i = 1; i <= n + q; i++){
        v[i].inds = i;
        if(v[i].ind <= n){
            update(1, 1, n + q, i, n + q, -1);
            update(1, 1, n + q, i, i, v[i].p);
        }
    }
    sort(v + 1, v + n + q + 1, cmp2);
    for(i = 1; i <= n; i++){
        lst[ v[i].p ] = v[i].inds;
    }
    for(i = n + 1; i <= n + q; i++){
        update(1, 1, n + q, lst[ v[i].p ], n + q, 1);
        update(1, 1, n + q, lst[ v[i].p ], lst[ v[i].p ], -v[i].p);
        update(1, 1, n + q, v[i].inds, n + q, -1);
        update(1, 1, n + q, v[i].inds, v[i].inds, v[i].p);
        lst[ v[i].p ] = v[i].inds;
        sol[i - n - 1] = aint[1].f + aint[1].s;
    }
    return sol;
}

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