oj.uz

Submission #1113466

# Submission time Handle Problem Language Result Execution time Memory
1113466 2024-11-16T15:55:21 Z jkb_gryz Bubble Sort 2 (JOI18_bubblesort2) C++14
0 / 100
 1578 ms 4936 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 4688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 4688 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 1578 ms 4936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 4688 KB Output isn't correct
2 Halted 0 ms 0 KB -