QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#879072#9986. ShioriNianFengWA 49ms11076kbC++146.8kb2025-02-01 20:43:222025-02-01 20:43:22

Judging History

This is the latest submission verdict.

  • [2025-02-01 20:43:22]
  • Judged
  • Verdict: WA
  • Time: 49ms
  • Memory: 11076kb
Show
  • [2025-02-01 20:43:22]
  • Submitted

answer

/* 年挽红枫，溪傍芦荻。*/

#ifdef DEBUG
#include <iostream>
#include <cmath>
#include <ctime>

bool Mbe;
void _Dihan();
#endif

#include <cstdio>
#include <cctype>
#include <algorithm>

typedef long long i64;
typedef unsigned long long ull;
typedef double f32;
typedef long double ldb;
typedef __int128 i28;
typedef unsigned __int128 u28;

template <typename T> bool chkMx(T &x, T y) { return x < y ? x = y, true : false; }
template <typename T> bool chkMn(T &x, T y) { return x > y ? x = y, true : false; }

namespace IO {

#define file(s) freopen(#s".in", "r", stdin), freopen(#s".out", "w", stdout)

constexpr int SIZE = 1 << 21;
char ibuf[SIZE], *p1 = ibuf, *p2 = ibuf, obuf[SIZE], *p3 = obuf;

#define flush() (fwrite(obuf, 1, p3 - obuf, stdout), p3 = obuf)
#define gc() (p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, SIZE, stdin), p1 == p2) ? EOF : *p1++)
#define pc(ch) (p3 == obuf + SIZE && flush(), *p3++ = ch)
class Flush { public: ~Flush() { flush(); } } _;

auto chkChar = [](const char &c) -> bool { return c >= 'a' && c <= 'z'; };
template <typename T> inline void read(T &x) {
   static char c;
   static bool f;

   x = 0, f = true;
   while (!isdigit(c = gc())) if (c == '-') f = false;

   while (isdigit(c)) x = x * 10 + (c ^ 48), c = gc();
   f || (x = ~(x - 1), 0);
}
inline void read(char &c) {
   while (!chkChar(c = gc())) ;
}
inline void read(char *s) {
   static char c;

   while (!chkChar(c = gc())) ;

   while (chkChar(c)) *s++ = c, c = gc();
   *s = '\0';
}

template <typename T> inline void write(T x) {
   static char stk[50];
   static unsigned top;

   x < 0 && (pc('-'), x = ~(x - 1), 1), top = 0;
   do stk[++top] = x % 10 ^ 48; while (x /= 10);

   while (top) pc(stk[top--]);
}
inline void write(char c) { pc(c); }
inline void write(char *s) { while (*s) pc(*s++); }
inline void write(const char *s) {
   for (int i = 0; *(s + i); ++i) pc(*(s + i));
}

template <typename T, typename ...Args>
 inline void read(T &first, Args &...args) { read(first), read(args...); }
template <typename T, typename ...Args>
 inline void write(T first, Args ...args) { write(first), write(args...); }

}
using namespace IO;

constexpr int N = 5e5 + 5;

int n, q, a[N];

class SegmentTree {
 private:
   struct Data {
      i64 v;
      int l, r;

      bool operator <(const Data &x) const {
         return v < x.v;
      }
   };
   struct Node {
      i64 sum;
      Data mn;

      i64 add;
      int cov;
   } _tr[N << 2];

   void _pushUp(const int &rt) {
      _tr[rt].sum = _tr[rt << 1].sum + _tr[rt << 1 | 1].sum;
      _tr[rt].mn = std::min(_tr[rt << 1].mn, _tr[rt << 1 | 1].mn);
   }

   void _add(const int &rt, const i64 &k, const int &l, const int &r) {
      _tr[rt].sum += k * (r - l + 1), _tr[rt].mn.v += k;
      _tr[rt].add += k;
   }
   void _cov(const int &rt, const int &k, const int &l, const int &r) {
      _tr[rt] = {1ll * k * (r - l + 1), {k, l, r}, 0, k};
   }
   void _pushDown(const int &rt, const int &l, const int &r) {
      int mid = l + r >> 1;

      if (~_tr[rt].cov) {
         _cov(rt << 1, _tr[rt].cov, l, mid);
         _cov(rt << 1 | 1, _tr[rt].cov, mid + 1, r);

         _tr[rt].cov = -1;
      }

      if (_tr[rt].add) {
         _add(rt << 1, _tr[rt].add, l, mid);
         _add(rt << 1 | 1, _tr[rt].add, mid + 1, r);

         _tr[rt].add = 0;
      }
   }

   void _build(const int &rt, const int &l, const int &r) {
      _tr[rt].cov = -1;
      if (l == r)
         return _tr[rt].sum = a[l], _tr[rt].mn = {a[l], l, l}, void();

      int mid = l + r >> 1;

      _build(rt << 1, l, mid);
      _build(rt << 1 | 1, mid + 1, r);

      _pushUp(rt);
   }

   void _update(
    const int &rt, const int &l, const int &r,
    const int &L, const int &R, const int &k
   ) {
      if (L <= l && r <= R)
         return _add(rt, k, l, r);
      _pushDown(rt, l, r);

      int mid = l + r >> 1;

      if (L <= mid)
         _update(rt << 1, l, mid, L, R, k);
      if (mid < R)
         _update(rt << 1 | 1, mid + 1, r, L, R, k);

      _pushUp(rt);
   }
   void _change(
    const int &rt, const int &l, const int &r,
    const int &L, const int &R, const int &k
   ) {
      if (L <= l && r <= R)
         return _cov(rt, k, l, r);
      _pushDown(rt, l, r);

      int mid = l + r >> 1;

      if (L <= mid)
         _change(rt << 1, l, mid, L, R, k);
      if (mid < R)
         _change(rt << 1 | 1, mid + 1, r, L, R, k);

      _pushUp(rt);
   }

   i64 _querySum(
    const int &rt, const int &l, const int &r,
    const int &L, const int &R
   ) {
      if (L <= l && r <= R)
         return _tr[rt].sum;
      _pushDown(rt, l, r);

      int mid = l + r >> 1;

      if (R <= mid)
         return _querySum(rt << 1, l, mid, L, R);
      if (mid < L)
         return _querySum(rt << 1 | 1, mid + 1, r, L, R);
      return _querySum(rt << 1, l, mid, L, R)
           + _querySum(rt << 1 | 1, mid + 1, r, L, R);
   }
   Data _queryMin(
    const int &rt, const int &l, const int &r,
    const int &L, const int &R
   ) {
      if (L <= l && r <= R)
         return _tr[rt].mn;
      _pushDown(rt, l, r);

      int mid = l + r >> 1;

      if (R <= mid)
         return _queryMin(rt << 1, l, mid, L, R);
      if (mid < L)
         return _queryMin(rt << 1 | 1, mid + 1, r, L, R);
      return std::min(
         _queryMin(rt << 1, l, mid, L, R),
         _queryMin(rt << 1 | 1, mid + 1, r, L, R)
      );
   }

   int _queryMex(const int &l, const int &r, const int &k) {
      if (l > r) return k;

      Data cur = _queryMin(1, 1, n, l, r);

      if (cur.v > k) return k;
      return std::max(_queryMex(l, cur.l - 1, cur.v + 1),
                      _queryMex(cur.r + 1, r, cur.v + 1));
   }

 public:
   void build() {
      _build(1, 1, n);
   }

   i64 querySum(int l, int r) {
      return _querySum(1, 1, n, l, r);
   }

   void update(int l, int r) {
      _update(1, 1, n, l, r, _queryMex(l, r, 0));
   }
   void change(int l, int r, int k) {
      _change(1, 1, n, l, r, k);
   }
} tr;

int main() {
#ifdef DEBUG
   file(cur);
#endif

   read(n, q);
   for (int i = 1; i <= n; ++i)
      read(a[i]);

   tr.build();

   while (q--) {
      static int opt, l, r, k;
      read(opt, l, r);

      switch (opt) {
       case 1:
         read(k), tr.change(l, r, k);

         break;
       case 2:
         tr.update(l, r);

         break;
       case 3:
         write(tr.querySum(l, r), '\n');

         break;
      }
   }

#ifdef DEBUG
   _Dihan();
#endif
   return 0;
}

#ifdef DEBUG
bool Med;
void _Dihan() {
   std::cerr << "Memory: " << abs(&Med - &Mbe) / 1048576.0 << " MB\n";
   std::cerr << "Time: " << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
}
#endif
源文件, 语言: C++14

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 9800kb

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: 0ms
memory: 9808kb

input:

1 1
0
1 1 1 0

output:

result:

ok 0 number(s): ""

Test #3:

score: -100
Wrong Answer
time: 49ms
memory: 11076kb

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...

output:

0
0
10
7
0
0
6
3
0
0
0
1
25
12
10
0
0
0
0
17
23
1
20
2
11
27
26
2
14
2
2
0
0
0
2
4
1
0
0
0
7
2
0
4
32
15
7
11
0
4
5
2
8
5
1
6
0
7
0
7
6
3
2
5
0
0
0
7
14
2
5
0
2
0
0
6
12
6
0
2
3
0
0
1
16
12
1
1
12
0
3
4
4
10
3
16
0
17
2
4
0
0
16
8
2
8
18
23
2
24
4
12
7
4
14
5
0
2
8
4
16
10
6
4
21
15
1
3
3
0
2
5
0
2
...

result:

wrong answer 29th numbers differ - expected: '18', found: '14'
English 繁體中文 简体中文

服务器时间: 2025-02-08 21:04:31 | 开源项目