Submission #97788

#	Time	Username	Problem	Language	Result	Execution time	Memory
97788		Alexa2001	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	7226 ms	114056 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;

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

    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];

    for(i=0; i<N; ++i) mp[a[i]] = 1;
    for(i=0; i<Q; ++i) mp[val[i]] = 1;
    int cnt = 0;
    for(auto &it : mp) it.second = ++cnt;

    aint.init(1, 1, cnt);

    for(i=0; i<N; ++i)
    {
        int pos = mp[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 = mp[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 = mp[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