Submission #128961

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
128961	2019-07-11 11:24:59	EntityIT	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	2142 ms	89804 KiB

bubblesort2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#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 ;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 40 / 40