Submission #101071

#	Time	Username	Problem	Language	Result	Execution time	Memory
101071		BartolM	Bubble Sort 2 (JOI18_bubblesort2)	C++17	0 / 100	105 ms	98236 KiB

bubblesort2

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
#include <vector>

using namespace std;

#define X first
#define Y second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair <int, int> pii;

const int INF=0x3f3f3f3f;
const int N=1e6+5;

int n, q, off=1, ma=0;
vector <int> ppp, pospos, valval, saz;
set <int> S[N];
int T[2*N], prop[2*N];

void propag(int pos, int lo, int hi) {
    if (prop[pos]==0) return;
    T[pos]+=prop[pos];
    if (pos<off) {
        prop[pos*2]+=prop[pos];
        prop[pos*2+1]+=prop[pos];
    }
    prop[pos]=0;
}

int query(int lo, int hi, int pos, int a, int b) {
    propag(pos, lo, hi);
    if (lo>=b || hi<=a) return 0;
    if (lo>=a && hi<=b) return T[pos];
    int mid=(lo+hi)/2;
    return max(query(lo, mid, pos*2, a, b), query(mid, hi, pos*2+1, a, b));
}

void update(int lo, int hi, int pos, int a, int b, int val) {
    propag(pos, lo, hi);
    if (lo>=b || hi<=a) return;
    if (lo>=a && hi<=b) {
        prop[pos]+=val;
        propag(pos, lo, hi);
        return;
    }
    int mid=(lo+hi)/2;
    update(lo, mid, pos*2, a, b, val);
    update(mid, hi, pos*2+1, a, b, val);
    T[pos]=max(T[pos*2], T[pos*2+1]);
}

void load() {
    int nn, qq;
    scanf("%d %d", &nn, &qq);
    for (int i=0; i<nn; ++i) {
        int x;
        scanf("%d", &x);
        ppp.pb(x);
    }
    for (int i=0; i<qq; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        pospos.pb(a);
        valval.pb(b);
    }
}

void countScans(vector <int> p, vector <int> Pos, vector <int> Val) {
    n=p.size();
    q=Pos.size();
    for (int i=0; i<n; ++i) saz.pb(p[i]);
    for (int i=0; i<q; ++i) saz.pb(Val[i]);
    sort(saz.begin(), saz.end());
    for (int i=0; i<n; ++i) {
        p[i]=lower_bound(saz.begin(), saz.end(), p[i])-saz.begin()+1;
        S[p[i]].insert(-i);
        ma=max(ma, p[i]);
    }
    for (int i=0; i<q; ++i) {
        Val[i]=lower_bound(saz.begin(), saz.end(), Val[i])-saz.begin()+1;
        ma=max(ma, Val[i]);
    }

    while (off<ma) off*=2;
    int zbr=0;
    for (int i=1; i<=ma; ++i) {
        zbr+=S[i].size();
        S[i].insert(-1);
        T[off+i]=-(*S[i].begin())-(zbr-1);
    }
    for (int i=off-1; i>0; --i) T[i]=max(T[i*2], T[i*2+1]);

    for (int i=0; i<q; ++i) {
        int x=p[Pos[i]], mi=-(*S[x].begin());

        S[x].erase(-Pos[i]);
        update(0, off, 1, x, x+1, mi+(*S[x].begin()));

        int mii=-(*S[Val[i]].begin());
        S[Val[i]].insert(-Pos[i]);
        update(0, off, 1, Val[i], Val[i]+1, -(*S[Val[i]].begin())-mii);

        if (x<Val[i]) {
            update(0, off, 1, x+1, Val[i], -1);
        }
        else {
            update(0, off, 1, Val[i]+1, x, 1);
        }
        printf("%d\n", query(0, off, 1, 1, ma));
    }


}

//int main() {
//    load();
//    countScans(ppp, pospos, valval);
//    return 0;
//}

Compilation message (stderr)

bubblesort2.cpp: In function 'void load()':
bubblesort2.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &nn, &qq);
     ~~~~~^~~~~~~~~~~~~~~~~~~
bubblesort2.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
         ~~~~~^~~~~~~~~~
bubblesort2.cpp:67:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~

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