oj.uz

Submission #224814

# Submission time Handle Problem Language Result Execution time Memory
224814 2020-04-18T23:16:43 Z Bruteforceman Bubble Sort 2 (JOI18_bubblesort2) C++11
0 / 100
 44 ms 48896 KB 
#include "bits/stdc++.h"
#include "bubblesort2.h"
using namespace std;
const int maxn = 1000010;
int t[4 * maxn], prop[4 * maxn], opt[maxn], pre[maxn];
set <int> cont[maxn];
int idx;

void pushdown(int c) {
    if(!prop[c]) return ;
    int l = c << 1;
    int r = l + 1;
    t[l] += prop[c]; t[r] += prop[c];
    prop[l] += prop[c]; prop[r] += prop[c];
    prop[c] = 0;
}
void add(int x, int y, int val, int c = 1, int b = 1, int e = idx) {
    if(x <= b && e <= y) {
        t[c] += val;
        prop[c] += val;
        return ;
    }
    if(y < b || e < x) return ;
    pushdown(c);
    int m = (b + e) >> 1;
    int l = c << 1;
    int r = l + 1;
    add(x, y, val, l, b, m);
    add(x, y, val, r, m + 1, e);
    t[c] = max(t[l], t[r]);
}
inline int getMin() {
    return t[1];
}
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
    vector <int> answer (X.size());
    map <int, int> cmp;
    for(int i = 0; i < A.size(); i++) cmp[A[i]];
    for(int i = 0; i < V.size(); i++) cmp[V[i]];
    idx = 0;
    for(auto &i : cmp) {
        i.second = ++idx;
        pre[idx] = t[idx] = opt[idx] = 0;
        cont[idx].clear();
    }
    for(int i = 0; i < A.size(); i++) {
        A[i] = cmp[A[i]];
        pre[A[i]] += 1;
        opt[A[i]] = i + 1;
        cont[A[i]].insert(i + 1);
    }
    for(int i = 1; i <= idx; i++) {
        pre[i] += pre[i - 1];
        t[i] = opt[i] - pre[i];
        cont[i].insert(0);
    }
    for(int i = 0; i < V.size(); i++) {
        int x = X[i];
        int tmp;
        V[i] = cmp[V[i]];

        add(A[x], idx, 1);
        cont[A[x]].erase(x + 1);
        tmp = opt[A[x]];
        opt[A[x]] = *cont[A[x]].rbegin();
        add(A[x], A[x], opt[A[x]] - tmp);


        A[x] = V[i];
        add(A[x], idx, -1);
        cont[A[x]].insert(x + 1);
        tmp = opt[A[x]];
        opt[A[x]] = *cont[A[x]].rbegin();
        add(A[x], A[x], opt[A[x]] - tmp);
        answer[i] = getMin();
    }
    return answer;
}

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:38:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < A.size(); i++) cmp[A[i]];
                    ~~^~~~~~~~~~
bubblesort2.cpp:39:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < V.size(); i++) cmp[V[i]];
                    ~~^~~~~~~~~~
bubblesort2.cpp:46:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < A.size(); i++) {
                    ~~^~~~~~~~~~
bubblesort2.cpp:57:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0; i < V.size(); i++) {
                    ~~^~~~~~~~~~

Subtask #1
0 / 17.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

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