Submission #1143524

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143524		idiotcomputer	Bubble Sort 2 (JOI18_bubblesort2)	C++20	0 / 100	85 ms	36796 KiB

bubblesort2

#include <bits/stdc++.h>
using namespace std;
#define ll long long int 
#define pb push_back
#define sz(x) (int) (x).size()
#define pii pair<ll,ll>
#define f first
#define s second 
const int mxN = 1e6+50;
const int ninf = -1e8;
int cnt;

int st[4*mxN+5];
int laz[4*mxN+5];


void u1(int tl, int tr, int v, int l = 0, int r = cnt-1, int idx = 0){
    if (l > tr || r < tl) return;
    if (l >= tl && r <= tr){ laz[idx] += v; return; }
    int m = (l+r)/2;
    u1(tl,tr,v,l,m,2*idx+1);
    u1(tl,tr,v,m+1,r,2*idx+2);
    st[idx] = max(st[2*idx+1] + laz[2*idx+1], st[2*idx+2] + laz[2*idx+2]);
    return;
}

void u2(int t, int v, int l = 0, int r = cnt-1, int idx = 0){
    if (l > t || r < t) return;
    if (l == r){ st[idx] = v; return;}
   // pd(idx);
    int m = (l+r)/2;
    u2(t,v,l,m,2*idx+1);
    u2(t,v,m+1,r,2*idx+2);
    st[idx] = max(st[2*idx+1] + laz[2*idx+1], st[2*idx+2] + laz[2*idx+2]);
    return;    
}

int query(int tl, int tr, int l = 0, int r = cnt-1, int idx = 0){
    if (l > tr || r < tl) return ninf;
    if (l >= tl && r <= tr) return st[idx] + laz[idx];
    int m = (l+r)/2;
    return max(query(tl,tr,l,m,2*idx+1), query(tl,tr,m+1,r,2*idx+2)) + laz[idx];
}

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
    int n = sz(A);
    int q = sz(X);

    map<ll,int> idxs;
    vector<ll> all;
  /*  cout << n << ":\n";
    for (int i = 0; i < n; i++) cout << A[i] << " ";
    cout << '\n';
    cout << q << ":\n";
    for (int i = 0; i < q; i++) cout << X[i] << "," << V[i] << " ";
    cout << '\n';*/
    for (int i = 0; i < n; i++) all.pb((ll)A[i]*n + i);
    for (int i = 0; i < q; i++) all.pb((ll)V[i] * n + X[i]);
    sort(all.begin(),all.end());
    cnt = 0;
    int last = -1;
    for (int i = 0; i < sz(all); i++){
        if (all[i] == last) continue;
        idxs[all[i]] = cnt;
        cnt++;
        last = all[i];
    }
    vector<int> res(q);
//for (ll c : all) cout << c << " ";
   /// cout << '\n';
    //for (pii c : idxs) cout << c.f << ',' << c.s << '\n';
  //  return res;
    
    for (int i = 0; i < 4*mxN+5; i++) st[i] = ninf;
    memset(laz,0,sizeof(laz));

    for (int i = 0; i < n; i++) u2(idxs[(ll)A[i]*n+i],i), u1(idxs[(ll)A[i]*n+i]+1, cnt-1,-1);// cout << idxs[(ll)A[i]*n+i] << " ";
//cout << '\n';
    ll c;
    ll a;
    //cout << query(0,cnt-1) << "\n";
    for (int i = 0; i < q; i++){
        c = idxs[(ll) V[i] * n + X[i]];
        a = idxs[(ll) A[X[i]] * n + X[i]];
        A[X[i]] = V[i];
        u1(a+1,cnt-1,+1);
        u1(c+1,cnt-1,-1);
        u2(a,ninf);
        u2(c,i); 
      //  cout << "SWAPPING " << a << ',' << c << "\n";
        res[i] = query(0,cnt-1);
    }
    return res;
}

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