제출 #1269296

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1269296		happydavid@aoa	Bubble Sort 2 (JOI18_bubblesort2)	C++20	0 / 100	3155 ms	1436 KiB

bubblesort2

#include <bits/stdc++.h>
#define inf 1000000001
using namespace std;

struct Seg{
    int n;
    vector<int> Tree, A;

    void init(int N, vector<int> a){
        n = N;
        Tree.assign(4*n, inf);
        for(int i = 0; i < N; i++){
            A.push_back(a[i]);
        }
        build(1, 0, n-1);
    }

    void build(int node, int l, int r){
        if(l == r){
            Tree[node] = A[l];
        } else {
            int mid = (l+r) / 2;
            build(2*node, l, mid);
            build(2*node+1, mid+1, r);
            Tree[node] = min(Tree[2*node], Tree[2*node+1]);
        }
    }

    int min_query(int node, int l, int r, int ql, int qr){
        if(qr < l || ql > r ) return inf;
        if(ql <= l && r <= qr){
            return Tree[node];
        }
        int mid = (l+r)/2;
        return min(min_query(2*node, l, mid, ql, qr), min_query(2*node+1, mid+1, r, ql, qr));
    }

    void update(int node, int l, int r, int i, int val){
        if(l == r) Tree[node] = val, A[i] = val;
        else {
            int mid = (l+r) / 2;
            if(i <= mid){
                update(2*node, l, mid, i, val);
            } else {
                update(2*node+1, mid+1, r, i, val);
            }
            Tree[node] = min(Tree[2*node], Tree[2*node+1]);
        }
    }
};

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
    int n = A.size();
    int m = X.size();
    vector<int> answers;
    Seg seg;
    seg.init(n, A);
    for(int q = 0; q < m; q++){
        seg.update(1, 0, n-1, X[q], V[q]);
        int ans = 0;
        for(int i = 0; i < n-1; i++){
            int current_number = seg.A[i];
            int mi = seg.min_query(1, 0, n-1, i+1, n-1);
            if(mi < current_number) ans++;
        }
        answers.push_back(ans);
    }
    return answers;
}
/*
int main(){
    vector<int> A = {1, 2, 3, 4};
    vector<int> X = {0, 2};
    vector<int> V = {3, 1};
    vector<int> result = count_scans(A, X, V);
    for(const int& x : result){
        cout << x << ' ';
    } cout << endl;

    
    return 0;
}
*/

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