oj.uz

답안 #364539

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
364539 2021-02-09T12:35:10 Z buyolitsez Bubble Sort 2 (JOI18_bubblesort2) C++17
22 / 100
 297 ms 21232 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 16236 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 16236 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 63 ms 17384 KB Output is correct
2 Correct 152 ms 19088 KB Output is correct
3 Correct 258 ms 21084 KB Output is correct
4 Correct 297 ms 21212 KB Output is correct
5 Correct 268 ms 21228 KB Output is correct
6 Correct 274 ms 21180 KB Output is correct
7 Correct 256 ms 21212 KB Output is correct
8 Correct 249 ms 21232 KB Output is correct
9 Correct 255 ms 21184 KB Output is correct
10 Correct 223 ms 20700 KB Output is correct
11 Correct 224 ms 20700 KB Output is correct
12 Correct 220 ms 20828 KB Output is correct
13 Correct 221 ms 20700 KB Output is correct
14 Correct 235 ms 20700 KB Output is correct
15 Correct 221 ms 20700 KB Output is correct
16 Correct 213 ms 20828 KB Output is correct
17 Correct 214 ms 20700 KB Output is correct
18 Correct 221 ms 20572 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 16236 KB Output isn't correct
2 Halted 0 ms 0 KB -