oj.uz

Submission #120487

# Submission time Handle Problem Language Result Execution time Memory
120487 2019-06-24T16:18:14 Z Mercenary Bubble Sort 2 (JOI18_bubblesort2) C++14
0 / 100
 16 ms 2044 KB 
#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 >= x)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

bubblesort2.cpp: In function 'int getSum(int, int, int, int, int)':
bubblesort2.cpp:42: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:53:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 2044 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 512 KB Output isn't correct
2 Halted 0 ms 0 KB -