Submission #1118288

#	Time	Username	Problem	Language	Result	Execution time	Memory
1118288		patgra	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	3754 ms	114456 KiB

bubblesort2

#include <bits/stdc++.h>
#include "bubblesort2.h"
 
#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))
 
#define ll long long
 
constexpr bool dbg = false;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl
 
constexpr ll maxn = 5e5 + 7, treeBase = 1 << 20, inf = 1e18 + 7;
std::map<std::pair<int, int>, int> map;
int n, q;
ll tree[2 * treeBase], lazy[2 * treeBase];
 
void fixNode(int v) {
    // DC << "Fixin " << v << " -> ";
    tree[v] = std::max(tree[2 * v] + lazy[2 * v], tree[2 * v + 1] + lazy[2 * v + 1]);
    // DC << tree[v] << eol;
}
void add(int l, int r, ll x) {
    DC << "add " << l << ' ' << r << ' ' << x << eol;
    l += treeBase; r += treeBase;
    lazy[l] += x;
    if (l != r) lazy[r] += x;
    while (l / 2 != r / 2) {
        if (l % 2 == 0) lazy[l + 1] += x;
        if (r % 2 == 1) lazy[r - 1] += x;
        l /= 2; r /= 2;
        fixNode(l); fixNode(r);
    }
    l /= 2;
    while (l) fixNode(l), l /= 2;
}
int query() {
    DC << "query = " << tree[1] + lazy[1] << eol << eol;
    return tree[1] + lazy[1];
}
 
void mapValues(std::vector<int> &A, std::vector<int> &V, std::vector<int> &X) {
    rep(i, 0, n) map[{A[i], i}] = 1;
    rep(i, 0, q) map[{V[i], X[i]}] = 1;
    int cnt = 0;
    repIn2(k, v, map) v = ++cnt;
    DEBUG {
        DC << "map: " << eol;
        repIn2(k, v, map) DC << " {" << k.first << ' ' << k.second << "} => " << v << eol;
    }
}
 
void init(std::vector<int> &A) {
    tree[treeBase] = -2 * inf;
    repIn2(k, ni, map) {
        const auto& [val, index] = k;
        add(ni, ni, -inf -(n - index - 1));
    }
    rep(i, 0, n) {
        int mapped = map[{A[i], i}];
        int firstSmaller = map.lower_bound({A[i], -1}) -> second - 1;
        add(mapped, mapped, inf);
        add(0, firstSmaller, 1);
    }
}
 
void makeChange(int &index, int &val, std::vector<int> &A) {
    DC << "change " << index << ' ' << val << eol;
    int mapped = map[{A[index], index}];
    int firstSmaller = map.lower_bound({A[index], -1}) -> second - 1;
    add(mapped, mapped, -inf);
    add(0, firstSmaller, -1);
    A[index] = val;
    mapped = map[{A[index], index}];
    firstSmaller = map.lower_bound({A[index], -1}) -> second - 1;
    add(mapped, mapped, inf);
    add(0, firstSmaller, 1);
    DC << eol << eol;
}
 
std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V) {
    n = A.size(), q = X.size();
    std::vector<int> ans(q);
    mapValues(A, V, X);
    init(A);
    rep(i, 0, q) makeChange(X[i], V[i], A), ans[i] = query();
    return ans;
}
 
/*
4 2
1 2 3 4
0 3
2 1
*/

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