제출 #1270957

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270957		giaminh2211	Bubble Sort 2 (JOI18_bubblesort2)	C++20	100 / 100	1251 ms	59340 KiB

bubblesort2

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

#define mp make_pair

using namespace std;
using ll=long long;

const int N=1e6+13;

struct Segtree{
    int st[N << 2];
    int lazy[N << 2];

    void fix(int id, int l, int r){
        st[id] += lazy[id];
        if(l!=r){
            lazy[id << 1] += lazy[id];
            lazy[id << 1 | 1] += lazy[id];
        }
        lazy[id]=0;
    }

    void update(int id, int l, int r, int u, int v, int val){
        fix(id, l, r);
        if(l > v || r < u) return;
        if(u<=l && r<=v){
            lazy[id] += val;
            fix(id, l, r);
            return;
        }
        int mid=l+r >> 1;
        update(id << 1, l, mid, u, v, val);
        update(id << 1 | 1, mid+1, r, u, v, val);
        st[id]=max(st[id << 1], st[id << 1 | 1]);
    }
    
    int get(int id, int l, int r, int u){
    	fix(id, l, r);
    	if(l > u || r < u) return -1e9;
    	if(l==r) return st[id];
    	int mid=l+r  >> 1;
    	int get1=get(id << 1, l, mid, u);
    	int get2=get(id << 1 | 1, mid+1, r, u);
    	return max(get1, get2);
    }
} st;

int n, q;
int a[N];
vector<pair<int, int>> vt;
int x[N], v[N];
int res[N];

void scan(){
    cin >> n >> q;
    for(int i=0; i<n; i++){
        cin >> a[i];
        vt.emplace_back(a[i], i);
    }
    for(int i=0; i<q; i++){
        cin >> x[i] >> v[i];
        vt.emplace_back(v[i], x[i]);
    }
    sort(begin(vt), end(vt));
    for(int i=0; i<n; i++){
        a[i]=upper_bound(begin(vt), end(vt), mp(a[i], i))-begin(vt);
    }
    for(int i=0; i<q; i++){
        v[i]=upper_bound(begin(vt), end(vt), mp(v[i], x[i]))-begin(vt);
    }
}

void upd(int id, int val){
    st.update(1, 1, n+q, a[id], a[id], id*val);
    st.update(1, 1, n+q, a[id]+1, n+q, -val);
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> VQ) {
    n = (int)A.size();
    q = (int)X.size();

    vt.clear(); vt.reserve(n + q);
    for (int i = 0; i < n; ++i) {
        a[i] = A[i];
        vt.emplace_back(a[i], i);
    }
    for (int i = 0; i < q; ++i) {
        x[i] = X[i];               
        v[i] = VQ[i];
        vt.emplace_back(v[i], x[i]);
    }

    sort(begin(vt), end(vt));
    for (int i = 0; i < n; ++i) {
        a[i] = int(upper_bound(begin(vt), end(vt), mp(A[i], i)) - begin(vt));
    }
    for (int i = 0; i < q; ++i) {
        v[i] = int(upper_bound(begin(vt), end(vt), mp(VQ[i], x[i])) - begin(vt));
    }

    memset(st.st, 0, sizeof(st.st));
    memset(st.lazy, 0, sizeof(st.lazy));

    auto do_upd = [&](int id, int val) {
        st.update(1, 1, n + q, a[id], a[id], id * val);
        st.update(1, 1, n + q, a[id] + 1, n + q, -val);
    };

    for (int i = 0; i < n; ++i) do_upd(i, 1);

    vector<int> S(q);
    for (int i = 0; i < q; ++i) {
        do_upd(x[i], -1);
        a[x[i]] = v[i];
        do_upd(x[i], 1);
        S[i] = st.st[1]; 
    }
    return S;
}

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