Submission #392207

#	Time	Username	Problem	Language	Result	Execution time	Memory
392207		muhammad_hokimiyon	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	4412 ms	314096 KiB

bubblesort2

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

using namespace std;

const int maxn = 1000500;

int G;
int a[maxn];
set<int> s[4 * maxn];
int f[4 * maxn];
int t[4 * maxn];
int lz[4 * maxn];

void push(int x)
{
    lz[x + x] += lz[x];
    lz[x + x + 1] += lz[x];
    t[x + x] += lz[x];
    t[x + x + 1] += lz[x];
    lz[x] = 0;
}

void upd(int x, int l, int r, int p, int val)
{
    if(l == r){
        t[x] -= f[x];
        if(val > 0)s[x].insert(val);
        else s[x].erase(-val);
        if(s[x].empty())f[x] = 0;
        else f[x] = *--s[x].end();
        t[x] += f[x];
        return;
    }
    push(x);
    int m = (l + r) / 2;
    if(p <= m)upd(x + x, l, m, p, val);
    else upd(x + x + 1, m + 1, r, p, val);
    t[x] = max(t[x + x], t[x + x + 1]);
}

void upd(int x, int l, int r, int tl, int tr, int val)
{
    if(tl > tr)return;
    if(l == tl && r == tr){
        t[x] += val;
        lz[x] += val;
        return;
    }
    int m = (l + r) / 2;
    push(x);
    upd(x + x, l, m, tl, min(tr, m), val);
    upd(x + x + 1, m + 1, r, max(tl, m + 1), tr, val);
    t[x] = max(t[x + x], t[x + x + 1]);
}

vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
	int Q=X.size();
	vector<int> answer;
	int n = (int)A.size();
	vector<int> g;
	for(int i = 0; i < Q; i++){
        g.push_back(V[i]);
	}
	for(int i = 0; i < n; i++){
        g.push_back(A[i]);
	}
	map<int, int> m;
	sort(g.begin(), g.end());
    for(auto x : g){
        if(m.find(x) == m.end()){
            m[x] = ++G;
        }
    }
    for(int i = 0; i < n; i++){
        A[i] = m[A[i]];
        upd(1, 1, G, A[i], G, -1);
        upd(1, 1, G, A[i], i + 1);
	}
    for(int i = 0; i < Q; i++){
        V[i] = m[V[i]];
        upd(1, 1, G, A[X[i]], -(X[i] + 1));
        upd(1, 1, G, A[X[i]], G, 1);
        A[X[i]] = V[i];
        upd(1, 1, G, A[X[i]], (X[i] + 1));
        upd(1, 1, G, A[X[i]], G, -1);
        answer.push_back(t[1]);
    }
    return answer;
}

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