Submission #97789

#	Time	Username	Problem	Language	Result	Execution time	Memory
97789		Alexa2001	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	3010 ms	46628 KiB

bubblesort2

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

#define mid ((st+dr)>>1)
#define left_son (node<<1)
#define right_son ((node<<1)|1)

using namespace std;

const int Nmax = 1e6 + 5, lim = 1e6, inf = 1e6;
typedef long long ll;

ll a[Nmax], val[Nmax];

class SegmentTree
{
    int lazy[Nmax<<2], a[Nmax<<2];

public:
    void add(int node, int st, int dr, int L, int R, int Add)
    {
        if(L <= st && dr <= R)
        {
            lazy[node] += Add;
            return;
        }

        if(L <= mid) add(left_son, st, mid, L, R, Add);
        if(mid < R) add(right_son, mid+1, dr, L, R, Add);

        a[node] = max(a[left_son] + lazy[left_son], a[right_son] + lazy[right_son]);
    }
    int query()
    {
        return a[1] + lazy[1];
    }
    void init(int node, int st, int dr)
    {
        a[node] = -inf; lazy[node] = 0;
        if(st == dr) return;
        init(left_son, st, mid); init(right_son, mid+1, dr);
    }

} aint;

int Search(vector<ll> &a, ll val)
{
    int st = 0, dr = a.size() - 1;
    while(st <= dr)
        if(a[mid] < val) st = mid+1;
            else dr = mid-1;
    return st + 1;
}

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

    for(i=0; i<N; ++i) a[i] = (ll) lim * A[i] + i;
    for(i=0; i<Q; ++i) val[i] = (ll) lim * V[i] + X[i];

    vector<ll> vals;
    for(i=0; i<N; ++i) vals.push_back(a[i]);
    for(i=0; i<Q; ++i) vals.push_back(val[i]);
    sort(vals.begin(), vals.end());

    int cnt = vals.size();
    aint.init(1, 1, cnt);

    for(i=0; i<N; ++i)
    {
        int pos = Search(vals, (a[i]));
        aint.add(1, 1, cnt, pos, pos, +inf+i);
        aint.add(1, 1, cnt, 1, pos, +1);
    }

    vector<int> answer(Q);
    for(i=0; i<Q; ++i)
    {
        int pos = Search(vals, a[X[i]]);
        aint.add(1, 1, cnt, 1, pos, -1);
        aint.add(1, 1, cnt, pos, pos, -inf-X[i]);

        a[X[i]] = val[i];
        int act = Search(vals, val[i]);
        aint.add(1, 1, cnt, act, act, +inf+X[i]);
        aint.add(1, 1, cnt, 1, act, 1);

        answer[i] = aint.query() - N;
    }
    return answer;
}

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