Submission #329078

#	Time	Username	Problem	Language	Result	Execution time	Memory
329078		gmyu	Bubble Sort 2 (JOI18_bubblesort2)	C++14	0 / 100	44 ms	2024 KiB

bubblesort2

/*
ID: USACO_template
LANG: C++
PROG: USACO
*/
#include <iostream>  //cin , cout
#include <fstream>   //fin, fout
#include <stdio.h>   // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack>     // stacks
#include <queue>     // queues
#include <map>
#include <string>
#include <set>
#include <utility>

using namespace std;

typedef pair<int, int>          pii;
typedef vector<int>             vi;     /// adjlist without weight
typedef vector<pii>             vii;    /// adjlist with weight
typedef vector<pair<int,pii>>   vpip;   /// edge with weight
typedef long long               ll;

#define mp  make_pair
#define fst first
#define snd second
#define pb  push_back
#define trav(u, adj_v) for (auto& u: adj_v)

const int MOD = 1e9+7;  // 998244353;
const int MX  = 2e9+5;   //
const ll  INF = 1e18;    //

#define MAXV 500007
#define MAXE 100007

const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; /// 4 directions
struct NODE {
    int x, y;
    int val;
    int visited;
};
struct EDGE {
    int from, to;
    ll weight;
    bool operator<(EDGE other) const { return weight < other.weight; }
};

/// code from USACO examples
void setIO(string name) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    freopen((name+".in").c_str(),"r",stdin);
    freopen((name+".out").c_str(),"w",stdout);
}
bool debug = false, submit = true;

/*
for a given Ai, number of bubble sort related to Ai = (number of Aj > Ai, and j <i).
so the answer is max{for i = 0 .. N-1, (number of Aj > Ai, and j <i) }

but this leads O(N) for each Q and we need to change that to O lgN

Note that (number of Aj > Ai, and j <i) = i - (number of Aj < Ai, and j <i)
and for the max condition, if the corresponding Ai is Ai0. Then for any j > i0, Aj > Ai0. This means, the query becomes
    i - (number of Aj <= Ai, for j != i from 0 ... N-1)
this is because, if there is a Aj > Ai0 while j > i0, instead of using i0, we should use j for the max condition

Now, how do we update at each query? We use segment tree where each leaf is the (compressed) Ai and its corresponding i value.
When we change from Ai0 to Ai1.
    - every leaf before Ai0 does not change, and every leaf at Ai0 and beyond +1 for (i - #)
    - every leaf before Ai does not change, and every leaf at Ai and beyond -1 for (i-#)
and update Aio and Ai1

since there could be duplicated Ai value, we need to use (Ai, i) dual index to sort it

*/

/// ------ Segment Treee --------
int Nseg[2];
struct SEGNODE {
    int ct;                 /// sum is always updated before lazy value is used.
    int ma;
    int maLzVal;
    bool LazyPushedDown;    /// flag whether we already pushed down the lazy additional value
};
SEGNODE seg[4*MAXV];    /// max 2e5 unique y, which needs 2^19 for Nseg
vector<pii> uA;

void pullUp(int v, int l, int m, int r) {
    if(l==r) return;

    seg[v].ct = seg[2*v].ct + seg[2*v+1].ct;
    seg[v].ma = max(seg[2*v].ma, seg[2*v+1].ma);
}
void pushDown(int v, int l, int m, int r) {

    if(l==r) {
        seg[v].LazyPushedDown = true;
        return;
    }

    if(seg[v].LazyPushedDown) return;

    /// push down
    seg[2*v].ma += seg[v].maLzVal;
    seg[2*v].LazyPushedDown = false;

    seg[2*v+1].ma += seg[v].maLzVal;
    seg[2*v+1].LazyPushedDown = false;

    /// update v
    seg[v].maLzVal = 0;
    seg[v].LazyPushedDown = true;

}
void buildSeg(int v = 1, int l = Nseg[0], int r = Nseg[1]) {

    if(l == r) { // leaf
        seg[v].ct = 0; seg[v].ma = -MX;
        seg[v].maLzVal = 0; seg[v].LazyPushedDown = true;
        return;
    }

    int mid = (l + r) / 2;
    buildSeg(2*v, l, mid); buildSeg(2*v+1, mid+1, r);
    pullUp(v, l, mid, r);
    seg[v].maLzVal = 0; seg[v].LazyPushedDown = true;
}
int querySegCt(pii qriBd, int v = 1, int l = Nseg[0], int r = Nseg[1]) {    /// [0, qriBd)
    if(uA[l] >= qriBd) return 0;
    if(uA[r] < qriBd) {
        return seg[v].ct;
    }

    int mid = (l + r) / 2;
    //pushDown(v, l, mid, r);
    int ans = querySegCt(qriBd, 2*v, l, mid) + querySegCt(qriBd, 2*v+1, mid+1, r);
    //pullUp(v, l, mid, r);
    seg[v].ct = seg[2*v].ct + seg[2*v+1].ct;
    return ans;
}
void replaceSegLeaf(pii vt, int typ, int val, int v = 1, int l = Nseg[0], int r = Nseg[1]){
    if(uA[r] < vt || uA[l] > vt) return;

    int mid = (l + r) / 2;
    if(l == r) {
        if(typ == 0) {
            seg[v].ct = val;
        } else {
            seg[v].ma = val;
        }
        return;
    }

    pushDown(v, l, mid, r);

    replaceSegLeaf(vt, typ, val, 2*v, l, mid);
    replaceSegLeaf(vt, typ, val, 2*v+1, mid+1, r);

    pullUp(v, l, mid, r);
}
void updateSegMa(pii uleBd, int val, int v = 1, int l = Nseg[0], int r = Nseg[1]){    /// (uleBd, INF)
    if(uA[r] <= uleBd ) return;

    int mid = (l + r) / 2;
    if(uleBd < uA[l] ) {
        pushDown(v, l, mid, r);

        seg[v].ma += val;

        seg[v].maLzVal = val;
        seg[v].LazyPushedDown = false;

        return;
    }

    pushDown(v, l, mid, r);

    updateSegMa(uleBd, val, 2*v, l, mid);
    updateSegMa(uleBd, val, 2*v+1, mid+1, r);

    pullUp(v, l, mid, r);
}

vector<int> countScans( vector<int> A, vector<int> X, vector<int> V) {
    debug = false; submit = false;
    if(submit) setIO("testName");

    int i, j, k;
    vector<int> ret;

    for(i=0; i<A.size();i++) uA.pb(mp(A[i], i));
    for(i=0; i<V.size();i++) uA.pb(mp(V[i], X[i]));

    sort(uA.begin(), uA.end());
    uA.erase(unique(uA.begin(), uA.end()), uA.end());

    Nseg[0] = 0; Nseg[1] = uA.size() - 1;
    buildSeg();

    for(i=0;i<A.size();i++)
        replaceSegLeaf(mp(A[i], i), 0, 1);
    for(i=0;i<A.size();i++) {
        replaceSegLeaf(mp(A[i], i), 1, i - querySegCt(mp(A[i], i)));
        if(debug) cout << querySegCt(mp(A[i], i)) << " " << seg[1].ma << endl;
    }

    for(i=0; i<X.size(); i++) {
        updateSegMa(mp(A[X[i]], X[i]), 1);
        updateSegMa(mp(V[i], X[i]), -1);

        replaceSegLeaf(mp(A[X[i]], X[i]), 0, 0);
        replaceSegLeaf(mp(V[i], X[i]), 0, 1);

        replaceSegLeaf(mp(A[X[i]], X[i]), 1, -MX);
        replaceSegLeaf(mp(V[i], X[i]), 1, X[i] - querySegCt(mp(V[i], X[i])));

        A[X[i]] = V[i];
        ret.pb(seg[1].ma);

        if(debug) cout << seg[1].ma << endl;
    }

    return ret;

}

Compilation message (stderr)

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:194:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  194 |     for(i=0; i<A.size();i++) uA.pb(mp(A[i], i));
      |              ~^~~~~~~~~
bubblesort2.cpp:195:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  195 |     for(i=0; i<V.size();i++) uA.pb(mp(V[i], X[i]));
      |              ~^~~~~~~~~
bubblesort2.cpp:203:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  203 |     for(i=0;i<A.size();i++)
      |             ~^~~~~~~~~
bubblesort2.cpp:205:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  205 |     for(i=0;i<A.size();i++) {
      |             ~^~~~~~~~~
bubblesort2.cpp:210:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  210 |     for(i=0; i<X.size(); i++) {
      |              ~^~~~~~~~~
bubblesort2.cpp:191:12: warning: unused variable 'j' [-Wunused-variable]
  191 |     int i, j, k;
      |            ^
bubblesort2.cpp:191:15: warning: unused variable 'k' [-Wunused-variable]
  191 |     int i, j, k;
      |               ^
bubblesort2.cpp: In function 'void setIO(std::string)':
bubblesort2.cpp:54:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   54 |     freopen((name+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
bubblesort2.cpp:55:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   55 |     freopen((name+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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