Submission #1012716

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012716		Cookie	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	1422 ms	64940 KiB

bubblesort2

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
#define sz(a) (int)a.size()
#define ALL(v) v.begin(), v.end()
#define ALLR(v) v.rbegin(), v.rend()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
#define mpp make_pair
const ld PI = 3.14159265359, prec = 1e-9;;
//using u128 = __uint128_t;
//const int cox[4] = {1, 0, -1, 0};
//const int coy[4] = {0, -1, 0, 1};
const ll mod = 1e9 + 7, pr = 31;
const int mxn = 1e6 + 5, mxs = 3e5, sq = 500, mxv = 2e6 + 1;
const int max_iter = 8e4, global_iter = 15e5 + 5;
//const int base = (1 <<18);
const ll inf = 1e9 + 5, neg = -69420, inf2 = 1e14;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
//#define int long long
#include "bubblesort2.h"
int st[4 * mxn + 1], lz[4 * mxn + 1];
vt<pii>comp;
int bit[mxn + 1];
void updbit(int p, int v){
    while(p <= sz(comp)){
        bit[p] += v; p += p & (-p);
    }
}
int getbit(int p){
    int ans = 0;
    while(p){
        ans += bit[p]; p -= p & (-p);
    }
    return(ans);
}
void go(int nd, int v){
    st[nd] += v; lz[nd] += v;
}
void push(int nd){
    int &v = lz[nd];
    go(nd << 1, v); go(nd << 1 | 1, v);
    v = 0;
}
void pull(int nd){
    st[nd] = max(st[nd << 1], st[nd << 1 | 1]);
}
void updset(int nd, int l, int r, int id, int v){
    if(l == r){
        st[nd] = v; return;
    }
    int mid = (l + r) >> 1;
    push(nd);
    if(id <= mid)updset(nd << 1, l, mid, id, v); 
    else updset(nd << 1 | 1, mid + 1, r, id, v);
    pull(nd);
}
void updadd(int nd, int l, int r, int ql, int qr, int v){
    if(ql > r || qr < l)return;
    if(ql <= l && qr >= r){
        go(nd, v); return;
    }
    int mid = (l + r) >> 1;
    push(nd);
    updadd(nd << 1, l, mid, ql, qr, v); updadd(nd << 1 | 1, mid + 1, r, ql, qr, v);
    pull(nd);
}
int find(int sus, int sus2){
    return(lower_bound(ALL(comp), mpp(sus, sus2)) - comp.begin() + 1);
}
std::vector<int> countScans(std::vector<int> a,std::vector<int> x,std::vector<int> v){
	for(int i = 0; i < sz(a); i++)comp.pb(mpp(a[i], i));
	for(int i = 0; i < sz(x); i++)comp.pb(mpp(v[i], x[i]));
	sort(ALL(comp)); comp.resize(unique(ALL(comp)) - comp.begin());
	for(int i = 0; i < sz(a); i++){
	    updbit(find(a[i], i), 1);
	}
	for(int i = 1; i <= 4 * sz(comp); i++)st[i] = -inf;
	for(int i = 0; i < sz(a); i++){

	    updset(1, 1, sz(comp), find(a[i], i), i - getbit(find(a[i], i)));
	}
	vt<int>res;
	for(int i = 0; i < sz(v); i++){
	    int pos = x[i], val = v[i];
	    updset(1, 1, sz(comp), find(a[pos], pos), -inf);
	    updadd(1, 1, sz(comp), find(a[pos], pos) + 1, sz(comp), 1);
	    updbit(find(a[pos], pos), -1);
	    a[pos] = val;
	    updbit(find(a[pos], pos), 1);
	    updset(1, 1, sz(comp), find(a[pos], pos), pos - getbit(find(a[pos], pos)));
	    updadd(1, 1, sz(comp), find(a[pos], pos) + 1, sz(comp), -1);
	    res.pb(st[1] + 1);
	}
	return(res);
}
/*
#include <cstdio>
#include <cstdlib>
#include <vector>

int readInt(){
	int i;
	if(scanf("%d",&i)!=1){
		fprintf(stderr,"Error while reading input\n");
		exit(1);
	}
	return i;
}

int main(){
	int N,Q;
	N=readInt();
	Q=readInt();
	
	std::vector<int> A(N);
	for(int i=0;i<N;i++)
		A[i]=readInt();
	
	std::vector<int> X(Q),V(Q);
	for(int j=0;j<Q;j++){
		X[j]=readInt();
		V[j]=readInt();
	}
	
	std::vector<int> res=countScans(A,X,V);
	
	for(int j=0;j<int(res.size());j++)
		printf("%d\n",res[j]);
}
*/

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