oj.uz

답안 #128743

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
128743 2019-07-11T08:54:49 Z EntityIT Bubble Sort 2 (JOI18_bubblesort2) C++14
38 / 100
 63 ms 48240 KB 
#include "bubblesort2.h"
#include<bits/stdc++.h>

using namespace std;

#define pb push_back

const int N = (int)5e5 + 5, Q = N, inf = (int)1e9 + 123;
int n, q, order_q[N], order_a[N];

struct It {
    struct Node {
        int cnt, mx, lz;
        Node (int _cnt = 0, int _mx = -inf, int _lz = 0) : cnt(_cnt), mx(_mx), lz(_lz) {}
        Node operator+ (const Node &_) const { return Node(cnt + _.cnt, max(mx, _.mx), 0); }
    } node[N << 3];
    void true_val (int nd, int Left, int Right) {
        if (!node[nd].lz) return ;
        node[nd].mx += node[nd].lz;
        if (Left != Right) {
            node[nd << 1].lz += node[nd].lz;
            node[nd << 1 | 1].lz += node[nd].lz;
        }
        node[nd].lz = 0;
    }
    void upd_rep (int nd, int Left, int Right, int pos, int val_mx, int val_cnt) {
        true_val(nd, Left, Right);
        if (pos < Left || Right < pos) return ;
        if (Left == Right) {
            node[nd] = Node(val_cnt, val_mx, 0);
            return ;
        }
        int mid = (Left + Right) >> 1;
        upd_rep(nd << 1, Left, mid, pos, val_mx, val_cnt);
        upd_rep(nd << 1 | 1, mid + 1, Right, pos, val_mx, val_cnt);
        node[nd] = node[nd << 1] + node[nd << 1 | 1];
    }
    void upd_add (int nd, int Left, int Right, int l, int r, int val) {
        true_val(nd, Left, Right);
        if (r < Left || Right < l) return ;
        if (l <= Left && Right <= r) {
            node[nd].lz = val; true_val(nd, Left, Right);
            return ;
        }
        int mid = (Left + Right) >> 1;
        upd_add(nd << 1, Left, mid, l, r, val);
        upd_add(nd << 1 | 1, mid + 1, Right, l, r, val);
        node[nd] = node[nd << 1] + node[nd << 1 | 1];
    }
    int get_cnt (int nd, int Left, int Right, int l, int r) {
        true_val(nd, Left, Right);
        if (r < Left || Right < l) return 0;
        if (l <= Left && Right <= r) return node[nd].cnt;
        int mid = (Left + Right) >> 1;
        return get_cnt(nd << 1, Left, mid, l, r) + get_cnt(nd << 1 | 1, mid + 1, Right, l, r);
    }
} it;

struct Vec_ele {
    int val, pos_a, dstnct;
    Vec_ele (int _val = 0, int _pos_a = 0, int _dstnct = 0) : val(_val), pos_a(_pos_a), dstnct(_dstnct) {}
    bool operator< (const Vec_ele &_) const { return val < _.val; }
};

vector<int> countScans (vector<int> a, vector<int> x, vector<int> v) {
    n = (int)a.size(); q = (int)x.size();

    vector<Vec_ele> vec;
    for (int i = 0; i < n; ++i) vec.pb( Vec_ele(a[i], i, i) );
    for (int i = 0; i < q; ++i) vec.pb( Vec_ele(v[i], x[i], i + n) );
    sort(vec.begin(), vec.end() );

    for (int i = 0; i < (int)vec.size(); ++i) {
        int pos_a = vec[i].pos_a, dstnct = vec[i].dstnct;
        if (dstnct < n) {
            order_a[dstnct] = i;
            int up_val = pos_a - it.get_cnt(1, 0, (int)vec.size() - 1, 0, i);
            it.upd_rep(1, 0, (int)vec.size() - 1, order_a[dstnct], up_val, 1);
        }
        else order_q[dstnct - n] = i;
    }

    vector<int> ret(q);

    for (int i = 0; i < q; ++i) {
        it.upd_add(1, 0, (int)vec.size() - 1, order_a[ x[i] ], (int)vec.size() - 1, 1);
        it.upd_rep(1, 0, (int)vec.size() - 1, order_a[ x[i] ], -inf, 0);
        order_a[ x[i] ] = order_q[i];
        it.upd_add(1, 0, (int)vec.size() - 1, order_a[ x[i] ], (int)vec.size() - 1, -1);
        int up_val = x[i] - it.get_cnt(1, 0, (int)vec.size() - 1, 0, order_a[ x[i] ]);
        it.upd_rep(1, 0, (int)vec.size() - 1, order_a[ x[i] ], up_val, 1);
        ret[i] = it.node[1].mx;
    }

    return ret;
}

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 47352 KB Output is correct
2 Correct 44 ms 47352 KB Output is correct
3 Correct 47 ms 47480 KB Output is correct
4 Correct 47 ms 47480 KB Output is correct
5 Correct 46 ms 47480 KB Output is correct
6 Correct 46 ms 47552 KB Output is correct
7 Correct 47 ms 47536 KB Output is correct
8 Correct 54 ms 47480 KB Output is correct
9 Correct 46 ms 47480 KB Output is correct
10 Correct 47 ms 47480 KB Output is correct
11 Correct 46 ms 47480 KB Output is correct
12 Correct 48 ms 47480 KB Output is correct
13 Correct 46 ms 47480 KB Output is correct
14 Correct 46 ms 47608 KB Output is correct
15 Correct 46 ms 47564 KB Output is correct
16 Correct 46 ms 47480 KB Output is correct
17 Correct 46 ms 47480 KB Output is correct
18 Correct 46 ms 47480 KB Output is correct

Subtask #2
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 47352 KB Output is correct
2 Correct 44 ms 47352 KB Output is correct
3 Correct 47 ms 47480 KB Output is correct
4 Correct 47 ms 47480 KB Output is correct
5 Correct 46 ms 47480 KB Output is correct
6 Correct 46 ms 47552 KB Output is correct
7 Correct 47 ms 47536 KB Output is correct
8 Correct 54 ms 47480 KB Output is correct
9 Correct 46 ms 47480 KB Output is correct
10 Correct 47 ms 47480 KB Output is correct
11 Correct 46 ms 47480 KB Output is correct
12 Correct 48 ms 47480 KB Output is correct
13 Correct 46 ms 47480 KB Output is correct
14 Correct 46 ms 47608 KB Output is correct
15 Correct 46 ms 47564 KB Output is correct
16 Correct 46 ms 47480 KB Output is correct
17 Correct 46 ms 47480 KB Output is correct
18 Correct 46 ms 47480 KB Output is correct
19 Correct 59 ms 48184 KB Output is correct
20 Correct 61 ms 48056 KB Output is correct
21 Correct 62 ms 48076 KB Output is correct
22 Correct 63 ms 48056 KB Output is correct
23 Correct 62 ms 48056 KB Output is correct
24 Correct 61 ms 48056 KB Output is correct
25 Correct 61 ms 48184 KB Output is correct
26 Correct 60 ms 48056 KB Output is correct
27 Correct 59 ms 48056 KB Output is correct
28 Correct 60 ms 48060 KB Output is correct

Subtask #3
0 / 22.0

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

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 43 ms 47352 KB Output is correct
2 Correct 44 ms 47352 KB Output is correct
3 Correct 47 ms 47480 KB Output is correct
4 Correct 47 ms 47480 KB Output is correct
5 Correct 46 ms 47480 KB Output is correct
6 Correct 46 ms 47552 KB Output is correct
7 Correct 47 ms 47536 KB Output is correct
8 Correct 54 ms 47480 KB Output is correct
9 Correct 46 ms 47480 KB Output is correct
10 Correct 47 ms 47480 KB Output is correct
11 Correct 46 ms 47480 KB Output is correct
12 Correct 48 ms 47480 KB Output is correct
13 Correct 46 ms 47480 KB Output is correct
14 Correct 46 ms 47608 KB Output is correct
15 Correct 46 ms 47564 KB Output is correct
16 Correct 46 ms 47480 KB Output is correct
17 Correct 46 ms 47480 KB Output is correct
18 Correct 46 ms 47480 KB Output is correct
19 Correct 59 ms 48184 KB Output is correct
20 Correct 61 ms 48056 KB Output is correct
21 Correct 62 ms 48076 KB Output is correct
22 Correct 63 ms 48056 KB Output is correct
23 Correct 62 ms 48056 KB Output is correct
24 Correct 61 ms 48056 KB Output is correct
25 Correct 61 ms 48184 KB Output is correct
26 Correct 60 ms 48056 KB Output is correct
27 Correct 59 ms 48056 KB Output is correct
28 Correct 60 ms 48060 KB Output is correct
29 Incorrect 58 ms 48240 KB Output isn't correct
30 Halted 0 ms 0 KB -