oj.uz

답안 #364509

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
364509 2021-02-09T11:40:21 Z buyolitsez Bubble Sort 2 (JOI18_bubblesort2) C++17
0 / 100
 193 ms 6896 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){
    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) {
        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 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:87:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for (int i = 0; i < xx.size(); ++i) {
      |                     ~~^~~~~~~~~~~

Subtask #1
0 / 17.0

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

Subtask #2
0 / 21.0

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

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 2172 KB Output is correct
2 Correct 112 ms 4380 KB Output is correct
3 Incorrect 193 ms 6896 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

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