QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#326552 | #8229. 栈 | Xiaohuba | 0 | 126ms | 107776kb | C++23 | 9.4kb | 2024-02-13 13:47:06 | 2024-02-13 13:47:06 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
// #define LOCK_GETCHAR
// #define USE_INT_128
#if __cplusplus < 201400
#warning "Please use c++14 or higher."
#define CONSTEXPR_FUNC
#define ENABLE_IF_INT
#else
#define CONSTEXPR_FUNC constexpr
#define ENABLE_IF_INT , enable_if_t<_is_integer<T>, int> = 0
template <class T> constexpr bool _is_integer = numeric_limits<T>::is_integer;
template <> constexpr bool _is_integer<bool> = false;
template <> constexpr bool _is_integer<char> = false;
#ifdef USE_INT_128
template <> constexpr bool _is_integer<__int128> = true;
template <> constexpr bool _is_integer<__uint128_t> = true;
#endif
template <class T ENABLE_IF_INT>
constexpr T INF = numeric_limits<T>::max() >> 1;
#endif
#if !defined(_WIN32) && !defined(LOCK_GETCHAR)
#define getchar getchar_unlocked
#endif
#define il inline
#define mkp make_pair
#define fi first
#define se second
#define For(i, j, k) for (decltype(j - k) i = (j); i <= (k); ++i) // NOLINT
#define ForDown(i, j, k) for (decltype(j - k) i = (j); i >= (k); --i) // NOLINT
#define pb push_back
#define eb emplace_back
#ifndef ONLINE_JUDGE
#define FileIO(filename) \
freopen(filename ".in", "r", stdin); \
freopen(filename ".out", "w", stdout)
#else
#define FileIO(filename) void(0)
#endif
using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using db = double;
using ldb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#ifdef USE_INT_128
using lll = __int128_t;
using ulll = __uint128_t;
#endif
// clang-format off
template<typename T> constexpr il T sq(const T & x){ return x * x; }
template<typename T> CONSTEXPR_FUNC il void cmin(T & x, const T &y){ x = min(x, y); }
template<typename T> CONSTEXPR_FUNC il void cmax(T & x, const T &y){ x = max(x, y);}
template<typename T> CONSTEXPR_FUNC il T qpow(T x, ull y, T mod){T ans = 1; x %= mod; while (y) { if(y & 1)(ans *= x) %= mod;(x *= x) %= mod; y >>= 1;} return ans;}
template<typename T> CONSTEXPR_FUNC il T qpow(T x, ull y){T ans = 1; while (y) {if(y & 1) ans *= x;x *= x;y >>= 1;} return ans;}
template<typename T ENABLE_IF_INT> il void read(T &x){ x = 0; int f = 1; int c = getchar(); while(!isdigit(c)) {if (c == '-') f = -1;c = getchar();} while(isdigit(c)) {x = x * 10 + c - '0';c = getchar();} x *= f;}
template<typename T, typename ... Args> il void read(T &x, Args &... y){ read(x); read(y...); }
// clang-format on
// File head end
namespace {
// constexpr ll MAXN = ...;
class WBLT {
static il constexpr db alpha = 1.0 - 1.4142136 / 2;
static il constexpr ll INITIAL_SIZE = 3e6;
struct Node {
int lc, rc, sz;
ll sum, weight;
Node() : lc(0), rc(0), sz(0), sum(0), weight(0) {}
};
static il vector<Node> T{INITIAL_SIZE};
static il int cnt = 0;
static il int new_nd() {
if (cnt + 1 == T.size())
T.resize(T.size() * 1.5);
return ++cnt;
}
#define lc(p) (T[p].lc)
#define rc(p) (T[p].rc)
#define sz(p) (T[p].sz)
#define weight(p) (T[p].weight)
static il void pu(int p) {
assert(lc(p) && rc(p));
sz(p) = sz(lc(p)) + sz(rc(p));
T[p].sum = T[lc(p)].sum + T[rc(p)].sum;
T[p].weight = T[lc(p)].weight + T[rc(p)].weight;
}
static il int __merge(int lc, int rc) {
int p = new_nd();
return lc(p) = lc, rc(p) = rc, pu(p), p;
}
static int merge(int p, int q) {
if (!p || !q)
return p | q;
auto val = alpha * (sz(p) + sz(q));
if (min(sz(p), sz(q)) >= val)
return __merge(p, q);
else if (sz(p) >= sz(q)) {
if (sz(lc(p)) >= val) {
int pre = p;
p = new_nd(), T[p] = T[pre];
return rc(p) = merge(rc(p), q), pu(p), p;
} else {
int u = merge(lc(p), lc(rc(p))), v = merge(rc(rc(p)), q);
return merge(u, v);
}
} else {
if (sz(rc(q)) >= val) {
int pre = q;
q = new_nd(), T[q] = T[pre];
return lc(q) = merge(p, lc(q)), pu(q), q;
} else {
int u = merge(p, lc(lc(q))), v = merge(rc(lc(q)), rc(q));
return merge(u, v);
}
}
}
static pii split(int p, ll rk) {
assert(p);
if (!rk)
return {0, p};
else if (sz(p) == 1) {
if (rk == weight(p))
return {p, 0};
else {
assert(rk < weight(p));
int u = new_nd(), v = new_nd();
ll val = T[p].sum / weight(p);
sz(u) = sz(v) = 1;
weight(u) = rk, T[u].sum = val * weight(u);
weight(v) = weight(p) - rk, T[v].sum = val * weight(v);
return {u, v};
}
}
if (rk <= weight(lc(p))) {
auto [u, v] = split(lc(p), rk);
return {u, merge(v, rc(p))};
} else {
auto [u, v] = split(rc(p), rk - weight(lc(p)));
return {merge(lc(p), u), v};
}
}
static ll query(int p, ll ql, ll qr) {
// if (!(ql >= 1 && ql <= qr))
// cerr << ql << ' ' << qr << '\n';
assert(ql >= 1 && ql <= qr);
if (!p)
return 0;
else if (sz(p) == 1) {
ll cnt = min(qr, weight(p)) - ql + 1, val = T[p].sum / T[p].weight;
return cnt * val;
} else if (ql == 1 && qr >= weight(p))
return T[p].sum;
ll ans = 0, mid = weight(lc(p));
if (ql <= mid)
ans += query(lc(p), ql, qr);
if (qr > mid)
ans += query(rc(p), max(1ll, ql - mid), qr - mid);
return ans;
}
int rt = 0;
WBLT(int _rt) : rt(_rt) {}
public:
WBLT() : rt(0) {}
il void join(WBLT rhs) { rt = merge(rt, rhs.rt); }
static il WBLT join2(WBLT x, WBLT y) { return {merge(x.rt, y.rt)}; }
il void push(ll val, ll cnt) {
int p = new_nd();
sz(p) = 1, weight(p) = cnt, T[p].sum = val * weight(p);
rt = merge(rt, p);
}
il void pop_back(ll cnt) {
if (weight(rt) <= cnt)
return rt = 0, void();
auto [u, v] = split(rt, weight(rt) - cnt);
assert(weight(u) == weight(rt) - cnt);
rt = u;
}
il void pop_front(ll cnt) {
if (weight(rt) <= cnt)
return rt = 0, void();
auto [u, v] = split(rt, cnt);
rt = v;
}
il ll qry_sum(ll st, ll ed) const {
if (st > this->size())
return 0;
else {
// cerr << st << ' ' << min(ed, weight(rt)) << '\n';
return query(rt, st, min(ed, weight(rt)));
}
}
il ll size() const { return weight(rt); }
il void clear() { rt = 0; }
#undef lc
#undef rc
#undef sz
#undef weight
};
namespace SGT {
constexpr ll MAXN = 1e5 + 5;
using tag_t = tuple<short, ll, WBLT>;
il short &_type(tag_t &x) { return get<0>(x); }
struct Node {
int l, r;
array<tag_t, 2> tags;
Node() : l(0), r(0), tags() {}
} static T[MAXN << 1];
#define mid(p) ((T[p].l + T[p].r) >> 1)
#define lc(p) (mid(p) << 1)
#define rc(p) (mid(p) << 1 | 1)
il void f(int p, tag_t tg) {
int id = !!get<1>(T[p].tags[1]), tp1 = _type(T[p].tags[id]), tp2 = _type(tg);
tag_t &cur = T[p].tags[id];
assert(!id || tp1 == 2);
if (tp2 == 1) { // pop
ll cnt = get<1>(tg), val = get<2>(cur).size();
if (tp1 == 1)
get<1>(cur) += cnt;
else if (val >= cnt)
get<2>(cur).pop_back(cnt);
else {
get<2>(cur).clear();
if (id) {
assert(get<0>(T[p].tags[0]) == 1);
cur = {};
}
_type(T[p].tags[0]) = 1;
get<1>(T[p].tags[0]) += cnt - val;
}
} else if (tp2 == 2) { // push
if (tp1 != 1)
_type(cur) = 2, get<2>(cur).join(get<2>(tg));
else {
assert(id == 0);
T[p].tags[1] = tg;
}
}
}
il void pd(int p) {
f(lc(p), T[p].tags[0]), f(rc(p), T[p].tags[0]);
f(lc(p), T[p].tags[1]), f(rc(p), T[p].tags[1]);
T[p].tags[0] = T[p].tags[1] = {};
}
void build(int p, int l, int r) {
T[p].l = l, T[p].r = r;
if (l == r)
return;
int mid = (l + r) >> 1;
build(lc(p), l, mid), build(rc(p), mid + 1, r);
}
void push(int p, int ql, int qr, int val, int cnt) {
int l = T[p].l, r = T[p].r;
if (ql <= l && qr >= r) {
WBLT tag;
tag.push(val, cnt);
f(p, make_tuple(2, 0, tag));
return;
}
pd(p);
if (ql <= mid(p))
push(lc(p), ql, qr, val, cnt);
if (qr > mid(p))
push(rc(p), ql, qr, val, cnt);
}
void pop(int p, int ql, int qr, ll cnt) {
int l = T[p].l, r = T[p].r;
if (ql <= l && qr >= r)
return f(p, make_tuple(1, cnt, WBLT{}));
pd(p);
if (ql <= mid(p))
pop(lc(p), ql, qr, cnt);
if (qr > mid(p))
pop(rc(p), ql, qr, cnt);
}
ll qry(int p, int pos, ll L, ll R) {
if (T[p].l == T[p].r) {
int id = (get<0>(T[p].tags[0]) == 1);
// cerr << "> " << get<2>(T[p].tags[id]).size() << '\n';
return get<2>(T[p].tags[id]).qry_sum(L, R);
}
pd(p);
if (pos <= mid(p))
return qry(lc(p), pos, L, R);
else
return qry(rc(p), pos, L, R);
}
#undef mid
#undef lc
#undef rc
}; // namespace SGT
int n, m;
il void Main() {
read(n, m);
SGT::build(1, 1, n);
For(i, 1, m) {
int op, x = 0;
ll y = 0, z = 0, w = 0;
read(op, x, y, z);
if (op == 1) {
read(w);
SGT::push(1, x, y, w, z);
} else if (op == 2)
SGT::pop(1, x, y, z);
else if (op == 3) {
}
// printf("%lld\n", SGT::qry(1, x, y, z));
if (i > 16)
cout << op << ' ' << x << ' ' << y << ' ' << z << '\n';
}
// WBLT tr;
// tr.push(2, 3);
// cout << tr.size() << ' ' << tr.qry_sum(2, 4) << '\n';
}
} // namespace
signed main() { return Main(), 0; }
/*
[1 , 4]
[1, 2][3, 4]
[1][2][3][4]
*/
详细
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 4ms
memory: 107720kb
input:
4907 4910 2 763 3330 1 3 307 1 1 1 2262 3430 22699 89397 1 1915 4000 51541 67587 2 212 2990 9763 2 1086 2162 1 2 1813 4496 16760 1 51 2796 68005 99390 1 1267 1519 74236 66178 3 1768 23808 54314 2 900 4122 27758 3 3287 17350 28989 2 3277 4024 3633 2 444 4866 1 2 353 4219 1061 1 987 3141 99906 17320 2...
output:
2 3504 3847 1542 1 3524 4874 66273 1 2254 3348 8462 3 3153 3232 8506 2 3856 4375 24551 1 414 2978 77950 2 9 811 76118 2 1944 2353 52505 3 4457 53340 56776 1 3726 4051 8704 2 875 4538 267717 1 921 3284 42924 3 3163 7871 19789 3 2596 167 26077 3 2967 24 38 1 3978 4252 44094 3 823 82495 83640 2 483 163...
result:
wrong answer 1st numbers differ - expected: '0', found: '2'
Subtask #2:
score: 0
Memory Limit Exceeded
Test #6:
score: 0
Memory Limit Exceeded
input:
99999 99998 1 5026 18575 27178 90423 3 30623 1 1 3 76936 1 1 1 77021 95683 84664 24734 1 46085 74886 40512 11266 3 5048 8594 22468 1 53318 77721 97151 70784 1 70645 91192 37556 13013 1 56752 56940 91812 62887 1 7928 34576 87339 69404 3 74875 32807 100970 3 22338 17221 25771 3 21421 20602 57957 3 717...
output:
3 12902 18080 96767 3 52038 5775 15546 1 48465 57382 11270 1 35164 79557 7121 3 29308 4383 22056 1 619 27028 82974 3 30409 53182 81844 3 12668 60080 71081 1 80111 98319 96523 1 31101 50417 7107 1 56654 62593 25083 1 27455 43622 62176 1 14150 69591 93351 1 52895 85484 91165 3 66455 119029 221378 1 42...
result:
Subtask #3:
score: 0
Wrong Answer
Test #12:
score: 0
Wrong Answer
time: 126ms
memory: 107724kb
input:
100000 99993 1 47773 70467 16065 1 2 52349 78446 2304 3 40821 1 1 1 40216 93069 78144 1 1 41089 43671 76025 1 2 35263 68629 31066 3 79881 13534 57327 3 5556 1 1 2 21962 38192 1 1 664 58116 9417 1 3 28089 6039 7989 2 88500 90302 9946 3 63215 49410 60770 2 11069 89527 57581 2 70303 97603 12363 1 3420 ...
output:
3 60894 491 619 3 60760 407 1304 3 26531 6255 35499 2 15449 59440 60281 2 73501 98412 2036 2 41604 62285 2463 2 42396 57007 1 1 10918 27801 95645 2 36769 73870 21055 1 41755 80459 33030 2 11478 91848 38025 1 38309 76238 30786 1 73946 97353 84295 1 12987 85182 91472 2 14016 63139 109183 2 48781 57982...
result:
wrong answer 1st numbers differ - expected: '0', found: '3'
Subtask #4:
score: 0
Wrong Answer
Test #17:
score: 0
Wrong Answer
time: 105ms
memory: 107776kb
input:
99999 99996 3 77889 1 10000000000 1 6316 86327 89644 386 3 9260 1 10000000000 2 2603 47234 69717 2 20260 73011 19290 2 62477 81233 26127 1 50140 68508 37004 98794 2 14449 22788 16063 1 43860 84932 50375 21777 1 67345 94584 28202 66610 2 661 68654 1 1 14411 94422 82738 61196 1 16563 94416 4920 38408 ...
output:
2 87428 95951 69758 2 42898 57892 317995 3 8892 1 10000000000 1 80773 94146 69680 2 17931 52215 9660 1 619 15972 99789 2 67063 88496 136110 1 21401 76249 96102 1 8799 69886 83665 1 52053 77591 14348 1 25565 47568 44538 1 24878 89682 45388 2 1588 57442 319558 3 17768 1 10000000000 1 499 98330 17892 3...
result:
wrong answer 1st numbers differ - expected: '0', found: '2'
Subtask #5:
score: 0
Skipped
Dependency #1:
0%