Submission #120568

#	Time	Username	Problem	Language	Result	Execution time	Memory
120568		Mercenary	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	2469 ms	75312 KiB

bubblesort2

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

using namespace std;
#define taskname "A"
#define pb	push_back
#define mp 	make_pair
#ifndef LOCAL
#define cerr if(0)cout
#endif

typedef long double ld;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll,int> lli;
const int maxn = 1e6 + 6;
const ld inf = 1e9 + 5;

#define x first
#define y second

vector<pair<ii,int>> node;

int n , q;

int lz[maxn << 2] , s[maxn << 2] , cnt[maxn << 2];

void Push(int x , bool key){
    s[x] += lz[x];
    if(!key){
        lz[x * 2] += lz[x];
        lz[x * 2 + 1] += lz[x];
//        cnt[x] = cnt[x * 2] + cnt[x * 2 + 1];
    }
    lz[x] = 0;
}

int getSum(int x , int l , int r , int L , int R){
    Push(x , l == r);
    if(l > R || L > r)return 0;
    if(L <= l && r <= R)return cnt[x];
    int mid = (l + r) >> 1;
    return getSum(x * 2 , l , mid , L , R) + getSum(x * 2 + 1 , mid + 1 , r , L , R);
}

void updateRange(int x , int l , int r , int L , int R , int delta){
    Push(x , l == r);
    if(l > R || L > r || l > r || L > R)return;
    if(L <= l && r <= R){
        lz[x] += delta;
        Push(x , l == r);
        return;
    }
    int mid = (l + r) >> 1;
    updateRange(x * 2 , l , mid , L , R , delta);
    updateRange(x * 2 + 1 , mid + 1 , r , L , R , delta);
    s[x] = max(s[x * 2] , s[x * 2 + 1]);
}

void updatePoint(int x , int l , int r , int pos , int s1 , int cnt1){
    Push(x , l == r);
    if(pos > r || pos < l)return;
    if(l == r){
        s[x] = s1;
        cnt[x] = cnt1;
        lz[x] = 0;
        return;
    }
    int mid = (l + r) >> 1;
    updatePoint(x * 2, l , mid , pos , s1 , cnt1);
    updatePoint(x * 2 + 1 , mid + 1 , r , pos , s1 , cnt1);
    s[x] = max(s[x * 2] , s[x * 2 + 1]);
    cnt[x] = cnt[x * 2] + cnt[x * 2 + 1];
}

int arr[maxn] , pos[maxn];

vector<int> countScans(vector<int> a,vector<int> x,vector<int> v){
    q = x.size();n = a.size();
	vector<int> answer(q);
    for(int i = 0 ; i < n ; ++i){
        node.pb(mp(mp(a[i] , i) , i));
    }
    for(int i = 0 ; i < q ; ++i){
        node.pb(mp(mp(v[i] , x[i]) , i + n));
    }
    sort(node.begin(),node.end());
    fill_n(s,maxn*4,-1e9);
    for(int i = 0 ; i < n + q ; ++i){
        if(node[i].y >= n){
            pos[node[i].y - n] = i;
        }else{
            arr[node[i].y] = i;
            updatePoint(1 , 0 , n + q - 1 , i , node[i].y - getSum(1 , 0 , n + q - 1 , 0 , i) , 1);
        }
    }
    for(int i = 0 ; i < q ; ++i){
        updateRange(1 , 0 , n + q - 1 , arr[x[i]] , n + q - 1 , 1);
        updatePoint(1 , 0 , n + q - 1 , arr[x[i]] , -1e9 , 0);
//        cout << x[i] << " " << arr[x[i]] << " ";
        arr[x[i]] = pos[i];
//        cout << arr[x[i]] << " ";
        updateRange(1 , 0 , n + q - 1 , arr[x[i]] , n + q - 1 , -1);
//        cout << getSum(1 , 0 , n + q - 1 , arr[x[i]] , arr[x[i]]) << " ";
        updatePoint(1 , 0 , n + q - 1 , arr[x[i]] , x[i] - getSum(1 , 0 , n + q - 1 , 0 , arr[x[i]]) , 1);
        answer[i] = s[1];
//        cout << answer[i] << endl;
    }
	return answer;
}

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