Submission #991115

#	Time	Username	Problem	Language	Result	Execution time	Memory
991115		12345678	Bubble Sort 2 (JOI18_bubblesort2)	C++17	100 / 100	3413 ms	109256 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=1e6+5;

int n, q, t;
vector<int> res;
map<pair<int, int>, int> mp;

struct segtree
{
    int d[4*nx], lz[4*nx];
    void pushlz(int l, int r, int i)
    {
        d[i]+=lz[i];
        if (l!=r) lz[2*i]+=lz[i], lz[2*i+1]+=lz[i];
        lz[i]=0;
    }
    void update(int l, int r, int i, int ql, int qr, int vl)
    {
        pushlz(l, r, i);
        if (qr<l||r<ql) return;
        if (ql<=l&&r<=qr) return lz[i]+=vl, pushlz(l ,r, i), void();
        int md=(l+r)/2;
        update(l, md, 2*i, ql, qr, vl);
        update(md+1, r, 2*i+1, ql, qr, vl);
        d[i]=max(d[2*i], d[2*i+1]);
    }
} s;


std::vector<int> countScans(std::vector<int> A,std::vector<int> X,std::vector<int> V){
    n=A.size();
	q=X.size();
    for (int i=0; i<n; i++) mp[{A[i], i}]=0;
    for (int i=0; i<q; i++) mp[{V[i], X[i]}]=0;
    for (auto &[x, y]:mp) y=++t;
	for (int i=0; i<n; i++) s.update(1, n+q, 1, mp[{A[i], i}], mp[{A[i], i}], i), s.update(1, n+q, 1, mp[{A[i], i}], n+q, -1);
    for (int i=0; i<q; i++)
    {
        s.update(1, n+q, 1, mp[{A[X[i]], X[i]}], mp[{A[X[i]], X[i]}], -X[i]);
        s.update(1, n+q, 1, mp[{A[X[i]], X[i]}], n+q, 1);
        A[X[i]]=V[i];
        s.update(1, n+q, 1, mp[{A[X[i]], X[i]}], mp[{A[X[i]], X[i]}], X[i]);
        s.update(1, n+q, 1, mp[{A[X[i]], X[i]}], n+q, -1);
        res.push_back(s.d[1]+1);
    }
	return res;
}

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