QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#708525 | #3850. DJ Darko | ahsoltan# | RE | 0ms | 0kb | C++20 | 3.9kb | 2024-11-03 23:10:48 | 2024-11-03 23:11:00 |
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) int((x).size())
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
#ifdef LOCAL
auto operator<<(auto& o, auto x) -> decltype(x.first, o);
auto operator<<(auto& o, auto x) -> decltype(x.end(), o) {
o << "{";
for (int i = 0; auto y : x) o << ", " + !i++ * 2 << y;
return o << "}";
}
auto operator<<(auto& o, auto x) -> decltype(x.first, o) {
return o << "(" << x.first << ", " << x.second << ")";
}
void __print(auto... x) { ((cerr << x << " "), ...) << endl; }
#define debug(x...) __print("[" #x "]:", x)
#else
#define debug(...) 2137
#endif
struct se {
struct node{
ll mn, mx;
ll push_set, push_add;
ll su;
};
vector<node> st;
int si;
void tag_set(int p, ll v) {
st[p].mn = st[p].mx = st[p].push_set = v;
st[p].push_add = 0;
}
void tag_add(int p, ll v) {
st[p].mn += v;
st[p].mx += v;
if(st[p].push_set != -1)
st[p].push_set += v;
else
st[p].push_add += v;
}
void push(int p) {
assert(st[p].push_set == -1 || st[p].push_add == 0);
if(st[p].push_set != -1) {
tag_set(2 * p, st[p].push_set);
tag_set(2 * p + 1, st[p].push_set);
st[p].push_set = -1;
}
if(st[p].push_add) {
tag_add(2 * p, st[p].push_add);
tag_add(2 * p + 1, st[p].push_add);
st[p].push_add = 0;
}
}
void upd(int p) {
st[p].mn = min(st[2 * p].mn, st[2 * p + 1].mn);
st[p].mx = max(st[2 * p].mx, st[2 * p + 1].mx);
}
void build(vector<ll> co) {
si = 1;
while(si <= 2 * sz(co) + 2)
si *= 2;
st.assign(si, node{-1, -1, -1, 0LL, 0LL});
rep(i, 0, sz(co))
st[i + si / 2].su = co[i];
for(int i = si / 2 - 1; i >= 1; --i) {
st[i].su = st[2 *i].su + st[2 * i + 1].su;
}
}
void add(int b, int e, int x, int y, int p, ll v) {
if(e < x || b > y)
return;
if(x <= b && e <= y) {
tag_add(p, v);
return;
}
push(p);
int mid = (b + e) / 2;
add(b, mid, x, y, 2 * p, v);
add(mid + 1, e, x, y, 2 * p + 1, v);
upd(p);
}
void set(int b, int e, int x, int y, int p, ll v) {
if(e < x || b > y)
return;
if(x <= b && e <= y) {
tag_set(p, v);
return;
}
push(p);
int mid = (b + e) / 2;
set(b, mid, x, y, 2 * p, v);
set(mid + 1, e, x, y, 2 * p + 1, v);
upd(p);
}
vector<pair<ll, ll>> vr;
void ge(int b, int e, int x, int y, int p) {
if(e < x || b > y)
return;
if(x <= b && e <= y && st[p].mx == st[p].mn) {
vr.emplace_back(st[p].mx, st[p].su);
return;
}
push(p);
int mid = (b + e) / 2;
ge(b, mid, x, y, 2 * p);
ge(mid + 1, e, x, y, 2 * p + 1);
upd(p);
}
void ose(int b, int e, ll v) {
set(1, si / 2, b, e, 1, v);
}
void oadd(int b, int e, ll v) {
add(1, si / 2, b, e, 1, v);
}
vector<pair<ll, ll>> oge(int b, int e) {
vr.clear();
ge(1, si / 2, b, e, 1);
return vr;
}
};
ll daj(vector<pair<ll, ll>> ve) {
sort(all(ve));
ll left = 0;
ll right = 0;
for(auto [itr, co] : ve) {
right -= co;
}
for(auto [itr, co] : ve) {
right += co;
if(right + co >= 0 && left + co >= 0)
return itr;
left -= co;
}
assert(false);
}
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, q;
cin >> n >> q;
vector<ll> cur(n);
vector<ll> cost(n);
for(auto &i : cur)
cin >> i;
for(auto &i : cost)
cin >> i;
se st;
st.build(cost);
for(int i = 0; i < n; i++)
st.ose(i + 1, i + 1, cur[i]);
rep(_, 0, q) {
int tp;
cin >> tp;
if(tp == 1) {
int l, r, x;
cin >> l >> r >> x;
st.oadd(l, r, x);
}
else {
int l, r;
cin >> l >> r;
auto tmp = st.oge(l, r);
int nowy = daj(tmp);
cout << nowy << endl;
st.ose(l, r, nowy);
}
}
}
详细
Test #1:
score: 0
Runtime Error
input:
200000 200000 185413631 745038744 881479208 394948467 101727403 796960399 284541402 80768155 286582974 546327406 197495962 552359542 727479505 437895671 143092948 7626834 741609268 540494577 298656274 548860413 41137417 210529949 658779847 161355446 486548926 602900245 119414972 310187428 238177860 ...