Submission #120489

#	Time	Username	Problem	Language	Result	Execution time	Memory
120489		Mercenary	Bubble Sort 2 (JOI18_bubblesort2)	C++14	0 / 100	18 ms	2044 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];
    }
    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)return;
    if(L <= l && r <= R){
        lz[x] += delta;
        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]);
    cnt[x] = cnt[x * 2] + cnt[x * 2 + 1];
}

void updatePoint(int x , int l , int r , int pos , int s , int cnt){
    Push(x , l == r);
    if(l == r){
        ::s[x] = s;
        ::cnt[x] = cnt;
        return;
    }
    int mid = (l + r) >> 1;
    if(mid >= pos)updatePoint(x * 2, l , mid , pos , s , cnt);
    else updatePoint(x * 2 + 1 , mid + 1 , r , pos , s , cnt);
    ::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());
    for(int i = 0 ; i < n + q ; ++i){
        if(node[i].y >= n){
            pos[node[i].y - n] = i;
        }else{
            arr[node[i].x.y] = i;
            updatePoint(1 , 0 , n + q - 1 , i , node[i].x.y - getSum(1 , 0 , n + q - 1 , 0 , i) , 1);
        }
    }
    for(int i = 0 ; i < q ; ++i){
        updatePoint(1 , 0 , n + q - 1 , arr[x[i]] , -1 , 0);
        updateRange(1 , 0 , n + q - 1 , arr[x[i]] , n + q - 1 , 1);
        arr[x[i]] = pos[i];
        updatePoint(1 , 0 , n + q - 1 , arr[x[i]] , x[i] - getSum(1 , 0 , n + q - 1 , 0 , arr[x[i]]) , 1);
        updateRange(1 , 0 , n + q - 1 , arr[x[i]] , n + q - 1 , 1);
        answer[i] = s[1];
    }
	return answer;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'int getSum(int, int, int, int, int)':
bubblesort2.cpp:41:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + R >> 1;
               ~~^~~
bubblesort2.cpp: In function 'void updateRange(int, int, int, int, int, int)':
bubblesort2.cpp:52:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~

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