Submission #894176

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
894176	2023-12-28T02:17:31 Z	vovik	Bubble Sort 2 (JOI18_bubblesort2)	C++	Compilation error	0 ms	0 KB

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{v, b};
    }
    auto [a, b] = split(t[v].L, x);
    return t[v].L = b, pull(v), std::pair{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;
}
 
 
#ifdef __APPLE__
#include <cstdio>
#include <cstdlib>
#include <vector>
 
int readInt() {
    int i;
    if (scanf("%d", &i) != 1) {
        fprintf(stderr, "Error while reading input\n");
        exit(1);
    }
    return i;
}
 
int main() {
    int N, Q;
    N = readInt();
    Q = readInt();
 
    std::vector<int> A(N);
    for (int i = 0; i < N; i++)
        A[i] = readInt();
 
    std::vector<int> X(Q), V(Q);
    for (int j = 0; j < Q; j++) {
        X[j] = readInt();
        V[j] = readInt();
    }
 
    std::vector<int> res = countScans(A, X, V);
 
    for (int j = 0; j < int(res.size()); j++)
        printf("%d\n", res[j]);
}
#endif

Compilation message

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:32:46: error: missing template arguments before '{' token
   32 |         return t[v].R = a, pull(v), std::pair{v, b};
      |                                              ^
bubblesort2.cpp:32:46: error: expected ';' before '{' token
   32 |         return t[v].R = a, pull(v), std::pair{v, b};
      |                                              ^
      |                                              ;
bubblesort2.cpp:32:47: warning: left operand of comma operator has no effect [-Wunused-value]
   32 |         return t[v].R = a, pull(v), std::pair{v, b};
      |                                               ^
bubblesort2.cpp:32:51: error: expected ';' before '}' token
   32 |         return t[v].R = a, pull(v), std::pair{v, b};
      |                                                   ^
      |                                                   ;
bubblesort2.cpp:32:50: warning: right operand of comma operator has no effect [-Wunused-value]
   32 |         return t[v].R = a, pull(v), std::pair{v, b};
      |                                                  ^
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:35:42: error: missing template arguments before '{' token
   35 |     return t[v].L = b, pull(v), std::pair{a, v};
      |                                          ^
bubblesort2.cpp:35:42: error: expected ';' before '{' token
   35 |     return t[v].L = b, pull(v), std::pair{a, v};
      |                                          ^
      |                                          ;
bubblesort2.cpp:35:43: warning: left operand of comma operator has no effect [-Wunused-value]
   35 |     return t[v].L = b, pull(v), std::pair{a, v};
      |                                           ^
bubblesort2.cpp:35:47: error: expected ';' before '}' token
   35 |     return t[v].L = b, pull(v), std::pair{a, v};
      |                                               ^
      |                                               ;
bubblesort2.cpp:35:47: warning: right operand of comma operator has no effect [-Wunused-value]
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;
      |                     ~~^~~~~~~~~~