Submission #925330

#	Time	Username	Problem	Language	Result	Execution time	Memory
925330		boris_mihov	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	1567 ms	117416 KiB

bubblesort2

#include "bubblesort2.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <stack>

// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>

// using namespace __gnu_pbds;

// template <typename T>
// using OSet = tree <T, null_type, std::less <T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long llong;
const int MAXN = 500000 + 10;
const int MAXNUM = 1e6 + 10;
const int INF  = 1e9;

int n, q;
int cntDiff;
struct SegmentTree
{
    struct Node
    {
        int max;
        int val;
        int lazy;
        bool isActive;
    
        Node()
        {
            max = lazy = isActive = 0;
        }

        friend Node operator + (const Node &left, const Node &right)
        {
            Node res;
            res.max = std::max(left.max, right.max);
            res.isActive = left.isActive | right.isActive;
            return res;
        }
    };

    Node tree[4*MAXNUM];
    void push(int node, int l, int r)
    {
        if (tree[node].lazy == 0)
        {
            return;
        }
        
        if (tree[node].isActive)
        {
            tree[node].max += tree[node].lazy;
        }
    
        if (l == r)
        {
            tree[node].val += tree[node].lazy;
        } else
        {
            tree[2*node].lazy += tree[node].lazy;
            tree[2*node + 1].lazy += tree[node].lazy;
        }

        tree[node].lazy = 0;
    }

    void updateActive(int l, int r, int node, int queryPos, int queryIdx)
    {
        push(node, l, r);
        if (queryPos < l || r < queryPos)
        {
            return;
        }

        if (l == r)
        {
            if (tree[node].isActive)
            {
                tree[node].isActive = 0;
                tree[node].max = 0;
            } else
            {
                tree[node].isActive = true;
                tree[node].max = queryIdx - 1 + tree[node].val;
            }

            return;
        }

        int mid = (l + r) / 2;
        updateActive(l, mid, 2*node, queryPos, queryIdx);
        updateActive(mid + 1, r, 2*node + 1, queryPos, queryIdx);
        tree[node] = tree[2*node] + tree[2*node + 1];
    }

    void updateRange(int l, int r, int node, int queryL, int queryR, int queryVal)
    {
        push(node, l, r);
        if (queryR < l || r < queryL)
        {
            return;
        }

        if (queryL <= l && r <= queryR)
        {
            tree[node].lazy += queryVal;
            push(node, l, r);
            return;
        }

        int mid = (l + r) / 2;
        updateRange(l, mid, 2*node, queryL, queryR, queryVal);
        updateRange(mid + 1, r, 2*node + 1, queryL, queryR, queryVal);
        tree[node] = tree[2*node] + tree[2*node + 1];
    }

    int query()
    {
        return tree[1].max;
    }

    void add(int idx, int val)
    {
        updateActive(1, cntDiff, 1, val, idx);
        if (val < cntDiff) updateRange(1, cntDiff, 1, val + 1, cntDiff, -1);
    }

    void remove(int idx, int val)
    {
        updateActive(1, cntDiff, 1, val, idx);
        if (val < cntDiff) updateRange(1, cntDiff, 1, val + 1, cntDiff, 1);
    }
};

int in[MAXN];
int pos[MAXN];
int order[MAXN];
int updatePos[MAXN];
llong updateVal[MAXN];
SegmentTree tree;
llong a[MAXN];

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

    std::vector <std::pair <llong, std::pair <int,bool>>> v;
    for (int i = 1 ; i <= n ; ++i)
    {
        a[i] = 1LL * n * A[i - 1] + i;
        v.push_back({a[i], {i, true}});
    }

    for (int i = 0 ; i < q ; ++i)
    {
        updatePos[i + 1] = X[i] + 1; 
        updateVal[i + 1] = 1LL * n * V[i] + updatePos[i + 1];    
        v.push_back({updateVal[i + 1], {i + 1, false}});
    }

    std::sort(v.begin(), v.end());
    for (int i = 0 ; i < v.size() ; ++i)
    {
        cntDiff += (i == 0 || v[i].first > v[i - 1].first);
        if (v[i].second.second) a[v[i].second.first] = cntDiff;
        else updateVal[v[i].second.first] = cntDiff;
    }
    
    for (int i = 1 ; i <= n ; ++i)
    {
        tree.add(i, a[i]);
    }

    std::vector <int> answer(q, 0);
    for (int i = 1 ; i <= q ; ++i)
    {
        tree.remove(updatePos[i], a[updatePos[i]]);
        a[updatePos[i]] = updateVal[i];
        tree.add(updatePos[i], a[updatePos[i]]);
        answer[i - 1] = tree.query();
    }

    return answer;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:168:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, bool> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  168 |     for (int i = 0 ; i < v.size() ; ++i)
      |                      ~~^~~~~~~~~~

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