QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#769781#9774. Same SumPlentyOfPenalty#WA 373ms44300kbC++204.3kb2024-11-21 19:22:442024-11-21 19:22:45

Judging History

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

  • [2025-01-11 11:59:18]
  • hack成功,自动添加数据
  • (/hack/1443)
  • [2024-12-23 17:02:06]
  • hack成功,自动添加数据
  • (/hack/1310)
  • [2024-12-23 16:48:26]
  • hack成功,自动添加数据
  • (/hack/1309)
  • [2024-12-23 16:33:45]
  • hack成功,自动添加数据
  • (/hack/1308)
  • [2024-12-23 16:23:53]
  • hack成功,自动添加数据
  • (/hack/1307)
  • [2024-12-23 16:13:08]
  • hack成功,自动添加数据
  • (/hack/1306)
  • [2024-12-23 15:54:42]
  • hack成功,自动添加数据
  • (/hack/1305)
  • [2024-12-23 14:58:39]
  • hack成功,自动添加数据
  • (/hack/1304)
  • [2024-12-23 09:58:11]
  • hack成功,自动添加数据
  • (/hack/1302)
  • [2024-12-23 09:47:22]
  • hack成功,自动添加数据
  • (/hack/1301)
  • [2024-12-23 09:41:23]
  • hack成功,自动添加数据
  • (/hack/1300)
  • [2024-12-23 09:26:32]
  • hack成功,自动添加数据
  • (/hack/1299)
  • [2024-12-23 09:19:58]
  • hack成功,自动添加数据
  • (/hack/1298)
  • [2024-12-23 09:13:29]
  • hack成功,自动添加数据
  • (/hack/1297)
  • [2024-12-22 18:52:18]
  • hack成功,自动添加数据
  • (/hack/1296)
  • [2024-12-22 18:13:14]
  • hack成功,自动添加数据
  • (/hack/1294)
  • [2024-11-21 19:22:45]
  • 评测
  • 测评结果:WA
  • 用时:373ms
  • 内存:44300kb
  • [2024-11-21 19:22:44]
  • 提交

answer

#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
#define all(x) begin(x), end(x)
#ifdef memset0
#define log(...) fprintf(stderr, __VA_ARGS__)
#else
#define endl '\n'
#define log(...) (void(0))
#endif
using namespace std;
using ll = long long;
using lf = long double;
using ull = unsigned long long;
using lll = __int128;

const int N = 2e5 + 9;
const int b1 = 131, b2 = 131131;
const int p1 = 998244353, p2 = 1e9 + 7;
int n, m, a[N];

template <const int mod> int power(int a, int b) {
  int s = 1;
  for (; b; b >>= 1, a = (ll)a * a % mod)
    if (b & 1) s = (ll)s * a % mod;
  return s;
}

struct atom {
  int x, y;

  static atom get_base(ll k) {
    int k1 = k % (p1 - 1);
    if (k1 < 0) k1 += p1 - 1;
    int k2 = k % (p2 - 1);
    if (k2 < 0) k2 += p2 - 1;
    return {power<p1>(b1, k1), power<p2>(b2, k2)};
  }

  atom operator+(atom rhs) const {
    rhs.x += x;
    if (rhs.x >= p1) rhs.x -= p1;
    rhs.y += y;
    if (rhs.y >= p2) rhs.y -= p2;
    return rhs;
  }

  atom operator*(const atom &rhs) const {
    return {
        (int)((ll)x * rhs.x % p1), //
        (int)((ll)y * rhs.y % p2),
    };
  }

  bool operator==(const atom &rhs) const { return x == rhs.x && y == rhs.y; }
};
const atom one = {1, 1};

struct segment {
  int l, r, mid;
  ll tag;
  ll min, max;
  atom pos, neg, pos_tag, neg_tag;
} p[N << 2];

void pushup(int u, ll tag, const atom &pos_tag, const atom &neg_tag) {
  p[u].tag += tag;
  p[u].pos_tag = p[u].pos_tag * pos_tag;
  p[u].neg_tag = p[u].neg_tag * neg_tag;
}

void pushdown(int u) {
  if (p[u].tag) {
    pushup(u << 1, p[u].tag, p[u].pos_tag, p[u].neg_tag);
    pushup(u << 1 | 1, p[u].tag, p[u].pos_tag, p[u].neg_tag);
    p[u].tag = 0;
    p[u].pos_tag = one;
    p[u].neg_tag = one;
  }
}

void maintain(int u) {
  p[u].min = min(p[u << 1].min, p[u << 1 | 1].min);
  p[u].max = max(p[u << 1].max, p[u << 1 | 1].max);
  p[u].pos = p[u << 1].pos + p[u << 1 | 1].pos;
  p[u].neg = p[u << 1].neg + p[u << 1 | 1].neg;
}

void build(int u, int l, int r) {
  p[u].l = l, p[u].r = r, p[u].mid = (l + r) >> 1;
  if (l == r) {
    p[u].min = p[u].max = a[l];
    p[u].pos = atom::get_base(a[l]);
    p[u].neg = atom::get_base(-a[l]);
    return;
  }
  build(u << 1, l, p[u].mid);
  build(u << 1 | 1, p[u].mid + 1, r);
  maintain(u);
  log("u=%d >> min=%lld max=%lld pos=%d,%d neg=%d,%d\n", u, p[u].min, p[u].max, p[u].pos.x, p[u].pos.y, p[u].neg.x, p[u].neg.y);
}

void modify(int u, int l, int r, ll tag, const atom &pos_tag, const atom &neg_tag) {
  if (p[u].l == l && p[u].r == r) {
    pushup(u, tag, pos_tag, neg_tag);
    return;
  }
  pushdown(u);
  if (r <= p[u].mid) {
    modify(u << 1, l, r, tag, pos_tag, neg_tag);
  } else if (l > p[u].mid) {
    modify(u << 1 | 1, l, r, tag, pos_tag, neg_tag);
  } else {
    modify(u << 1, l, p[u].mid, tag, pos_tag, neg_tag);
    modify(u << 1 | 1, p[u].mid + 1, r, tag, pos_tag, neg_tag);
  }
  maintain(u);
}

tuple<ll, ll, atom, atom> query(int u, int l, int r) {
  if (p[u].l == l && p[u].r == r) {
    return make_tuple(p[u].min, p[u].max, p[u].pos, p[u].neg);
  }
  pushdown(u);
  if (r <= p[u].mid) {
    return query(u << 1, l, r);
  } else if (l > p[u].mid) {
    return query(u << 1 | 1, l, r);
  } else {
    auto s1 = query(u << 1, l, p[u].mid);
    auto s2 = query(u << 1 | 1, p[u].mid + 1, r);
    return make_tuple(               //
        min(get<0>(s1), get<0>(s2)), //
        max(get<1>(s1), get<1>(s2)), //
        get<2>(s1) * get<2>(s2),     //
        get<3>(s1) * get<3>(s2)      //
    );
  }
}

int main() {
#ifdef memset0
  freopen("G.in", "r", stdin);
#endif
  cin.tie(0)->sync_with_stdio(0);

  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  build(1, 1, n);

  for (int o, l, r, v, i = 1; i <= m; i++) {
    cin >> o >> l >> r;
    log("> o=%d l=%d r=%d\n", o, l, r);
    if (o == 1) {
      cin >> v;
      modify(1, l, r, v, atom::get_base(v), atom::get_base(-v));
    } else {
      auto [min, max, pos, neg] = query(1, l, r);
      // log("! min=%d max=%d pos=%d,%d neg=%d,%d\n", min, max, pos.x, pos.y, neg.x, neg.y);
      ll s = min + max;
      if (pos == neg * atom::get_base(s)) {
        cout << "YES" << endl;
      } else {
        cout << "NO" << endl;
      }
    }
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5780kb

input:

8 4
1 2 3 4 5 6 7 8
2 1 8
1 1 4 4
2 1 6
2 1 8

output:

YES
NO
YES

result:

ok 3 token(s): yes count is 2, no count is 1

Test #2:

score: -100
Wrong Answer
time: 373ms
memory: 44300kb

input:

200000 200000
0 0 0 1 1 0 2 1 1 2 0 1 0 0 0 2 1 0 1 2 2 1 2 1 2 0 0 2 1 2 1 0 0 2 0 2 1 1 1 2 0 0 0 0 2 0 1 0 0 2 2 1 1 0 0 2 1 0 2 0 2 1 2 1 0 1 2 1 0 1 2 1 2 1 0 1 2 0 1 0 1 1 0 2 1 2 0 2 2 1 1 2 1 2 2 0 0 1 2 0 0 2 2 0 1 2 2 0 0 1 2 1 2 0 2 0 0 2 0 2 1 0 1 1 1 1 2 1 2 0 1 2 1 0 2 1 0 1 1 2 2 0 1 ...

output:

NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
NO
...

result:

wrong answer expected YES, found NO [464th token]