QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#560981#9155. 集合oyzr100 ✓600ms29564kbC++232.1kb2024-09-12 19:17:562024-09-12 19:17:56

Judging History

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

  • [2024-09-12 19:17:56]
  • 评测
  • 测评结果:100
  • 用时:600ms
  • 内存:29564kb
  • [2024-09-12 19:17:56]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5, MAXM = 6e5 + 5, MAXQ = 1e6 + 5, MOD = 998244353;
int read(){
    char c = getchar();
    while (c > '9' || c < '0')
        c = getchar();
    int res = 0;
    while (c >= '0' && c <= '9'){
        res = (res << 3) + (res << 1) + (c ^ 48);
        c = getchar();
    }
    return res;
}
long long qpow(long long a, long long b){
    long long res = 1;
    for (; b; b >>= 1, a = a * a % MOD)
        if (b & 1)
            res = res * a % MOD;
    return res;
}
long long base, p;
int a[MAXN][3], b[MAXN][3];
long long ha[MAXM], hb[MAXM];
long long bp[MAXN], olda[MAXM], oldb[MAXM];
long long numa = 0, numb = 0;
int cnt = 0;
void insert(int id, int k){
    cnt++;
    for (int i = 0; i < 3; i++){
        int x = a[id][i];
        numa -= olda[x];
        ha[x] += bp[id] * k; ha[x] = (ha[x] + MOD) % MOD;
        olda[x] = qpow(p, ha[x]);
        numa += olda[x]; numa = (numa % MOD + MOD) % MOD;
    }
    for (int i = 0; i < 3; i++){
        int x = b[id][i];
        numb -= oldb[x];
        hb[x] += bp[id] * k; hb[x] = (hb[x] + MOD) % MOD;
        oldb[x] = qpow(p, hb[x]);
        numb += oldb[x]; numb = (numb % MOD + MOD) % MOD;
    }
}
int ans[MAXN];
mt19937 rnd(time(0));
int main(){
    base = rnd() % MOD, p = rnd() % MOD;
    int n = read(), m = read(), q = read();
    bp[0] = 1;
    for (int i = 1; i <= n; i++)
        bp[i] = bp[i - 1] * base % MOD;
    for (int i = 1; i <= m; i++)
        olda[i] = oldb[i] = 1;
    for (int i = 1; i <= n; i++)
        a[i][0] = read(), a[i][1] = read(), a[i][2] = read();
    for (int i = 1; i <= n; i++)
        b[i][0] = read(), b[i][1] = read(), b[i][2] = read();
    int r = 0;
    for (int l = 1; l <= n; l++){
        while (numa == numb && r < n){
            r++;
            insert(r, 1);
        }
        ans[l] = r - (numa != numb);
        insert(l, -1);
    }
    while (q--){
        int l = read(), r = read();
        if (r <= ans[l])
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 51ms
memory: 13956kb

Pretest #10:

score: 5
Accepted
time: 31ms
memory: 14036kb

Pretest #11:

score: 5
Accepted
time: 362ms
memory: 14400kb

Pretest #12:

score: 5
Accepted
time: 380ms
memory: 16844kb

Pretest #13:

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

Pretest #14:

score: 5
Accepted
time: 6ms
memory: 14040kb

Pretest #15:

score: 5
Accepted
time: 244ms
memory: 13976kb

Pretest #16:

score: 5
Accepted
time: 239ms
memory: 12060kb

Pretest #17:

score: 5
Accepted
time: 34ms
memory: 16120kb

Pretest #18:

score: 5
Accepted
time: 26ms
memory: 16440kb

Pretest #19:

score: 5
Accepted
time: 600ms
memory: 16896kb

Pretest #20:

score: 5
Accepted
time: 509ms
memory: 29432kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 5
Accepted
time: 23ms
memory: 11976kb

Test #10:

score: 5
Accepted
time: 59ms
memory: 13956kb

Test #11:

score: 5
Accepted
time: 382ms
memory: 17080kb

Test #12:

score: 5
Accepted
time: 347ms
memory: 17276kb

Test #13:

score: 5
Accepted
time: 3ms
memory: 16168kb

Test #14:

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

Test #15:

score: 5
Accepted
time: 223ms
memory: 11924kb

Test #16:

score: 5
Accepted
time: 215ms
memory: 13980kb

Test #17:

score: 5
Accepted
time: 30ms
memory: 11928kb

Test #18:

score: 5
Accepted
time: 28ms
memory: 17180kb

Test #19:

score: 5
Accepted
time: 540ms
memory: 16504kb

Test #20:

score: 5
Accepted
time: 516ms
memory: 29564kb

Extra Test:

score: 0
Extra Test Passed