oj.uz

답안 #522870

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
522870 2022-02-06T08:21:29 Z CraniXort Bubble Sort 2 (JOI18_bubblesort2) C++17
0 / 100
 18 ms 3248 KB 
#include <bits/stdc++.h>

std::ifstream fin("bubble.in");
std::ofstream fout("bubble.out");

struct Element {
    int value, pos, index, norm;

    static bool sortByValue(Element &a, Element &b) {
        if(a.value == b.value)
            return a.pos < b.pos;
        return a.value < b.value;
    }

    static bool sortByIndex(Element &a, Element &b) {
        return a.index < b.index;
    }
    void print() {
        fout << value << ' ' << pos << ' ' << index << ' ' << norm << '\n';
    }
};

class SegmTree {
    int size;
    std::vector <int> lazy, min;

    void propagate(int node) {
        lazy[2*node+1] += lazy[node];
        lazy[2*node+2] += lazy[node];
        min[2*node+1] += lazy[node];
        min[2*node+2] += lazy[node];
        lazy[node] = 0;
    }

    void set(int node, int left, int right, int pos, int value) {
        if(left == right) {
            min[node] = value;
            return;
        }
            

        propagate(node);

        int mid = (left + right) / 2;
        if(mid >= pos)
            set(2*node+1, left, mid, pos, value);
        else
            set(2*node+2, mid+1, right, pos, value);

        min[node] = std::min(min[2*node+1], min[2*node+2]);
    }

    void update(int node, int left, int right, int from, int to, int value) {
        if(left > to or right < from)
            return;

        propagate(node);

        if(from <= left and right <= to) {
            min[node] += value;
            lazy[node] += value;
            return;
        }

        int mid = (left + right) / 2;
        update(2*node+1, left, mid, from, to, value);
        update(2*node+2, mid+1, right, from, to, value);

        min[node] = std::min(min[2*node+1], min[2*node+2]);
    }

    int query(int node, int left, int right, int from, int to) {
        if(left > to or right < from)
            return 1e9;
        
        if(from <= left and right <= to)
            return min[node];

        propagate(node);

        int mid = (left + right) / 2;
    
        int ans = std::min(query(2*node+1, left, mid, from, to), query(2*node+2, mid+1, right, from, to));

        min[node] = std::min(min[2*node+1], min[2*node+2]);

        return ans;

    }


    public:
    SegmTree(int n) {
        size = 1;
        while(size < n)
            size *= 2;
        
        lazy.resize(2 * size);
        min.resize(2 * size);

        std::fill(min.begin(), min.end(), 1e9);
    }

    int getMin() {
        return min[0];
    }

    int querySegm(int left, int right) {
        return query(0, 0, size-1, left, right);
    }

    void updateSegm(int left, int right, int value) {
        update(0, 0, size-1, left, right, value);
    }

    void setSegm(int pos, int value) {
        set(0, 0, size-1, pos, value);
    }
};

class Bit {
    int size;
    std::vector <int> bit;
    public:

    Bit(int n) {
        size = n + 1;
        bit.resize(size + 1);
    }

    void update(int pos, int value) {
        pos ++;
        while(pos <= size) {
            bit[pos] += value;
            pos = pos + (pos & -pos);
        }
    }
    int query(int pos) {
        pos ++;
        int ans = 0;
        while(pos > 0) {
            ans += bit[pos];
            pos = pos - (pos & -pos);
        }
        return ans;
    }
};

std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
    std::vector <int> ans(X.size());

    std::vector <Element> v;
    int n = A.size();
    for(int i = 0, value; i < n; i ++) {
        value = A[i];
        v.push_back({value, i, i, 0});
    }

    int Q = X.size();
    for(int i = 0, value, pos; i < Q; i ++) {
        pos = X[i];
        value = V[i];
        v.push_back({value, pos, n + i, 0});
    }

    std::sort(v.begin(), v.end(), Element::sortByValue);


    for(int i = 1; i < v.size(); i ++) {
        int crt = v[i-1].norm;
        if(!(v[i].value == v[i-1].value and v[i].pos == v[i-1].pos))
            crt ++;
        v[i].norm = crt;
    }

    std::sort(v.begin(), v.end(), Element::sortByIndex);

    SegmTree segm(n+Q);
    Bit bit(n+Q);

    for(int i = 0; i < n; i ++) {
        segm.setSegm(v[i].norm, v[i].pos - i);
        bit.update(v[i].norm, 1);
    }

    for(int i = n; i < n+Q; i ++) {
        int currPos = v[v[i].pos].norm;
        int nextPos = v[i].norm;
        v[v[i].pos].norm = v[i].norm;

        segm.setSegm(nextPos, bit.query(nextPos) - v[i].pos);
        segm.updateSegm(nextPos + 1, n+Q-1, 1);

        segm.updateSegm(currPos + 1, n+Q-1, -1);
        segm.setSegm(currPos, 1e9);

        // fout << -segm.getMin() << '\n';
        ans[i-n] = -segm.getMin();
    }

    return ans;
}

// int main() {
//     int n, Q;
//     fin >> n;
//     std::vector <int> v(n);
//     for(int i = 0; i < n; i ++)
//         fin >> v[i];

//     fin >> Q;
//     std::vector <int> x(Q), val(Q);
//     for(int i = 0; i < Q; i ++) 
//         fin >> x[i] >> val[i];

//     std::vector <int> ans = countScans(v, x, val);

//     for(auto i: ans)
//         fout << i << '\n';



//     return 0;
// }

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:169:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Element>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |     for(int i = 1; i < v.size(); i ++) {
      |                    ~~^~~~~~~~~~

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 588 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 588 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 18 ms 3248 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 588 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -