QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #861640 | #9986. Shiori | ucup-team6275# | TL | 1ms | 3584kb | C++20 | 6.3kb | 2025-01-18 18:56:10 | 2025-01-18 18:56:16 |
Judging History
answer
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <string>
#include <vector>
using namespace std;
#define ll long long
const int INF = 1e9;
struct Node {
ll sum;
int mx, mn;
int push_set, push_plus;
};
Node get_empty() {
return {0, -INF, INF, -1, -1};
}
Node merge(const Node& a, const Node& b) {
Node ans;
ans.sum = a.sum + b.sum;
ans.mx = max(a.mx, b.mx);
ans.mn = min(a.mn, b.mn);
ans.push_plus = 0;
ans.push_set = -1;
return ans;
}
struct SegTree {
int n;
vector <Node> t;
SegTree(int n, const vector <int>& a) : n(n) {
t.resize(4 * n);
build(1, 0, n - 1, a);
}
void build(int v, int l, int r, const vector <int>& a) {
if (l == r) {
t[v].sum = t[v].mx = t[v].mn = a[l];
t[v].push_set = -1;
t[v].push_plus = 0;
return;
}
int m = (l + r) / 2;
build(2 * v, l, m, a);
build(2 * v + 1, m + 1, r, a);
t[v] = merge(t[2 * v], t[2 * v + 1]);
}
void make_plus(int v, int l, int r, int x) {
t[v].mn += x;
t[v].mx += x;
t[v].sum += 1ll * (r - l + 1) * x;
if (t[v].push_set != -1) t[v].push_set += x;
else t[v].push_plus += x;
}
void make_set(int v, int l, int r, int x) {
t[v].mn = t[v].mx = x;
t[v].sum = 1ll * (r - l + 1) * x;
t[v].push_set = x;
t[v].push_plus = 0;
}
inline void push(int v, int l, int r) {
int m = (l + r) / 2;
if (t[v].push_set != -1) {
make_set(2 * v, l, m, t[v].push_set);
make_set(2 * v + 1, m + 1, r, t[v].push_set);
t[v].push_set = -1;
} else if (t[v].push_plus != 0) {
make_plus(2 * v, l, m, t[v].push_plus);
make_plus(2 * v + 1, m + 1, r, t[v].push_plus);
t[v].push_plus = 0;
}
}
void set_seg(int v, int l, int r, int A, int B, int x) {
if (l > B || A > r) return;
if (A <= l && r <= B) {
make_set(v, l, r, x);
return;
}
push(v, l, r);
int m = (l + r) / 2;
set_seg(2 * v, l, m, A, B, x);
set_seg(2 * v + 1, m + 1, r, A, B, x);
t[v] = merge(t[2 * v], t[2 * v + 1]);
}
void add_seg(int v, int l, int r, int A, int B, int x) {
if (l > B || A > r) return;
if (A <= l && r <= B) {
make_plus(v, l, r, x);
return;
}
push(v, l, r);
int m = (l + r) / 2;
add_seg(2 * v, l, m, A, B, x);
add_seg(2 * v + 1, m + 1, r, A, B, x);
t[v] = merge(t[2 * v], t[2 * v + 1]);
}
int get_min(int v, int l, int r, int A, int B) {
if (l > B || A > r) return INF;
if (A <= l && r <= B) return t[v].mn;
push(v, l, r);
int m = (l + r) / 2;
return min(get_min(2 * v, l, m, A, B), get_min(2 * v + 1, m + 1, r, A, B));
}
ll get_sum(int v, int l, int r, int A, int B) {
if (l > B || A > r) return 0;
if (A <= l && r <= B) return t[v].sum;
int m = (l + r) / 2;
push(v, l, r);
return get_sum(2 * v, l, m, A, B) + get_sum(2 * v + 1, m + 1, r, A, B);
}
int find_pos_min(int v, int l, int r, int A, int B, int x) {
if (l > B || A > r || t[v].mn != x) return -1;
if (l == r) return l;
push(v, l, r);
int m = (l + r) / 2;
int lft = find_pos_min(2 * v, l, m, A, B, x);
if (lft != -1) return lft;
return find_pos_min(2 * v + 1, m + 1, r, A, B, x);
}
int first_more(int v, int l, int r, int A, int B, int x) {
if (l > B || A > r || t[v].mx <= x) return -1;
if (l == r) return l;
int m = (l + r) / 2;
push(v, l, r);
int lft = first_more(2 * v, l, m, A, B, x);
if (lft != -1) return lft;
return first_more(2 * v + 1, m + 1, r, A, B, x);
}
int last_more(int v, int l, int r, int A, int B, int x) {
if (l > B || A > r || t[v].mx <= x) return -1;
if (l == r) return l;
int m = (l + r) / 2;
push(v, l, r);
int rgt = last_more(2 * v + 1, m + 1, r, A, B, x);
if (rgt != -1) return rgt;
return last_more(2 * v, l, m, A, B, x);
}
};
void solve() {
int n, m;
cin >> n >> m;
vector <int> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
SegTree t(n, a);
vector <array <int, 3>> st;
while (m--) {
int op;
cin >> op;
if (op == 1) {
int l, r, v;
cin >> l >> r >> v; --l; --r;
t.set_seg(1, 0, n - 1, l, r, v);
} else if (op == 2) {
int l, r;
cin >> l >> r; --l; --r;
int mex = 0;
for (int val = 0;; ++val) {
int my_min = t.get_min(1, 0, n - 1, l, r);
if (my_min != val) {
mex = val;
break;
}
while (my_min == val) {
int l_pos = t.find_pos_min(1, 0, n - 1, l, r, val);
int r_bad = t.first_more(1, 0, n - 1, l_pos, r, val);
if (r_bad == -1) r_bad = r + 1;
r_bad--;
st.push_back({l_pos, r_bad, val});
t.set_seg(1, 0, n - 1, l_pos, r_bad, INF);
my_min = t.get_min(1, 0, n - 1, l, r);
}
}
for (auto i : st) {
t.set_seg(1, 0, n - 1, i[0], i[1], i[2]);
}
st.clear();
t.add_seg(1, 0, n - 1, l, r, mex);
} else {
int l, r;
cin >> l >> r; --l; --r;
cout << t.get_sum(1, 0, n - 1, l, r) << "\n";
}
}
}
signed main() {
if (1) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
}
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
/*
5 8
0 7 2 1 0
1 2 4 0
2 1 3
2 3 4
3 1 3
1 2 3 4
3 1 4
2 1 5
3 2 5
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3584kb
input:
5 8 0 7 2 1 0 1 2 4 0 2 1 3 2 3 4 3 1 3 1 2 3 4 3 1 4 2 1 5 3 2 5
output:
5 11 22
result:
ok 3 number(s): "5 11 22"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3584kb
input:
1 1 0 1 1 1 0
output:
result:
ok 0 number(s): ""
Test #3:
score: -100
Time Limit Exceeded
input:
10 500000 0 0 0 0 0 0 0 0 0 0 3 2 9 2 4 10 2 2 7 2 7 9 3 1 1 3 5 8 1 5 10 0 3 1 9 3 5 9 2 2 4 1 2 4 0 2 5 6 3 8 8 1 4 6 0 1 6 6 0 2 4 10 3 1 9 3 5 7 1 4 10 0 3 6 9 3 2 6 2 1 8 1 5 9 0 3 7 8 3 4 8 2 4 8 2 5 8 2 1 9 2 3 8 1 5 10 0 2 4 8 3 1 6 2 1 4 2 3 7 3 4 10 1 4 6 0 1 1 6 0 2 3 7 1 1 1 0 2 1 10 1 5...