Submission #894181

#	Time	Username	Problem	Language	Result	Execution time	Memory
894181		vovik	Bubble Sort 2 (JOI18_bubblesort2)	C++98	100 / 100	2111 ms	41632 KiB

bubblesort2

#include <bits/stdc++.h>
 
std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V);
 
struct node {
    std::pair<int, int> x;
    int y = rand();
    int L = 0, R = 0;
    int sz = 1;
    int cost = -1e9;
};
 
const int N = 1e6 + 5;
node t[N];
int cur = 0;
 
void pull(int v) {
    t[v].sz = t[t[v].L].sz + t[t[v].R].sz + 1;
    t[v].cost = std::max({t[t[v].L].cost, t[v].x.second - t[t[v].L].sz, t[t[v].R].cost - t[t[v].L].sz - 1});
}
 
int merge(int v, int u) {
    if (!v || !u) return v | u;
    if (t[v].y > t[u].y) return t[v].R = merge(t[v].R, u), pull(v), v;
    return pull(t[u].L = merge(v, t[u].L)), pull(u), u;
}
 
std::pair<int, int> split(int v, std::pair<int, int> x) {
    if (!v) return {v, v};
    if (t[v].x <= x) {
        auto [a, b] = split(t[v].R, x);
        return t[v].R = a, pull(v), std::pair<int, int>{v, b};
    }
    auto [a, b] = split(t[v].L, x);
    return t[v].L = b, pull(v), std::pair<int, int>{a, v};
}
 
void add(int&v, std::pair<int, int> x) {
    auto [a, b] = split(v, x);
    t[++cur].x = x;
    pull(cur);
    v = merge(merge(a, cur), b);
}
 
void del(int&v, std::pair<int, int> x) {
    auto [a, b] = split(v, x);
    auto [y, z] = split(a, {x.first, x.second - 1});
    v = merge(y, b);
}
 
std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V) {
    t[0].sz = 0;
    std::vector<int> ans(X.size());
    int v = 0;
    for (int i = 0; i < A.size(); ++i) add(v, {A[i], i});
    for (int i = 0; i < X.size(); ++i) del(v, {A[X[i]], X[i]}), A[X[i]] = V[i], add(v, {A[X[i]], X[i]}), ans[i] = t[v].cost;
    return ans;
}
 

Compilation message (stderr)

bubblesort2.cpp: In function 'std::pair<int, int> split(int, std::pair<int, int>)':
bubblesort2.cpp:31:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   31 |         auto [a, b] = split(t[v].R, x);
      |              ^
bubblesort2.cpp:34:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   34 |     auto [a, b] = split(t[v].L, x);
      |          ^
bubblesort2.cpp: In function 'void add(int&, std::pair<int, int>)':
bubblesort2.cpp:39:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   39 |     auto [a, b] = split(v, x);
      |          ^
bubblesort2.cpp: In function 'void del(int&, std::pair<int, int>)':
bubblesort2.cpp:46:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |     auto [a, b] = split(v, x);
      |          ^
bubblesort2.cpp:47:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   47 |     auto [y, z] = split(a, {x.first, x.second - 1});
      |          ^
bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:55:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |     for (int i = 0; i < A.size(); ++i) add(v, {A[i], i});
      |                     ~~^~~~~~~~~~
bubblesort2.cpp:56:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for (int i = 0; i < X.size(); ++i) del(v, {A[X[i]], X[i]}), A[X[i]] = V[i], add(v, {A[X[i]], X[i]}), ans[i] = t[v].cost;
      |                     ~~^~~~~~~~~~

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