oj.uz

Submission #962347

# Submission time Handle Problem Language Result Execution time Memory
962347 2024-04-13T11:01:42 Z alextodoran Fish 2 (JOI22_fish2) C++17
5 / 100
 4000 ms 34576 KB 
/**
 _  _   __  _ _ _  _  _ _
 |a  ||t  ||o    d | |o  |
| __    _| | _ | __|  _ |
| __ |/_  | __  /__\ / _\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 100000;

int N;
ll A[N_MAX + 2];

struct Block {
    int l, r;
    bool contains (int i) {
        return (l <= i && i <= r);
    }
};

struct SegInfo {
    ll val; int cnt;
    ll lazy;
    void add (const ll &x) {
        val += x; lazy += x;
    }
};
SegInfo operator + (const SegInfo &A, const SegInfo &B) {
    SegInfo C;
    C.val = min(A.val, B.val);
    C.cnt = (C.val == A.val ? A.cnt : 0) + (C.val == B.val ? B.cnt : 0);
    C.lazy = 0;
    return C;
}
void build_tree (SegInfo seg_tree[], int node, int l, int r) {
    seg_tree[node].cnt = r - l + 1;
    if (l != r) {
        int mid = (l + r) / 2;
        int left = node * 2, right = node * 2 + 1;
        build_tree(seg_tree, left, l, mid);
        build_tree(seg_tree, right, mid + 1, r);
    }
}
void build_tree (SegInfo seg_tree[]) {
    build_tree(seg_tree, 1, 1, N);
}
void update_tree (SegInfo seg_tree[], int node, int l, int r, int ul, int ur, ll x) {
    if (ul <= l && r <= ur) {
        seg_tree[node].add(x);
        return;
    }
    int mid = (l + r) / 2;
    int left = node * 2, right = node * 2 + 1;
    seg_tree[left].add(seg_tree[node].lazy);
    seg_tree[right].add(seg_tree[node].lazy);
    seg_tree[node].lazy = 0;
    if (ul <= mid) {
        update_tree(seg_tree, left, l, mid, ul, ur, x);
    }
    if (mid + 1 <= ur) {
        update_tree(seg_tree, right, mid + 1, r, ul, ur, x);
    }
    seg_tree[node] = seg_tree[left] + seg_tree[right];
}
void update_tree (SegInfo seg_tree[], int ul, int ur, ll x) {
    update_tree(seg_tree, 1, 1, N, ul, ur, x);
}
void update_tree (SegInfo seg_tree[], int i, ll x) {
    update_tree(seg_tree, 1, 1, N, i, i, x);
}
SegInfo query_cnt (SegInfo seg_tree[], int node, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) {
        return seg_tree[node];
    }
    int mid = (l + r) / 2;
    int left = node * 2, right = node * 2 + 1;
    seg_tree[left].add(seg_tree[node].lazy);
    seg_tree[right].add(seg_tree[node].lazy);
    seg_tree[node].lazy = 0;
    if (ql <= mid && mid + 1 <= qr) {
        return query_cnt(seg_tree, left, l, mid, ql, qr)
             + query_cnt(seg_tree, right, mid + 1, r, ql, qr);
    } else if (qr <= mid) {
        return query_cnt(seg_tree, left, l, mid, ql, qr);
    } else {
        return query_cnt(seg_tree, right, mid + 1, r, ql, qr);
    }
}
int query_cnt (SegInfo seg_tree[], int ql, int qr) {
    return query_cnt(seg_tree, 1, 1, N, ql, qr).cnt;
}
int query_last (SegInfo seg_tree[], int node, int l, int r, int i, ll val) {
    if (l == r) {
        return (seg_tree[node].val <= val ? l : 0);
    }
    int mid = (l + r) / 2;
    int left = node * 2, right = node * 2 + 1;
    seg_tree[left].add(seg_tree[node].lazy);
    seg_tree[right].add(seg_tree[node].lazy);
    seg_tree[node].lazy = 0;
    if (i <= mid) {
        return query_last(seg_tree, left, l, mid, i, val);
    } else {
        int j = query_last(seg_tree, right, mid + 1, r, i, val);
        return (j != 0 ? j : query_last(seg_tree, left, l, mid, i, val));
    }
}
int query_last (SegInfo seg_tree[], int i, ll val) {
    return query_last(seg_tree, 1, 1, N, i, val);
}
int query_first (SegInfo seg_tree[], int node, int l, int r, int i, ll val) {
    if (l == r) {
        return (seg_tree[node].val <= val ? l : N + 1);
    }
    int mid = (l + r) / 2;
    int left = node * 2, right = node * 2 + 1;
    seg_tree[left].add(seg_tree[node].lazy);
    seg_tree[right].add(seg_tree[node].lazy);
    seg_tree[node].lazy = 0;
    if (mid + 1 <= i) {
        return query_first(seg_tree, right, mid + 1, r, i, val);
    } else {
        int j = query_first(seg_tree, left, l, mid, i, val);
        return (j != N + 1 ? j : query_first(seg_tree, right, mid + 1, r, i, val));
    }
}
int query_first (SegInfo seg_tree[], int i, ll val) {
    return query_first(seg_tree, 1, 1, N, i, val);
}

SegInfo min_tree[N_MAX * 4 + 2];

void add_block (Block b) {
    update_tree(min_tree, b.l, b.r, +1);
}
void del_block (Block b) {
    update_tree(min_tree, b.l, b.r, -1);
}

vector <Block> block_tree[N_MAX * 4 + 2];

void add_blocks (int node, int l, int r, int i, vector <Block> &blocks) {
    if (l != r) {
        int mid = (l + r) / 2;
        int left = node * 2, right = node * 2 + 1;
        if (i <= mid) {
            add_blocks(left, l, mid, i, blocks);
        } else {
            add_blocks(right, mid + 1, r, i, blocks);
        }
    }
    while (blocks.empty() == false && l <= blocks.back().l && blocks.back().r <= r) {
        add_block(blocks.back());
        block_tree[node].push_back(blocks.back());
        blocks.pop_back();
    }
}
void add_blocks (int i, vector <Block> &blocks) {
    add_blocks(1, 1, N, i, blocks);
}
void del_blocks (int node, int l, int r, int i) {
    while (block_tree[node].empty() == false && block_tree[node].back().contains(i)) {
        del_block(block_tree[node].back());
        block_tree[node].pop_back();
    }
    if (l != r) {
        int mid = (l + r) / 2;
        int left = node * 2, right = node * 2 + 1;
        if (i <= mid) {
            del_blocks(left, l, mid, i);
        } else {
            del_blocks(right, mid + 1, r, i);
        }
    }
}
void del_blocks (int i) {
    del_blocks(1, 1, N, i);
}

ll Fen[N_MAX + 2];
void update_Fen (int pos, ll val) {
    for (int i = pos; i <= N; i += i & -i) {
        Fen[i] += val;
    }
}
ll query_Fen (int pos) {
    ll sum = 0;
    for (int i = pos; i >= 1; i -= i & -i) {
        sum += Fen[i];
    }
    return sum;
}
ll query_Fen (int l, int r) {
    return (l <= r ? query_Fen(r) - query_Fen(l - 1) : 0);
}

SegInfo max_tree[N_MAX * 4];

vector <Block> find_blocks (int i) {
    vector <Block> blocks;
    vector <int> ls, rs;
    int j; ll sum;
    j = i; sum = 0;
    while (j > 1) {
        sum += A[j];
        j = query_last(max_tree, j - 1, -sum);
        ls.push_back(j + 1);
    }
    j = i; sum = 0;
    while (j < N) {
        sum += A[j];
        j = query_first(max_tree, j + 1, -sum);
        rs.push_back(j - 1);
    }
    for (int l : ls) {
        for (int r : rs) {
            ll sum = query_Fen(l, r);
            if (sum < A[l - 1] && sum < A[r + 1]) {
                blocks.push_back(Block{l, r});
            }
        }
    }
    return blocks;
}

void add_blocks (int i) {
    vector <Block> blocks = find_blocks(i);
    reverse(blocks.begin(), blocks.end());
    add_blocks(i, blocks);
}

SegInfo A_tree[N_MAX * 4 + 2];
SegInfo B_tree[N_MAX * 4 + 2];

void update (int i, ll a) {
    update_Fen(i, a - A[i]);
    update_tree(max_tree, i, -(a - A[i]));
    update_tree(A_tree, i, -a - (-A[i]));
    if (i + 1 <= N) {
        update_tree(A_tree, i + 1, N, a - A[i]);
    }
    update_tree(B_tree, i, -a - (-A[i]));
    if (1 <= i - 1) {
        update_tree(B_tree, 1, i - 1, a - A[i]);
    }
    A[i] = a;
    del_blocks(i);
    add_blocks(i);
    if (i - 1 >= 1) {
        del_blocks(i - 1);
        add_blocks(i - 1);
    }
    if (i + 1 <= N) {
        del_blocks(i + 1);
        add_blocks(i + 1);
    }
}
int query (int l, int r) {
    l = max(l, query_last(A_tree, r, query_Fen(1, l - 1) - 1));
    r = min(r, query_first(B_tree, l, query_Fen(r + 1, N) - 1));
    return query_cnt(min_tree, l, r);
}

int Q;

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin >> N;
    build_tree(min_tree);
    build_tree(max_tree);
    for (int i = 1; i <= N; i++) {
        ll a; cin >> a;
        update(i, a);
    }
    cin >> Q;
    while (Q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int i; ll a; cin >> i >> a;
            update(i, a);
        } else {
            int l, r;
            cin >> l >> r;
            cout << query(l, r) << "\n";
        }
    }

    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 5 ms 14684 KB Output is correct
4 Correct 3 ms 14848 KB Output is correct
5 Correct 21 ms 14828 KB Output is correct
6 Correct 17 ms 14680 KB Output is correct
7 Correct 23 ms 14684 KB Output is correct
8 Correct 19 ms 14684 KB Output is correct
9 Correct 18 ms 14684 KB Output is correct
10 Correct 19 ms 14896 KB Output is correct
11 Correct 18 ms 14684 KB Output is correct
12 Correct 24 ms 14912 KB Output is correct
13 Correct 19 ms 14684 KB Output is correct
14 Correct 26 ms 14684 KB Output is correct
15 Correct 28 ms 14884 KB Output is correct
16 Correct 25 ms 14684 KB Output is correct
17 Correct 21 ms 14872 KB Output is correct
18 Correct 18 ms 14684 KB Output is correct
19 Correct 20 ms 14684 KB Output is correct
20 Correct 19 ms 14912 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Execution timed out 4093 ms 34576 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 5 ms 14684 KB Output is correct
4 Correct 3 ms 14848 KB Output is correct
5 Correct 21 ms 14828 KB Output is correct
6 Correct 17 ms 14680 KB Output is correct
7 Correct 23 ms 14684 KB Output is correct
8 Correct 19 ms 14684 KB Output is correct
9 Correct 18 ms 14684 KB Output is correct
10 Correct 19 ms 14896 KB Output is correct
11 Correct 18 ms 14684 KB Output is correct
12 Correct 24 ms 14912 KB Output is correct
13 Correct 19 ms 14684 KB Output is correct
14 Correct 26 ms 14684 KB Output is correct
15 Correct 28 ms 14884 KB Output is correct
16 Correct 25 ms 14684 KB Output is correct
17 Correct 21 ms 14872 KB Output is correct
18 Correct 18 ms 14684 KB Output is correct
19 Correct 20 ms 14684 KB Output is correct
20 Correct 19 ms 14912 KB Output is correct
21 Correct 3 ms 14680 KB Output is correct
22 Execution timed out 4093 ms 34576 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Execution timed out 4093 ms 34576 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Execution timed out 4093 ms 34576 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14680 KB Output is correct
2 Correct 3 ms 14684 KB Output is correct
3 Correct 5 ms 14684 KB Output is correct
4 Correct 3 ms 14848 KB Output is correct
5 Correct 21 ms 14828 KB Output is correct
6 Correct 17 ms 14680 KB Output is correct
7 Correct 23 ms 14684 KB Output is correct
8 Correct 19 ms 14684 KB Output is correct
9 Correct 18 ms 14684 KB Output is correct
10 Correct 19 ms 14896 KB Output is correct
11 Correct 18 ms 14684 KB Output is correct
12 Correct 24 ms 14912 KB Output is correct
13 Correct 19 ms 14684 KB Output is correct
14 Correct 26 ms 14684 KB Output is correct
15 Correct 28 ms 14884 KB Output is correct
16 Correct 25 ms 14684 KB Output is correct
17 Correct 21 ms 14872 KB Output is correct
18 Correct 18 ms 14684 KB Output is correct
19 Correct 20 ms 14684 KB Output is correct
20 Correct 19 ms 14912 KB Output is correct
21 Correct 3 ms 14680 KB Output is correct
22 Execution timed out 4093 ms 34576 KB Time limit exceeded
23 Halted 0 ms 0 KB -