Submission #1125463

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125463		ntdaccode	Bubble Sort 2 (JOI18_bubblesort2)	C++17	60 / 100	9090 ms	13200 KiB

bubblesort2

#include<bits/stdc++.h>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back

using namespace std;

typedef pair<int,int> ii;
typedef tuple<int,int,int> tp;

const int M = 5e5 + 10;
const int SIZE = 500;

int n, q, a[M], uu[M], vv[M];
int f[M];

vector<ii> rrh[SIZE + 10];
int id(int i) {
  return (i + SIZE - 1)/SIZE;
}

int get_cnt(int val,int pos)
{
  int ret = 0;
  int bl = id(pos);
  int l = (bl - 1) * SIZE + 1;
  for(int i = 1;i <= bl - 1; i++) {
    ii tmp = {val,pos};
    ret += rrh[i].size() - (upper_bound(rrh[i].begin(), rrh[i].end(), tmp) - rrh[i].begin() );
  }
  for(int i = l;i <= pos - 1; i++) {
    if(a[i] > val) ret++;
  }
  return ret;
}
int t[SIZE + 10][4 * SIZE + 40],lz[SIZE + 10][4 * SIZE + 40];

void build(int block, int s, int l, int r)
{
  if(l == r) {
    t[block][s] = f[rrh[block][l].second];
    return ;
  }
  int mid = (l + r)/2;
  build(block, s * 2, l, mid);
  build(block, s * 2 + 1, mid + 1, r);
  t[block][s] = max(t[block][s * 2], t[block][s * 2 + 1]);
}

void lazy(int block,int s)
{
  t[block][s * 2] += lz[block][s];
  t[block][s * 2 + 1] += lz[block][s];
  lz[block][s * 2] += lz[block][s];
  lz[block][s * 2 + 1] += lz[block][s];
  lz[block][s] = 0;
  return ;
}

void upd(int block, int s, int l, int r, int u, int v, int val)
{
  if(l > v || r < u) return ;
  if(u <= l && r <= v) {
    t[block][s] += val;
    lz[block][s] += val;
    return ;
  }
  int mid = (l + r)/2;
  if(l != r && lz[block][s] != 0) lazy(block,s);
  upd(block, s * 2, l, mid, u, v, val);
  upd(block, s * 2 + 1, mid + 1, r, u, v, val);
  t[block][s] = max(t[block][s * 2], t[block][s * 2 + 1]);
}

void get(int block, int s, int l, int r)
{
  if(l == r) {
    f[rrh[block][l].second] = t[block][s];
    return ;
  }
  int mid = (l + r)/2;
  if(l != r && lz[block][s] != 0) lazy(block,s);

  get(block, s * 2, l, mid);
  get(block, s * 2 + 1, mid + 1, r);
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V)
{
  n = A.size();
  q = X.size();
  vector<int> ans;
   cin >> n >> q;
    for(int i = 1;i <= n; i++) {
        a[i] = A[i - 1];
    }
    for(int i = 1;i <= q; i++)
      {
        uu[i] = X[i - 1];
        vv[i] = V[i - 1];
        uu[i]++;
      }
     for(int i = 1;i <= n; i++) {
        rrh[id(i)].pb({a[i],i});
     }
     for(int i = 1;i <= id(n); i++) {
        sort(rrh[i].begin(), rrh[i].end());
     }
     // tim f
     for(int i = 1;i <= n; i++) f[i] = get_cnt(a[i],i);
     for(int i = 1;i <= id(n); i++) {
        build(i,1,0,rrh[i].size() - 1);
     }

     for(int i = 1;i <= q; i++) {
        int bl = id(uu[i]);
        // upd != block
        for(int j = bl + 1; j <= id(n); j++) {
          ii tmp = {a[uu[i]],0};

          int u = lower_bound(rrh[j].begin(), rrh[j].end(), tmp) - rrh[j].begin() - 1;
          int sz = rrh[j].size();
          if(u != -1) upd(j, 1, 0, sz - 1, 0, min(u, sz - 1), -1);
          tmp = {vv[i], 0};
          u = lower_bound(rrh[j].begin(), rrh[j].end(), tmp) - rrh[j].begin() - 1;
          //cout << u << " ";
          if(u != -1) upd(j, 1, 0, sz - 1, 0, min(u, sz - 1), 1);
        }
        // upd == block
        get(bl,1,0,rrh[bl].size() - 1);
        int l = (bl - 1) * SIZE + 1;
        int r = min(n,bl * SIZE);
        for(int j = uu[i] + 1;j <= r; j++) f[j] = f[j] - (a[j] < a[uu[i]]) + (a[j] < vv[i]);

        f[uu[i]] = get_cnt(vv[i], uu[i]);
        a[uu[i]] = vv[i];
        for(int j = l; j <= r; j++) rrh[bl][j - l] = {a[j],j};
        sort(rrh[bl].begin(), rrh[bl].end());
        build(bl,1,0,rrh[bl].size() - 1);

        // get kq
        int kq = 0;
        for(int i = 1;i <= id(n); i++) kq = max(kq, t[i][1]);
        ans.pb(kq);
     }
     return ans;

}

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