Submission #1116659

#	Time	Username	Problem	Language	Result	Execution time	Memory
1116659		jkb_gryz	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	3246 ms	138544 KiB

bubblesort2

#include <bits/stdc++.h>
#include "bubblesort2.h"
 
using namespace std;
#define ll long long
#define para pair<ll, ll>
 
const int base = 1<<20;
const ll INF = 1e18+7;
const ll MAXN = 1e6+7;
 
ll tree[base<<1];
ll lazy[base<<1];
 
void push(ll v){
    lazy[2*v] += lazy[v];
    lazy[2*v+1] += lazy[v];
    
    tree[2*v] += lazy[v];
    tree[2*v+1] += lazy[v];
 
    lazy[v] = 0;
}
 
ll p, k;
ll val;
ll smaller[MAXN];
 
void update(ll v, ll l, ll r){
    if(l > k || r < p) return;
    if(p <= l && r <= k){
        tree[v] += val;
        lazy[v] += val;
    }
    else{
        ll mid = (l+r)/2;
 
        push(v);
 
        update(2*v, l, mid);
        update(2*v+1, mid+1, r);
 
        tree[v] = max(tree[2*v], tree[2*v+1]);
    }
}
 
ll query(ll v, ll l, ll r){
    if(l > k || r < p) return -INF;
    if(p <= l && r <= k){
        return tree[v];
    }
    else{
        ll mid = (l+r)/2;
 
        push(v);
 
        auto lQ = query(2*v, l, mid);
        auto rQ = query(2*v+1, mid+1, r);
        return max(lQ, rQ);
    }
}
 
 
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){     
    int n = A.size();
	int Q = X.size();
	vector<int> res(Q);
 
    vector<ll> skalowanie;
    for(auto i : A)
        skalowanie.push_back(i);

    for(auto i : V)
        skalowanie.push_back(i);
    
    sort(skalowanie.begin(), skalowanie.end());
    map<ll, ll> skalowanie2;
    ll prev = 0;
    for(ll i = 0; i < skalowanie.size(); ++i){
        if(skalowanie2[skalowanie[i]] == 0) skalowanie2[skalowanie[i]] = i+1, prev = i;
        smaller[i+1] = prev;
    }
    ll id = skalowanie.size()+7;

    p = 0, k = id;
    val = -INF;
    update(1, 1, id);
    
    for(ll i = 0; i < n; ++i){
        A[i] = skalowanie2[A[i]]++;
        p = 0, k = smaller[A[i]];
        val = 1;
        update(1, 1, id);
        p = k = A[i];
        val = INF + i; 
        update(1, 1, id);
    }

    for(ll i = 0; i < Q; ++i){
        p = 0, k = smaller[A[X[i]]];
        val = -1;
        update(1, 1, id);
        p = k = A[X[i]];
        val = -INF;
        update(1, 1, id);

        A[X[i]] = skalowanie2[V[i]]++;

        p = 0, k = smaller[A[X[i]]];
        val = 1;
        update(1, 1, id);
        p = k = A[X[i]];
        val = INF + X[i];
        update(1, 1, id);
        p = 0, k = id;
        res[i] = query(1, 1, id) - n + 1;
    }
 
	return res;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:79:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(ll i = 0; i < skalowanie.size(); ++i){
      |                   ~~^~~~~~~~~~~~~~~~~~~

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