Submission #153584

#	Time	Username	Problem	Language	Result	Execution time	Memory
153584		karma	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	3968 ms	99680 KiB

bubblesort2

/*
   (1)(number x: x < i && a[x] > a[i])
   (2)(i - number x: a[x] < a[i])
   (1) >= (2) -> res = max((2))
*/
#include "bubblesort2.h"
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
#define ll      long long
#define pb      emplace_back
#define mp      make_pair

using namespace std;

const int N = int(1e5) + 2;
const int inf = int(1e8);
typedef pair<int, int> pii;

struct TSegment {
     vector<int> st, lazy, l, h;
     void Build(int x, int low, int high) {
          l[x] = low, h[x] = high;
          if(l[x] == h[x]) return;
          int mid = (low + high) >> 1;
          Build(x << 1, low, mid);
          Build(x << 1 | 1, mid + 1, high);
     }
     void Init(int n) { ++n;
         st.resize(n << 2, -inf), lazy.resize(n << 2, 0);
         l.resize(n << 2, 0), h.resize(n << 2, 0);
         Build(1, 1, n - 1);
     }
     void Down(int x) {
         if(!lazy[x]) return;
         if(l[x] < h[x]) {
             st[x << 1] += lazy[x];
             st[x << 1 | 1] += lazy[x];
             lazy[x << 1] += lazy[x];
             lazy[x << 1 | 1] += lazy[x];
         }
         lazy[x] = 0;
     }
     void Update(int x, int low, int high, int val) {
          Down(x);
          if(high < low || l[x] > high || h[x] < low) return;
          if(low <= l[x] && h[x] <= high) {
             st[x] += val; lazy[x] += val;
             Down(x);
             return;
          }
          Update(x << 1, low, high, val);
          Update(x << 1 | 1, low, high, val);
          st[x] = max(st[x << 1], st[x << 1 | 1]);
     }
     int Query() {Down(1); return st[1];}
} Irene;

vector<pii> v;
int sz, p;

void Add(int val, int x) {
     p = lower_bound(v.begin(), v.end(), mp(val, x)) - v.begin() + 1;
     Irene.Update(1, p, p, inf + x);
     Irene.Update(1, p + 1, sz, -1);
}

void Rmv(int val, int x) {
     p = lower_bound(v.begin(), v.end(), mp(val, x)) - v.begin() + 1;
     Irene.Update(1, p, p, -inf - x);
     Irene.Update(1, p + 1, sz, 1);
}

vector<int> countScans(vector<int> a, vector<int> qx, vector<int> qv) {
      int n = a.size(), q = qx.size(); vector<int> res;
      for(int i = 0; i < n; ++i) v.pb(a[i], i);
      for(int i = 0; i < q; ++i) v.pb(qv[i], qx[i]);
      sort(v.begin(), v.end());
      v.erase(unique(v.begin(), v.end()));
      Irene.Init(sz = v.size());
      for(int i = 0; i < n; ++i) Add(a[i], i);
      for(int i = 0; i < q; ++i) {
         Rmv(a[qx[i]], qx[i]); Add(qv[i], qx[i]);
         a[qx[i]] = qv[i];
         res.pb(Irene.Query());
      }
      return res;
}

//int main() {
//    ios_base::sync_with_stdio(0);
//    cin.tie(0), cout.tie(0);
//    if(fopen("test.inp", "r")) {
//        freopen("test.inp", "r", stdin);
//        freopen("test.out", "w", stdout);
//    }
//    int n, q; vector<int> a, v, x, res;
//    cin >> n >> q; a.resize(n);
//    for(int& x: a) cin >> x;
//    x.resize(q), v.resize(q);
//    for(int i = 0; i < q; ++i) cin >> x[i] >> v[i];
//    res = countScans(a, x, v);
//    for(int ans: res) cout << ans << '\n';
//}

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