oj.uz

Submission #1043589

# Submission time Handle Problem Language Result Execution time Memory
1043589 2024-08-04T11:47:01 Z underwaterkillerwhale Bubble Sort 2 (JOI18_bubblesort2) C++17
39 / 100
 70 ms 89044 KB 
#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for (auto id : v)
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }

const int N = 5e5 + 7;
const int Mod = 1e9 + 7;
const int INF = 2e9;
const ll BASE = 137;

int n, nval, Q;
int a[N];
pair<int,int> qr[N];
vector<int> vals;
set<int,greater<int>> pos[(int)1e6 + 7];

struct Segment_Tree {
    struct Node {
        int val, fs;
        Node () : fs(0), val(0) {};
    };
    int m;
    Node st[((int)1e6 + 7) << 2];
    int lz[((int)1e6 + 7) << 2];

    void init (int n) {
        m = n;
    }

    void down (int id) {
        rep (i, id << 1, id << 1 | 1) {
            st[i].val += lz[id];
            lz[i] += lz[id];
        }
        lz[id] = 0;
    }

    void update (int id, int l, int r, int u, int v, int val) {
        if (l > v || r < u) return;
        if (l >= u && r <= v) {
            st[id].val += val;
            lz[id] += val;
            return;
        }
        int mid = l + r >> 1;
        down(id);
        update (id << 1, l, mid, u, v, val);
        update (id << 1 | 1, mid + 1, r, u, v, val);
        st[id].val = max(st[id << 1].val, st[id << 1 | 1].val);
    }

    void Assign (int id, int l, int r, int pos, int val) {
        if (l > pos || r < pos) return;
        if (l == r) {
            st[id].val += val - st[id].fs;
            st[id].fs = val;
            return;
        }
        int mid = l + r >> 1;
        down(id);
        Assign (id << 1, l, mid, pos, val);
        Assign (id << 1 | 1, mid + 1, r, pos, val);
        st[id].val = max(st[id << 1].val, st[id << 1 | 1].val);
    }

    void update (int u, int v, int val) {
        update (1, 1, m, u, v, val);
    }

    void Assign (int pos, int val) {
        Assign (1, 1, m, pos, val);
    }
}ST;

int cps (int x) {
    return lower_bound(ALL(vals), x) - vals.begin() + 1;
}

//void solution() {
vector<int> countScans(vector<int> A, vector<int> X, vector<int> V) {
//    cin >> n;
//    rep (i, 1, n) cin >> a[i];
//    cin >> Q;
//    rep (i, 1, Q) cin >> qr[i].fs >> qr[i].se;
    n = SZ(A);
    Q = SZ(X);
    rep (i, 1, n) a[i] = A[i - 1];
    rep (i, 1, Q) qr[i].fs = X[i - 1], qr[i].se = V[i - 1];

    rep (i, 1, n) vals.push_back(qr[i].se);
    rep (i, 1, Q) vals.push_back(a[i]);
    sort (ALL(vals));
    vals.resize(nval = unique(ALL(vals)) - vals.begin());
    rep (i, 1, n) a[i] = cps(a[i]);
    rep (i, 1, Q) qr[i].se = cps(qr[i].se);
    ST.init(nval);
    rep (i, 1, n) {
        pos[a[i]].insert(i);
        ST.Assign(a[i], i);
        ST.update (a[i], nval, -1);
    }
    rep (i, 1, nval) pos[i].insert(0);
    vector<int> Ans;
    rep (i, 1, Q) {
        int p, val;
        tie(p, val) = qr[i];
        ++p;
        pos[a[p]].erase(p);
        pos[val].insert(p);
        ST.Assign(a[p], *pos[a[p]].begin());
        ST.update(a[p], nval, 1);
        ST.Assign(val, *pos[val].begin());
        ST.update(val, nval, -1);
        a[p] = val;
        Ans.push_back(ST.st[1].val);
//        cout << ST.st[1].val <<"\n";
    }
    return Ans;

}

//#define file(name) freopen(name".inp","r",stdin); \
//freopen(name".out","w",stdout);
//int main () {
////    file("c");
//    ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
//    int num_Test = 1;
////    cin >> num_Test;
//    while (num_Test--)
//        solution();
//}
/*
no bug challenge +2
4
1 2 3 4
2
0 3
2 1
*/

Compilation message

bubblesort2.cpp:134:1: warning: multi-line comment [-Wcomment]
  134 | //#define file(name) freopen(name".inp","r",stdin); \
      | ^
bubblesort2.cpp: In constructor 'Segment_Tree::Node::Node()':
bubblesort2.cpp:6:12: warning: 'Segment_Tree::Node::first' will be initialized after [-Wreorder]
    6 | #define fs first
      |            ^~~~~
bubblesort2.cpp:31:18: note: in expansion of macro 'fs'
   31 |         int val, fs;
      |                  ^~
bubblesort2.cpp:31:13: warning:   'int Segment_Tree::Node::val' [-Wreorder]
   31 |         int val, fs;
      |             ^~~
bubblesort2.cpp:32:9: warning:   when initialized here [-Wreorder]
   32 |         Node () : fs(0), val(0) {};
      |         ^~~~
bubblesort2.cpp: In member function 'void Segment_Tree::update(int, int, int, int, int, int)':
bubblesort2.cpp:57:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |         int mid = l + r >> 1;
      |                   ~~^~~
bubblesort2.cpp: In member function 'void Segment_Tree::Assign(int, int, int, int, int)':
bubblesort2.cpp:71:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   71 |         int mid = l + r >> 1;
      |                   ~~^~~

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 84824 KB Output is correct
2 Correct 12 ms 84828 KB Output is correct
3 Correct 14 ms 84960 KB Output is correct
4 Correct 15 ms 85096 KB Output is correct
5 Correct 15 ms 84948 KB Output is correct
6 Correct 14 ms 85084 KB Output is correct
7 Correct 14 ms 84960 KB Output is correct
8 Correct 14 ms 85084 KB Output is correct
9 Correct 14 ms 85084 KB Output is correct
10 Correct 12 ms 84828 KB Output is correct
11 Correct 13 ms 84952 KB Output is correct
12 Correct 14 ms 85080 KB Output is correct
13 Correct 14 ms 85008 KB Output is correct
14 Correct 15 ms 84968 KB Output is correct
15 Correct 14 ms 84824 KB Output is correct
16 Correct 13 ms 84828 KB Output is correct
17 Correct 13 ms 84976 KB Output is correct
18 Correct 13 ms 85040 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 84824 KB Output is correct
2 Correct 12 ms 84828 KB Output is correct
3 Correct 14 ms 84960 KB Output is correct
4 Correct 15 ms 85096 KB Output is correct
5 Correct 15 ms 84948 KB Output is correct
6 Correct 14 ms 85084 KB Output is correct
7 Correct 14 ms 84960 KB Output is correct
8 Correct 14 ms 85084 KB Output is correct
9 Correct 14 ms 85084 KB Output is correct
10 Correct 12 ms 84828 KB Output is correct
11 Correct 13 ms 84952 KB Output is correct
12 Correct 14 ms 85080 KB Output is correct
13 Correct 14 ms 85008 KB Output is correct
14 Correct 15 ms 84968 KB Output is correct
15 Correct 14 ms 84824 KB Output is correct
16 Correct 13 ms 84828 KB Output is correct
17 Correct 13 ms 84976 KB Output is correct
18 Correct 13 ms 85040 KB Output is correct
19 Incorrect 21 ms 85996 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 86364 KB Output is correct
2 Correct 41 ms 87676 KB Output is correct
3 Correct 60 ms 89032 KB Output is correct
4 Correct 70 ms 89032 KB Output is correct
5 Correct 58 ms 89032 KB Output is correct
6 Correct 63 ms 89036 KB Output is correct
7 Correct 56 ms 88920 KB Output is correct
8 Correct 58 ms 88920 KB Output is correct
9 Correct 58 ms 89044 KB Output is correct
10 Correct 47 ms 89036 KB Output is correct
11 Correct 45 ms 89036 KB Output is correct
12 Correct 47 ms 89036 KB Output is correct
13 Correct 45 ms 89036 KB Output is correct
14 Correct 46 ms 89036 KB Output is correct
15 Correct 46 ms 89044 KB Output is correct
16 Correct 42 ms 89036 KB Output is correct
17 Correct 43 ms 88888 KB Output is correct
18 Correct 47 ms 89036 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 84824 KB Output is correct
2 Correct 12 ms 84828 KB Output is correct
3 Correct 14 ms 84960 KB Output is correct
4 Correct 15 ms 85096 KB Output is correct
5 Correct 15 ms 84948 KB Output is correct
6 Correct 14 ms 85084 KB Output is correct
7 Correct 14 ms 84960 KB Output is correct
8 Correct 14 ms 85084 KB Output is correct
9 Correct 14 ms 85084 KB Output is correct
10 Correct 12 ms 84828 KB Output is correct
11 Correct 13 ms 84952 KB Output is correct
12 Correct 14 ms 85080 KB Output is correct
13 Correct 14 ms 85008 KB Output is correct
14 Correct 15 ms 84968 KB Output is correct
15 Correct 14 ms 84824 KB Output is correct
16 Correct 13 ms 84828 KB Output is correct
17 Correct 13 ms 84976 KB Output is correct
18 Correct 13 ms 85040 KB Output is correct
19 Incorrect 21 ms 85996 KB Output isn't correct
20 Halted 0 ms 0 KB -