oj.uz

Submission #364531

# Submission time Handle Problem Language Result Execution time Memory
364531 2021-02-09T12:14:16 Z buyolitsez Bubble Sort 2 (JOI18_bubblesort2) C++17
22 / 100
 280 ms 21852 KB 
#include "bubblesort2.h"
#include <bits/stdc++.h>

using namespace std;

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")

#define eb emplace_back

typedef long long ll;

auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
mt19937 rnd(seed);


const int MAXN = 1e6 + 15;
const int ADD = 1e6;

int t[4 * MAXN], tadd[4 * MAXN];
int f[MAXN];

void Update(int pos, int val) {
    for(;pos < MAXN; pos = (pos | (pos + 1))) {
        f[pos] += val;
    }
}

int Sum(int pos) {
    int ans = 0;
    for(; pos >= 0; pos = (pos & (pos + 1)) - 1) {
        ans += f[pos];
    }
    return ans;
}

void Push(int v, int vl, int vr) {
    if (tadd[v]) {
        t[v] += tadd[v];
        if (vl != vr) {
            tadd[2 * v + 1] += tadd[v];
            tadd[2 * v + 2] += tadd[v];
        }
        tadd[v] = 0;
    }
}

void Update(int l, int r, int val, int v = 0, int vl = 0, int vr = MAXN - 1) {
    Push(v, vl, vr);
    if (vr < l || r < vl) {return;}
    if (vl >= l && vr <= r) {
        tadd[v] += val;
        Push(v, vl, vr);
        return;
    }
    int vm = vl + (vr - vl) / 2;
    Update(l, r, val, 2 * v + 1, vl, vm);
    Update(l, r, val, 2 * v + 2, vm + 1, vr);
    t[v] = max(t[2 * v + 1], t[2 * v + 2]);
}

int Query(int pos, int v = 0, int vl = 0, int vr = MAXN - 1) {
    Push(v, vl, vr);
    if (vl == vr) {
        return t[v];
    }
    int vm = vl + (vr - vl) / 2;
    if (pos <= vm) {
        return Query(pos, 2 * v + 1, vl, vm);
    }
    return Query(pos, 2 * v + 2, vm + 1, vr);
}

int GetMx() {
    Push(0, 0, MAXN - 1);
    return t[0];
}

std::vector<int> countScans(std::vector<int> aa,std::vector<int> xx,std::vector<int> vv){
    fill(t, t + 4 * MAXN, -(int)1e9);
    vector <ll> a, x, v, all;
    int n = aa.size(), q = xx.size();
    for (int i = 0; i < n; ++i) {
        a.eb(aa[i] * ADD + i);
        all.eb(a[i]);
    }
    for (int i = 0; i < xx.size(); ++i) {
        x.eb(xx[i]);
        v.eb(vv[i] * ADD + xx[i]);
        all.eb(v[i]);
    }
    sort(all.begin(), all.end());
    all.resize(unique(all.begin(), all.end()) - all.begin());
    for (int i = 0; i < n; ++i) {
        a[i] = lower_bound(all.begin(), all.end(), a[i]) - all.begin();
        Update(a[i], 1);
    }
    for (int i = 0; i < n; ++i) {
        int val = Query(a[i]);
        Update(a[i], a[i], -val);
        Update(a[i], a[i], i);
        int cntLess = Sum(a[i] - 1);
        Update(a[i], a[i], -cntLess);
    }
    for (auto &u : v) {
        u = lower_bound(all.begin(), all.end(), u) - all.begin();
    }
    vector <int> s;
    for(int f = 0; f < q; ++f) {
        int pos = x[f];
        int x = a[pos];
        int y = v[f];
        a[pos] = y;
        Update(x + 1, MAXN - 1, 1);
        Update(y + 1, MAXN - 1, -1);
        Update(x, -1);
        Update(y, 1);
        int val = Query(x);
        Update(x, x, -val - (int)1e9);
        int cntLess = Sum(y - 1);
        int nowVal = Query(y);
        Update(y, y, -nowVal + (pos - cntLess));
        s.eb(GetMx());
    }
    return s;
}

Compilation message

bubblesort2.cpp: In function 'std::vector<int> countScans(std::vector<int>, std::vector<int>, std::vector<int>)':
bubblesort2.cpp:88:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |     for (int i = 0; i < xx.size(); ++i) {
      |                     ~~^~~~~~~~~~~

Subtask #1
0 / 17.0

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

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 16236 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 65 ms 17384 KB Output is correct
2 Correct 155 ms 19216 KB Output is correct
3 Correct 280 ms 21084 KB Output is correct
4 Correct 254 ms 21744 KB Output is correct
5 Correct 258 ms 21852 KB Output is correct
6 Correct 250 ms 21616 KB Output is correct
7 Correct 263 ms 21596 KB Output is correct
8 Correct 263 ms 21852 KB Output is correct
9 Correct 258 ms 21596 KB Output is correct
10 Correct 230 ms 21212 KB Output is correct
11 Correct 227 ms 21212 KB Output is correct
12 Correct 220 ms 21212 KB Output is correct
13 Correct 220 ms 21212 KB Output is correct
14 Correct 220 ms 21212 KB Output is correct
15 Correct 217 ms 21388 KB Output is correct
16 Correct 211 ms 21340 KB Output is correct
17 Correct 214 ms 21212 KB Output is correct
18 Correct 211 ms 21212 KB Output is correct

Subtask #4
0 / 40.0

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