oj.uz

Submission #146217

# Submission time Handle Problem Language Result Execution time Memory
146217 2019-08-22T20:41:52 Z nicolaalexandra Bubble Sort 2 (JOI18_bubblesort2) C++14
22 / 100
 168 ms 5240 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)(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 632 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 632 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 92 ms 3012 KB Output is correct
3 Correct 163 ms 5112 KB Output is correct
4 Correct 166 ms 5240 KB Output is correct
5 Correct 162 ms 5112 KB Output is correct
6 Correct 168 ms 5240 KB Output is correct
7 Correct 162 ms 5112 KB Output is correct
8 Correct 166 ms 5132 KB Output is correct
9 Correct 163 ms 5240 KB Output is correct
10 Correct 139 ms 5136 KB Output is correct
11 Correct 136 ms 5116 KB Output is correct
12 Correct 137 ms 5220 KB Output is correct
13 Correct 137 ms 5156 KB Output is correct
14 Correct 135 ms 5212 KB Output is correct
15 Correct 135 ms 5116 KB Output is correct
16 Correct 131 ms 5112 KB Output is correct
17 Correct 129 ms 5196 KB Output is correct
18 Correct 129 ms 5236 KB Output is correct

Subtask #4
0 / 40.0

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