QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#769843#9774. Same SumPlentyOfPenalty#WA 742ms63968kbC++204.5kb2024-11-21 19:35:052024-11-21 19:35:06

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:35:06]
  • 评测
  • 测评结果:WA
  • 用时:742ms
  • 内存:63968kb
  • [2024-11-21 19:35:05]
  • 提交

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;

#define int long long

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

template <const int mod> int power(int a, int b) {
  int s = 1;
  for (; b; b >>= 1, a = (lll)a * a % mod)
    if (b & 1) s = (lll)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)((lll)x * rhs.x % p1), //
        (int)((lll)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].min += tag;
  p[u].max += tag;
  p[u].tag += tag;
  p[u].pos = p[u].pos * pos_tag;
  p[u].neg = p[u].neg * neg_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=%lld >> min=%lld max=%lld pos=%lld,%lld neg=%lld,%lld\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)      //
    );
  }
}

signed 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=%lld l=%lld r=%lld\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=%lld max=%lld pos=%lld,%lld neg=%lld,%lld\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;
      }
    }
  }
}

详细

Test #1:

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

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: 742ms
memory: 63968kb

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:

YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
NO
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YES
YE...

result:

wrong answer expected NO, found YES [1st token]