Submission #444009

#	Time	Username	Problem	Language	Result	Execution time	Memory
444009		SirCovidThe19th	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	2735 ms	53372 KiB

bubblesort2

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

#define vi vector<int>
#define all(x) x.begin(), x.end()

const int mx = (1<<20); int seg[mx*2], lz[mx*2]; vector<pair<int, int>> mp; vi ans;

void upd(int x, int y, int v, int l = 0, int r = mp.size()-1, int i = 1){
    if (l > y or r < x) return;
    if (l >= x and r <= y){ seg[i] += v, lz[i] += v; return; }
    int m = (l+r)/2; upd(x, y, v, l, m, i*2); upd(x, y, v, m+1, r, i*2+1);
    seg[i] = max(seg[i*2], seg[i*2+1])+lz[i];
}
vi countScans(vi A, vi X, vi V){
    for (int i = 0; i < A.size(); i++) mp.push_back({A[i], i});
    for (int i = 0; i < X.size(); i++) mp.push_back({V[i], X[i]});
    sort(all(mp)); mp.erase(unique(all(mp)), mp.end());
    auto lb = [&](pair<int, int> x){ return lower_bound(all(mp), x)-mp.begin(); };    
    auto app = [&](int i, int sgn){// i - elems less/eq
        int p = lb({A[i], i}); upd(p, p, (i+1)*sgn);
        p = lb({A[i], -1}); upd(p, mp.size()-1, -sgn);
    };for (int i = 0; i < A.size(); i++) app(i, 1);
    for (int i = 0; i < X.size(); i++){
        app(X[i], -1); A[X[i]] = V[i]; app(X[i], 1);
        ans.push_back(seg[1]);
    }return ans;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:16:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |     for (int i = 0; i < A.size(); i++) mp.push_back({A[i], i});
      |                     ~~^~~~~~~~~~
bubblesort2.cpp:17:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     for (int i = 0; i < X.size(); i++) mp.push_back({V[i], X[i]});
      |                     ~~^~~~~~~~~~
bubblesort2.cpp:23:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     };for (int i = 0; i < A.size(); i++) app(i, 1);
      |                       ~~^~~~~~~~~~
bubblesort2.cpp:24:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (int i = 0; i < X.size(); i++){
      |                     ~~^~~~~~~~~~

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