Submission #821793

#	Time	Username	Problem	Language	Result	Execution time	Memory
821793		AdamGS	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	3773 ms	113372 KiB

bubblesort2

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=5e5+7;
int T[LIM], tr[8*LIM], lazy[8*LIM], N=1;
vector<pair<int,int>>skal;
map<pair<int,int>,int>mp;
pair<int,int>pyt[LIM];
void spl(int v) {
  tr[2*v]+=lazy[v];
  tr[2*v+1]+=lazy[v];
  lazy[2*v]+=lazy[v];
  lazy[2*v+1]+=lazy[v];
  lazy[v]=0;
}
void upd(int v, int l, int r, int a, int b, int x) {
  if(r<a || l>b) return;
  if(a<=l && r<=b) {
    tr[v]+=x;
    lazy[v]+=x;
    return;
  }
  if(lazy[v]) spl(v);
  int mid=(l+r)/2;
  upd(2*v, l, mid, a, b, x);
  upd(2*v+1, mid+1, r, a, b, x);
  tr[v]=max(tr[2*v], tr[2*v+1]);
}
vector<int>countScans(vector<int>A, vector<int>X, vector<int>V) {
  int n=A.size(), q=X.size();
  rep(i, n) skal.pb({A[i], i});
  rep(i, q) skal.pb({V[i], X[i]});
  sort(all(skal));
  int akt=0;
  for(auto i : skal) if(mp.find(i)==mp.end()) mp[i]=akt++;
  while(N<akt) N*=2;
  rep(i, n) {
    int p=mp[{A[i], i}];
    upd(1, 0, N-1, p, p, i);
    upd(1, 0, N-1, p+1, N-1, -1);
  }
  vector<int>ans(q);
  rep(i, q) {
    int p=mp[{A[X[i]], X[i]}];
    upd(1, 0, N-1, p, p, -X[i]);
    upd(1, 0, N-1, p+1, N-1, 1);
    A[X[i]]=V[i];
    p=mp[{A[X[i]], X[i]}];
    upd(1, 0, N-1, p, p, X[i]);
    upd(1, 0, N-1, p+1, N-1, -1);
    ans[i]=tr[1];
  }
  return ans;
}

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