QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#930624#9774. Same SumLyc-123TL 369ms31404kbC++205.2kb2025-03-10 01:32:022025-03-10 01:32:04

Judging History

This is the latest submission verdict.

  • [2025-03-10 01:32:04]
  • Judged
  • Verdict: TL
  • Time: 369ms
  • Memory: 31404kb
Show
  • [2025-03-10 01:32:02]
  • Submitted

answer

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
// #define uint64_t __int128_t
const int MAXN = 2e5 + 10;
const int SEED = 1e9 + 7;
const uint64_t MOD = 100000041894234263;
uint64_t pw[MAXN], rpw[MAXN];
uint64_t rseed;
uint64_t mpow(__int128_t a, uint64_t b) {
    if (a == SEED && b < MAXN && pw[b]) return pw[b];
    uint64_t md = MOD;
    __int128_t ret = 1;
    for (; b; b >>= 1) {
        if (b & 1) ret = ret * a % md;
        a = a * a % md;
    }
    // if (a == SEED && b < MAXN) pw[b] = ret;
    return ret;
}
uint64_t revpow(uint64_t a, uint64_t b) {
    if (a == SEED && b < MAXN && rpw[b]) return rpw[b];
    return mpow(rseed, b);
}
class SegmentTree {
    struct TreeNode {
        int l, r;
        uint64_t expr;
        uint64_t tag;
        uint64_t rev;
        uint64_t sum;
    } a[4 * MAXN];
    uint64_t val[MAXN];
    uint64_t seed;
public:
    SegmentTree() {
        seed = SEED;
    }
    void cat_val(int i, uint64_t x) { val[i] = x; }
    void build(int u, int l, int r) {
        a[u].l = l, a[u].r = r;
        if (l == r) {
            a[u].expr = pw[val[l]];
            a[u].rev = rpw[val[l]];
            a[u].sum = val[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        a[u].expr = (a[u << 1].expr + a[u << 1 | 1].expr) % MOD;
        a[u].rev = (a[u << 1].rev + a[u << 1 | 1].rev) % MOD;
        a[u].sum = (a[u << 1].sum + a[u << 1 | 1].sum);
    }
    void update(int u) {
        if (a[u].tag == 0) return;
        if (a[u].l == a[u].r) return;
        a[u << 1].tag += a[u].tag;
        a[u << 1 | 1].tag += a[u].tag;
        __int128_t pww, rpww;
        if (a[u].tag < MAXN) pww = pw[a[u].tag];
        else pww = mpow(SEED, a[u].tag);
        if (a[u].tag < MAXN) rpww = rpw[a[u].tag];
        else rpww = revpow(SEED, a[u].tag);
        a[u << 1].expr = (__int128_t)a[u << 1].expr * pww % MOD;
        a[u << 1 | 1].expr = (__int128_t)a[u << 1 | 1].expr * pww % MOD;
        a[u << 1].rev = (__int128_t)a[u << 1].rev * rpww % MOD;
        a[u << 1 | 1].rev = (__int128_t)a[u << 1 | 1].rev * rpww % MOD;
        a[u << 1].sum = a[u << 1].sum + (__int128_t)a[u].tag * (a[u << 1].r - a[u << 1].l + 1);
        a[u << 1 | 1].sum = a[u << 1 | 1].sum + (__int128_t)a[u].tag * (a[u << 1 | 1].r - a[u << 1 | 1].l + 1);
        a[u].tag = 0;
    }
    void add(int u, int l, int r, uint64_t w) {
        if (l <= a[u].l && r >= a[u].r) {
            a[u].expr = (__int128_t)a[u].expr * pw[w] % MOD;
            a[u].rev = (__int128_t)a[u].rev * rpw[w] % MOD;
            a[u].sum = a[u].sum + (__int128_t)w * (a[u].r - a[u].l + 1);
            a[u].tag += w;
            return;
        }
        update(u);
        int mid = (a[u].l + a[u].r) >> 1;
        if (l <= mid) add(u << 1, l, r, w);
        if (r > mid) add(u << 1 | 1, l, r, w);
        a[u].expr = (a[u << 1].expr + a[u << 1 | 1].expr) % MOD;
        a[u].rev = (a[u << 1].rev + a[u << 1 | 1].rev) % MOD;
        a[u].sum = (a[u << 1].sum + a[u << 1 | 1].sum);


    }
    uint64_t query_expr(int u, int l, int r) {
        if (l <= a[u].l && r >= a[u].r) return a[u].expr;
        update(u);
        int mid = (a[u].l + a[u].r) >> 1;
        uint64_t ret = 0;
        if (l <= mid) ret += query_expr(u << 1, l, r);
        if (r > mid) ret += query_expr(u << 1 | 1, l, r);
        return ret % MOD;
    }
    uint64_t query_rev(int u, int l, int r) {
        if (l <= a[u].l && r >= a[u].r) return a[u].rev;
        update(u);
        int mid = (a[u].l + a[u].r) >> 1;
        uint64_t ret = 0;
        if (l <= mid) ret += query_rev(u << 1, l, r);
        if (r > mid) ret += query_rev(u << 1 | 1, l, r);
        return ret % MOD;
    }
    uint64_t query_sum(int u, int l, int r) {
        if (l <= a[u].l && r >= a[u].r) return a[u].sum;
        update(u);
        int mid = (a[u].l + a[u].r) >> 1;
        uint64_t ret = 0;
        if (l <= mid) ret += query_sum(u << 1, l, r);
        if (r > mid) ret += query_sum(u << 1 | 1, l, r);
        return ret;
    }
} SegTree1;

int main() {
	std::ios::sync_with_stdio(false); std::cin.tie(nullptr);

	int n, q;
	std::cin >> n >> q;

	for(int i = 1; i <= n; i++) {
		long long x;
        cin >> x;
        SegTree1.cat_val(i, x);
	}

	uint64_t P = 100000041894234263;
	uint64_t Phi = P - 1;
	
	pw[0] = rpw[0] = 1; rpw[1] = mpow(SEED, Phi - 1);

	for(int i = 1; i <= 2e5; i++) {
		pw[i] = (__int128) pw[i - 1] * SEED % P;
		rpw[i] = (__int128) rpw[i - 1] * rpw[1] % P;
	}

	SegTree1.build(1, 1, n);
	for(int i = 1; i <= q; i++) {
		int opt, x, y; long long w;
		std::cin >> opt >> x >> y;
		if(opt == 1) {
			std::cin >> w;
			SegTree1.add(1, x, y, w);
		} else {
			long long _M = SegTree1.query_expr(1, x, y),
			   _m = SegTree1.query_rev(1,  x, y),
			   _avg = SegTree1.query_sum(1, x, y);

		//	std::cout << _M << " " << _m << " " << _avg << "\n";

			if(2ll * _avg % (y - x + 1) != 0) {
				std::cout << "NO\n";
			} else {
				_avg = 2ll * _avg / (y - x + 1);
				std::cout << ((_M == (__int128) mpow(SEED, _avg) * _m % P) ? "YES" : "NO") << "\n";
			}
		}
	}
	return 0;
}
源文件, 语言: C++20

详细

Test #1:

score: 100
Accepted
time: 2ms
memory: 9572kb

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: 0
Accepted
time: 360ms
memory: 31324kb

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:

ok 100047 token(s): yes count is 22, no count is 100025

Test #3:

score: 0
Accepted
time: 369ms
memory: 31404kb

input:

200000 200000
5 5 2 0 1 1 4 1 1 0 4 2 2 5 5 4 1 2 2 0 3 3 3 2 5 4 1 5 1 0 0 4 3 4 2 2 3 1 4 2 0 5 4 0 2 5 5 5 2 2 3 4 0 2 2 5 0 2 3 5 4 0 0 2 1 0 5 3 1 4 5 2 2 3 4 5 0 5 5 5 3 3 0 1 4 3 0 0 3 2 2 0 4 5 5 5 2 4 5 2 5 3 1 1 5 2 1 0 1 0 5 0 0 1 5 1 5 3 1 5 3 5 4 0 2 2 4 2 5 2 3 4 5 4 3 5 2 5 2 4 5 3 4 ...

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:

ok 99734 token(s): yes count is 10, no count is 99724

Test #4:

score: -100
Time Limit Exceeded

input:

200000 200000
185447 70128 80288 38126 188018 126450 46081 189881 15377 21028 12588 100061 7218 74518 162803 34448 90998 44793 167718 16370 136024 153269 186316 137564 3082 169700 175712 19214 82647 72919 170919 142138 57755 168197 81575 126456 183138 106882 167154 184388 198667 190302 188371 183732...

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:





					

	




			

						

				

					
					

						English
						繁體中文
						简体中文
					

				

				
				
				
服务器时间: 2025-03-15 08:03:04 | 开源项目