Submission #1113466

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113466		jkb_gryz	Bubble Sort 2 (JOI18_bubblesort2)	C++14	0 / 100	1578 ms	4936 KiB

bubblesort2

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

using namespace std;

const int base = 1<<20;
int tree[base<<1];

void update(int v, int x){
    v += base;
    tree[v] += x;
    v /= 2;

    while(v){
        tree[v] = tree[2*v] + tree[2*v+1];
        v /= 2;
    }
}

int query(int a, int b){
    a += base - 1;
    b += base + 1;

    int res = 0;
    while(a/2 != b/2){
        if(a % 2 == 0) res += tree[a+1];
        if(b % 2 == 1) res += tree[b-1];
        
        a/=2;
        b/=2;
    }

    return res;
}

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

    map<long long, int> skalowanie;
    for(auto i : A){
        skalowanie[i] = 0;
    }
    for(auto i : V){
        skalowanie[i] = 0;
    }
    int id = 0;

    for(auto &i : skalowanie) i.second = ++id;

    for(auto i : A) update(skalowanie[i], 1);

    for(int i = 0; i < Q; ++i){
        update(skalowanie[A[X[i]]], -1);
        A[X[i]] = V[i];
        update(skalowanie[X[i]], 1);

        int curRes = 0;
        for(int j = 0; j < n; ++j){
            curRes = max(curRes, query(skalowanie[i]+1, id) - (n - j - 1));
        }
        res[i] = curRes;
    }

	return res;
}

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