oj.uz

Submission #146216

# Submission time Handle Problem Language Result Execution time Memory
146216 2019-08-22T20:37:38 Z nicolaalexandra Bubble Sort 2 (JOI18_bubblesort2) C++14
22 / 100
 167 ms 5248 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];
    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);
    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 380 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 380 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 161 ms 5240 KB Output is correct
4 Correct 167 ms 5236 KB Output is correct
5 Correct 163 ms 5084 KB Output is correct
6 Correct 161 ms 5072 KB Output is correct
7 Correct 160 ms 5084 KB Output is correct
8 Correct 161 ms 5156 KB Output is correct
9 Correct 161 ms 5156 KB Output is correct
10 Correct 138 ms 5248 KB Output is correct
11 Correct 137 ms 5112 KB Output is correct
12 Correct 139 ms 5248 KB Output is correct
13 Correct 135 ms 5188 KB Output is correct
14 Correct 140 ms 5240 KB Output is correct
15 Correct 149 ms 5112 KB Output is correct
16 Correct 129 ms 5084 KB Output is correct
17 Correct 129 ms 5168 KB Output is correct
18 Correct 130 ms 5112 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -