oj.uz

Submission #146218

# Submission time Handle Problem Language Result Execution time Memory
146218 2019-08-22T20:49:47 Z nicolaalexandra Bubble Sort 2 (JOI18_bubblesort2) C++14
0 / 100
 30 ms 1652 KB 
#include <fstream>
#include <algorithm>
#include <vector>
#define DIM 1000010
#define INF 1000010
using namespace std;
 
pair <int,int> aint[4*DIM];
void lazy (int nod, int st, int dr){
    if (!aint[nod].second)
        return;
    aint[nod].first += aint[nod].second;
    if (st != dr){ /// nu e frunza
        aint[nod<<1].second += aint[nod].second;
        aint[(nod<<1)|1].second += aint[nod].second;
    }
    aint[nod].second = 0;
}
void update (int nod, int st, int dr, int x, int y, int val){
    lazy (nod,st,dr);
    if (st > dr || y < st || x > dr)
        return;
    if (x <= st && dr <= y){
        aint[nod].second += val;
        lazy (nod,st,dr);
        return;
    }
    int mid = (st+dr)>>1;
    update (nod<<1,st,mid,x,y,val);
    update ((nod<<1)|1,mid+1,dr,x,y,val);
    aint[nod].first = max (aint[nod<<1].first,aint[(nod<<1)|1].first);
}
inline int cautare_binara (long long v[], int n, long long val){
    int st = 1, dr = n;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (v[mid] < val)
            st = mid+1;
        else dr = mid-1;
    }
    return st;
}
vector <int> countScans (vector <int> a, vector <int> x, vector <int> v){
    int k = 0, n = a.size(), q = v.size();
    long long w[DIM*2],qry[DIM*2];
    vector <long long> A;
    for (int i=0;i<n;i++){
        A.push_back((long long)(1LL*a[i]*(n+1)+i)); /// fac asta ca sa obtin elemente distincte pe care dupa le normalizez
        w[++k] = A[i];
    }
    for (int i=0;i<q;i++){
        qry[i] = (long long)(1LL*v[i]*(n+1)+x[i]);
        w[++k] = qry[i];
    }
    sort (w+1,w+k+1);
    update (1,1,k,1,k,-INF); /// initializez cu -INF, apoi adaug INF+i
    /// starea initiala
    for (int i=0;i<n;i++){
        int val = cautare_binara(w,k,A[i]);
        update (1,1,k,val,val,INF+i); /// am i puncte mai mici decat el in stanga lui
        update (1,1,k,1,val,1);
    }
    vector <int> sol;
    for (int i=0;i<q;i++){
        int poz = cautare_binara (w,k,A[x[i]]);
        update (1,1,k,1,poz,-1);
        update (1,1,k,poz,poz,-INF-x[i]);
        a[x[i]] = qry[i];
 
        poz = cautare_binara (w,k,qry[i]);
        update (1,1,k,poz,poz,INF+x[i]);
        update (1,1,k,1,poz,1);
 
        sol.push_back(aint[1].first+aint[1].second - n);
    }
    return sol;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 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 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 30 ms 1652 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 376 KB Output isn't correct
2 Halted 0 ms 0 KB -