Submission #392076

#	Time	Username	Problem	Language	Result	Execution time	Memory
392076		muhammad_hokimiyon	Bubble Sort 2 (JOI18_bubblesort2)	C++14	38 / 100	73 ms	3100 KiB

bubblesort2

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

using namespace std;

const int maxn = 1000500;

int G;
int a[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] += val;
        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<pair<int, int>> g;
	for(int i = 0; i < Q; i++){
        g.push_back({V[i], -(i + 1)});
	}
	for(int i = 0; i < n; i++){
        g.push_back({A[i], i});
	}
	map<int, int> m;
	sort(g.begin(), g.end());
	for(int i = 0; i < (int)g.size(); i++){
        if(g[i].second >= 0){
            A[g[i].second] = ++G;
        }else{
            V[-g[i].second - 1] = ++G;
        }
	}
	for(int i = 0; i < n; i++){
        upd(1, 1, G, A[i], G, -1);
        upd(1, 1, G, A[i], i);
	}
    for(int i = 0; i < Q; i++){
        upd(1, 1, G, A[X[i]], -X[i]);
        upd(1, 1, G, A[X[i]], G, 1);
        A[X[i]] = V[i];
        upd(1, 1, G, A[X[i]], X[i]);
        upd(1, 1, G, A[X[i]], G, -1);
        answer.push_back(t[1] + 1);
    }
    return answer;
}

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