oj.uz

Submission #146212

# Submission time Handle Problem Language Result Execution time Memory
146212 2019-08-22T20:22:56 Z nicolaalexandra Bubble Sort 2 (JOI18_bubblesort2) C++14
22 / 100
 164 ms 5852 KB 
#include <fstream>
#include <algorithm>
#include <vector>
#define DIM 500010
#define INF 2000000000
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)
            return mid;
        if (v[mid] < val)
            st = mid+1;
        else dr = mid-1;
    }}
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];
    for (int i=0;i<n;i++){
        a[i] = (long long)(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)(v[i]*(n+1)+x[i]);
        w[++k] = qry[i];
    }
    sort (w+1,w+k+1);
    int k2 = 1;
    for (int i=2;i<=k;i++)
        if (w[i] != w[i-1])
            w[++k2] = w[i];
    k = k2;
    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 - n);
    }
    return sol;
}

Compilation message

bubblesort2.cpp: In function 'int cautare_binara(long long int*, int, long long int)':
bubblesort2.cpp:42:6: warning: control reaches end of non-void function [-Wreturn-type]
     }}
      ^

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
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1400 KB Output is correct
2 Correct 94 ms 3320 KB Output is correct
3 Correct 164 ms 5852 KB Output is correct
4 Correct 161 ms 5624 KB Output is correct
5 Correct 160 ms 5744 KB Output is correct
6 Correct 159 ms 5752 KB Output is correct
7 Correct 159 ms 5752 KB Output is correct
8 Correct 158 ms 5628 KB Output is correct
9 Correct 159 ms 5752 KB Output is correct
10 Correct 134 ms 4728 KB Output is correct
11 Correct 126 ms 4792 KB Output is correct
12 Correct 126 ms 4736 KB Output is correct
13 Correct 125 ms 4776 KB Output is correct
14 Correct 127 ms 4700 KB Output is correct
15 Correct 121 ms 4732 KB Output is correct
16 Correct 115 ms 4864 KB Output is correct
17 Correct 117 ms 4876 KB Output is correct
18 Correct 116 ms 4804 KB Output is correct

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 -