oj.uz

Submission #146215

# Submission time Handle Problem Language Result Execution time Memory
146215 2019-08-22T20:30:13 Z nicolaalexandra Bubble Sort 2 (JOI18_bubblesort2) C++14
22 / 100
 176 ms 5368 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)
            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+aint[1].second - 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 89 ms 2936 KB Output is correct
3 Correct 169 ms 5368 KB Output is correct
4 Correct 176 ms 5240 KB Output is correct
5 Correct 172 ms 5196 KB Output is correct
6 Correct 164 ms 5112 KB Output is correct
7 Correct 163 ms 5084 KB Output is correct
8 Correct 169 ms 5232 KB Output is correct
9 Correct 160 ms 5112 KB Output is correct
10 Correct 137 ms 4088 KB Output is correct
11 Correct 128 ms 4176 KB Output is correct
12 Correct 132 ms 4148 KB Output is correct
13 Correct 128 ms 4120 KB Output is correct
14 Correct 124 ms 4088 KB Output is correct
15 Correct 122 ms 4088 KB Output is correct
16 Correct 115 ms 4088 KB Output is correct
17 Correct 116 ms 4088 KB Output is correct
18 Correct 117 ms 4132 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 -