QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#488806#9155. 集合chy_is_a_fish100 ✓208ms28492kbC++141.6kb2024-07-24 15:27:322024-07-24 15:27:33

Judging History

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

  • [2024-07-24 15:27:33]
  • 评测
  • 测评结果:100
  • 用时:208ms
  • 内存:28492kb
  • [2024-07-24 15:27:32]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 6e5 + 5, K = 13131;
const ll mod = 1e12 + 39;
int n, m, q, a[N][3], b[N][3], R[N];
ll h[N], A[N], B[N], sa, sb;
ll F(ll x) 
{
    unsigned long long t = x;
    t ^= t >> 5;
    t ^= t << 14;
    t ^= t >> 27;
    t ^= t << 39;
    x = (t % mod);
    return x;
}
void add(ll w[], ll& s, ll v, int p, int t) {s -= F(w[p]); w[p] += t * v; s += F(w[p]);}
int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m >> q; h[0] = 1;
    for (int i = 1; i <= n; i++) h[i] = h[i-1] * K % mod;
    for (int i = 1; i <= n; i++) cin >> a[i][0] >> a[i][1] >> a[i][2];
    for (int i = 1; i <= n; i++) cin >> b[i][0] >> b[i][1] >> b[i][2];
    for (int l = 1, r = 0; l <= n; l++)
    {
        if (r < l - 1) r = l - 1;
        if (r < n)
        {
            do
            {
                r++;
                for (int j = 0; j < 3; j++) add(A, sa, h[r], a[r][j], 1);
                for (int j = 0; j < 3; j++) add(B, sb, h[r], b[r][j], 1);
            }
            while (r < n && sa == sb);
        }
        if (sa != sb) 
        {
            for (int j = 0; j < 3; j++) add(A, sa, h[r], a[r][j], -1);
            for (int j = 0; j < 3; j++) add(B, sb, h[r], b[r][j], -1);
            r--;
        }
        R[l] = r;
        for (int j = 0; j < 3; j++) add(A, sa, h[l], a[l][j], -1);
        for (int j = 0; j < 3; j++) add(B, sb, h[l], b[l][j], -1);
    }
    while (q--)
    {
        int l, r; cin >> l >> r;
        cout << (r <= R[l] ? "Yes" : "No") << "\n";
    }
    return 0;
}

Details


Pretests

Pretest #1:

score: 5
Accepted
time: 2ms
memory: 11776kb

Pretest #2:

score: 5
Accepted
time: 0ms
memory: 11748kb

Pretest #3:

score: 5
Accepted
time: 0ms
memory: 11788kb

Pretest #4:

score: 5
Accepted
time: 1ms
memory: 11820kb

Pretest #5:

score: 5
Accepted
time: 1ms
memory: 11836kb

Pretest #6:

score: 5
Accepted
time: 1ms
memory: 11748kb

Pretest #7:

score: 5
Accepted
time: 1ms
memory: 11756kb

Pretest #8:

score: 5
Accepted
time: 1ms
memory: 11816kb

Pretest #9:

score: 5
Accepted
time: 22ms
memory: 11764kb

Pretest #10:

score: 5
Accepted
time: 18ms
memory: 11756kb

Pretest #11:

score: 5
Accepted
time: 80ms
memory: 18048kb

Pretest #12:

score: 5
Accepted
time: 76ms
memory: 19956kb

Pretest #13:

score: 5
Accepted
time: 2ms
memory: 11756kb

Pretest #14:

score: 5
Accepted
time: 0ms
memory: 11936kb

Pretest #15:

score: 5
Accepted
time: 112ms
memory: 11828kb

Pretest #16:

score: 5
Accepted
time: 108ms
memory: 11984kb

Pretest #17:

score: 5
Accepted
time: 4ms
memory: 11848kb

Pretest #18:

score: 5
Accepted
time: 9ms
memory: 12772kb

Pretest #19:

score: 5
Accepted
time: 194ms
memory: 15960kb

Pretest #20:

score: 5
Accepted
time: 208ms
memory: 28016kb

Final Tests

Test #1:

score: 5
Accepted
time: 2ms
memory: 11828kb

Test #2:

score: 5
Accepted
time: 1ms
memory: 11840kb

Test #3:

score: 5
Accepted
time: 0ms
memory: 11760kb

Test #4:

score: 5
Accepted
time: 0ms
memory: 11780kb

Test #5:

score: 5
Accepted
time: 1ms
memory: 11772kb

Test #6:

score: 5
Accepted
time: 1ms
memory: 11776kb

Test #7:

score: 5
Accepted
time: 1ms
memory: 11832kb

Test #8:

score: 5
Accepted
time: 1ms
memory: 13860kb

Test #9:

score: 5
Accepted
time: 20ms
memory: 11764kb

Test #10:

score: 5
Accepted
time: 19ms
memory: 11892kb

Test #11:

score: 5
Accepted
time: 84ms
memory: 18056kb

Test #12:

score: 5
Accepted
time: 80ms
memory: 20104kb

Test #13:

score: 5
Accepted
time: 2ms
memory: 11760kb

Test #14:

score: 5
Accepted
time: 2ms
memory: 11996kb

Test #15:

score: 5
Accepted
time: 111ms
memory: 11896kb

Test #16:

score: 5
Accepted
time: 108ms
memory: 11852kb

Test #17:

score: 5
Accepted
time: 9ms
memory: 11908kb

Test #18:

score: 5
Accepted
time: 10ms
memory: 12768kb

Test #19:

score: 5
Accepted
time: 195ms
memory: 18012kb

Test #20:

score: 5
Accepted
time: 203ms
memory: 28492kb

Extra Test:

score: 0
Extra Test Passed