Submission #514547

#	Time	Username	Problem	Language	Result	Execution time	Memory
514547		Vladth11	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	4678 ms	121724 KiB

bubblesort2

#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#include "bubblesort2.h"

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;

const ll NMAX = 10000001;
const ll VMAX = 21;
const ll INF = 2e9;
const ll MOD = 1000000007;
const ll BLOCK = 318;
const ll base = 31;
const ll nr_of_bits = 60;

int n;

class AINT{
public:
    int aint[NMAX], lazy[NMAX];
    void propaga(int node, int st, int dr){
        if(st != dr)
        {
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
        aint[node] += lazy[node];
        lazy[node] = 0;
    }
    void update(int node, int st, int dr, int a, int b, int val){
        propaga(node, st, dr);
        if(a > b)
            return;
        if(a <= st && dr <= b){
            lazy[node] += val;
            return;
        }
        int mid = (st + dr) / 2;
        if(a <= mid)
            update(node * 2, st, mid, a, b, val);
        if(b > mid)
            update(node * 2 + 1, mid + 1, dr, a, b, val);
        propaga(node * 2, st, mid);
        propaga(node * 2 + 1, mid + 1, dr);
        aint[node] = max(aint[node * 2], aint[node * 2 + 1]);
    }
    int maxim(){
        propaga(1, 1, n);
        return aint[1];
    }
}st;

map <pii, int> mp;

vector<int> countScans(vector<int> A, vector<int> X, vector<int> V){
	int Q=X.size();
	vector<int> answer(Q);
    vector <pii> norm;
    swap(X, V); /// ups pare ca le-am incurcat
    for(int i = 0; i < A.size(); i++){
        norm.push_back({A[i], i + 1});
    }
    for(int i = 0; i < Q; i++){
        norm.push_back({X[i], V[i] + 1}); /// Grija aici la  + 1
    }
    sort(norm.begin(), norm.end());
    int cnt = 0;
    for(int i = 0; i < norm.size(); i++){
        if(i == 0 || norm[i] != norm[i - 1])
            cnt++;
        mp[norm[i]] = cnt;
    }
    n = cnt;
    for(int i = 1; i <= n; i++){
        st.update(1, 1, n, i, i, -INF);
    }
    for(int i = 0; i < A.size(); i++){
        pii x = {A[i], i + 1};
        int poz = mp[x];
        st.update(1, 1, n, poz, poz, INF);
        st.update(1, 1, n, poz, poz, i + 1);
        st.update(1, 1, n, poz + 1, n, -1); /// sortedPosition creste cu 1, deci contributia e -1
    }
    for(int i = 0; i < Q; i++){
        pii x = {A[V[i]], V[i] + 1};
        A[V[i]] = X[i];
        int poz = mp[x];
        st.update(1, 1, n, poz, poz, -INF);
        st.update(1, 1, n, poz, poz, -x.second);
        st.update(1, 1, n, poz + 1, n, 1);
        x = {A[V[i]], V[i] + 1};
        poz = mp[x];
        st.update(1, 1, n, poz, poz, INF);
        st.update(1, 1, n, poz, poz, x.second);
        st.update(1, 1, n, poz + 1, n, -1);
        answer[i] = st.maxim() - 1;
    }
	return answer;
}

Compilation message (stderr)

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

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