oj.uz

Submission #1043581

# Submission time Handle Problem Language Result Execution time Memory
1043581 2024-08-04T11:43:01 Z underwaterkillerwhale Bubble Sort 2 (JOI18_bubblesort2) C++17
39 / 100
 58 ms 73428 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[N << 2];
    ll lz[N << 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 11 ms 68184 KB Output is correct
2 Correct 10 ms 68444 KB Output is correct
3 Correct 12 ms 68728 KB Output is correct
4 Correct 13 ms 68944 KB Output is correct
5 Correct 12 ms 68952 KB Output is correct
6 Correct 12 ms 68700 KB Output is correct
7 Correct 11 ms 68596 KB Output is correct
8 Correct 11 ms 68700 KB Output is correct
9 Correct 12 ms 68696 KB Output is correct
10 Correct 12 ms 68696 KB Output is correct
11 Correct 11 ms 68700 KB Output is correct
12 Correct 11 ms 68696 KB Output is correct
13 Correct 12 ms 68444 KB Output is correct
14 Correct 11 ms 68444 KB Output is correct
15 Correct 11 ms 68612 KB Output is correct
16 Correct 12 ms 68676 KB Output is correct
17 Correct 13 ms 68444 KB Output is correct
18 Correct 13 ms 68444 KB Output is correct

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 68184 KB Output is correct
2 Correct 10 ms 68444 KB Output is correct
3 Correct 12 ms 68728 KB Output is correct
4 Correct 13 ms 68944 KB Output is correct
5 Correct 12 ms 68952 KB Output is correct
6 Correct 12 ms 68700 KB Output is correct
7 Correct 11 ms 68596 KB Output is correct
8 Correct 11 ms 68700 KB Output is correct
9 Correct 12 ms 68696 KB Output is correct
10 Correct 12 ms 68696 KB Output is correct
11 Correct 11 ms 68700 KB Output is correct
12 Correct 11 ms 68696 KB Output is correct
13 Correct 12 ms 68444 KB Output is correct
14 Correct 11 ms 68444 KB Output is correct
15 Correct 11 ms 68612 KB Output is correct
16 Correct 12 ms 68676 KB Output is correct
17 Correct 13 ms 68444 KB Output is correct
18 Correct 13 ms 68444 KB Output is correct
19 Incorrect 18 ms 69720 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 18 ms 69980 KB Output is correct
2 Correct 41 ms 71728 KB Output is correct
3 Correct 58 ms 73156 KB Output is correct
4 Correct 57 ms 73164 KB Output is correct
5 Correct 57 ms 73352 KB Output is correct
6 Correct 55 ms 73164 KB Output is correct
7 Correct 56 ms 73360 KB Output is correct
8 Correct 56 ms 73416 KB Output is correct
9 Correct 55 ms 73268 KB Output is correct
10 Correct 46 ms 73428 KB Output is correct
11 Correct 44 ms 73416 KB Output is correct
12 Correct 48 ms 73388 KB Output is correct
13 Correct 49 ms 73420 KB Output is correct
14 Correct 42 ms 73304 KB Output is correct
15 Correct 42 ms 73416 KB Output is correct
16 Correct 40 ms 73420 KB Output is correct
17 Correct 42 ms 73420 KB Output is correct
18 Correct 41 ms 73428 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 68184 KB Output is correct
2 Correct 10 ms 68444 KB Output is correct
3 Correct 12 ms 68728 KB Output is correct
4 Correct 13 ms 68944 KB Output is correct
5 Correct 12 ms 68952 KB Output is correct
6 Correct 12 ms 68700 KB Output is correct
7 Correct 11 ms 68596 KB Output is correct
8 Correct 11 ms 68700 KB Output is correct
9 Correct 12 ms 68696 KB Output is correct
10 Correct 12 ms 68696 KB Output is correct
11 Correct 11 ms 68700 KB Output is correct
12 Correct 11 ms 68696 KB Output is correct
13 Correct 12 ms 68444 KB Output is correct
14 Correct 11 ms 68444 KB Output is correct
15 Correct 11 ms 68612 KB Output is correct
16 Correct 12 ms 68676 KB Output is correct
17 Correct 13 ms 68444 KB Output is correct
18 Correct 13 ms 68444 KB Output is correct
19 Incorrect 18 ms 69720 KB Output isn't correct
20 Halted 0 ms 0 KB -