QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#326552#8229. 栈Xiaohuba0 126ms107776kbC++239.4kb2024-02-13 13:47:062024-02-13 13:47:06

Judging History

你现在查看的是最新测评结果

  • [2024-02-13 13:47:06]
  • 评测
  • 测评结果:0
  • 用时:126ms
  • 内存:107776kb
  • [2024-02-13 13:47:06]
  • 提交

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%