Submission #1219855

#	Time	Username	Problem	Language	Result	Execution time	Memory
1219855		akamizane	Bubble Sort 2 (JOI18_bubblesort2)	C++20	100 / 100	1949 ms	166592 KiB

bubblesort2

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

#ifdef LOCAL
#include <debug.h>
#else
#define debug(...) 42
#endif

// #define int long long

const int maxn = 1e6 + 5;

struct SegmentTree{
    int n;
    vector<int> a, lazy;
 
    SegmentTree(int _n){
        n = _n;
        a.resize(n * 4 + 4); lazy.resize(n * 4 + 4);
    }
 
    void update_node(int i, int v){
        a[i] += v;
        lazy[i] += v;
    }
 
    void down(int id){
        update_node(id * 2, lazy[id]); update_node(id * 2 + 1, lazy[id]);
        lazy[id] = 0;
    }
 
    void update(int u, int v, int val){if (u <= v) update(u, v, val, 0, n-1, 1);}
    void update(int u, int v, int val, int l, int r, int id){
        if (u <= l && r <= v){
            update_node(id, val);
            return;
        }
        if (lazy[id]) down(id);
        int mid = (l + r) >> 1;
        if (u <= mid) update(u, v, val, l, mid, id * 2);
        if (v > mid) update(u, v, val, mid + 1, r, id * 2 + 1);
        a[id] = max(a[id * 2], a[id * 2 + 1]);
    }
 
    int get(){return a[1];}
 
};

set<int> pos[maxn];

vector<int> countScans(vector<int> a,vector<int> x,vector<int> v){
   int n = a.size();
   int q = v.size();
   for (auto& x : a) cin >> x;
   for (auto& u : x) cin >> u;
   for (auto& x : v) cin >> x;
   debug(a, x, v);
   vector<int> b = a;
   for (auto x : v) b.push_back(x);
   sort(b.begin(), b.end());
   b.erase(unique(b.begin(), b.end()), b.end());
   for (auto& x : a) x = lower_bound(b.begin(), b.end(), x) - b.begin(); 
   for (auto& x : v) x = lower_bound(b.begin(), b.end(), x) - b.begin(); 
   int m = b.size(); 
   for (int i = 0; i < n; i++){
      pos[a[i]].insert(i);
   }
   SegmentTree seg(m);
   for (int i = 0; i < m; i++){
      pos[i].insert(-1e9);
      seg.update(i, i, *pos[i].rbegin());
      seg.update(i, m - 1, -(pos[i].size() - 1));
   }
   vector<int> ans(q);
   debug(ans);
   for (int i = 0; i < q; i++){
      int idx = x[i], val = v[i];
      seg.update(a[idx], m - 1, 1);
      seg.update(a[idx], a[idx], -*pos[a[idx]].rbegin());
      pos[a[idx]].erase(idx);
      seg.update(a[idx], a[idx], *pos[a[idx]].rbegin());
      
      a[idx] = val;
      seg.update(a[idx], m - 1, -1);
      seg.update(a[idx], a[idx], -*pos[a[idx]].rbegin());
      pos[a[idx]].insert(idx);
      seg.update(a[idx], a[idx], *pos[a[idx]].rbegin());
      ans[i] = seg.get() + 1;
      debug(a);
   }
   return ans;
}

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