QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#488492#9155. 集合liyelin100 ✓748ms103680kbC++142.6kb2024-07-24 08:29:272024-07-24 08:29:27

Judging History

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

  • [2024-07-24 08:29:27]
  • 评测
  • 测评结果:100
  • 用时:748ms
  • 内存:103680kb
  • [2024-07-24 08:29:27]
  • 提交

answer

#include <bits/stdc++.h>
#define PB push_back
#define MP make_pair
#define PII pair<int, int>
#define FOR(i, l, r) for (int i = (l); i <= (r); ++i)
#define ROF(i, r, l) for (int i = (r); i >= (l); --i)
#define FI first
#define SE second
#define SZ size()
#define ull unsigned long long
using namespace std;
const int N = 2e5 + 5;
const int M = 6e5 + 5;
const ull P = 1e9 + 9;
int n, mn[N], m, q, a[N][3], b[N][3], cnt;
ull pw[N], ha[M], hb[M];
unordered_map<ull, int> A, B;
unordered_map<ull, bool> qc;
void clean_up(int x, int k) {
    qc.clear();
    FOR (i, 0, 2) {
        int s = a[x][i];
        if (!qc[ha[s]]) {
            qc[ha[s]] = 1;
            cnt += (A[ha[s]] != B[ha[s]]) * k; 
        } 
        s = b[x][i];
        if (!qc[hb[s]]) {
            qc[hb[s]] = 1;
            cnt += (A[hb[s]] != B[hb[s]]) * k; 
        } 
    }
}
void add(int x) {
    clean_up(x, -1);
    FOR (i, 0, 2) {
        A[ha[a[x][i]]]--;
        B[hb[b[x][i]]]--;
    }
    clean_up(x, 1);
    FOR (i, 0, 2) {
        int s = a[x][i];
        ha[s] -= pw[x];
        s = b[x][i];
        hb[s] -= pw[x];
    }
    clean_up(x, -1);
    FOR (i, 0, 2) {
        A[ha[a[x][i]]]++;
        B[hb[b[x][i]]]++;
    }
    clean_up(x, 1);
}
void sub(int x) {
    clean_up(x, -1);
    FOR (i, 0, 2) {
        A[ha[a[x][i]]]--;
        B[hb[b[x][i]]]--;
    }
    clean_up(x, 1);
    FOR (i, 0, 2) {
        int s = a[x][i];
        ha[s] += pw[x];
        s = b[x][i];
        hb[s] += pw[x];
    }
    clean_up(x, -1);
    FOR (i, 0, 2) {
        A[ha[a[x][i]]]++;
        B[hb[b[x][i]]]++;
    }
    clean_up(x, 1);
}
void solve() {
    int l = 1;
    ull all = 0;
    FOR (i, 1, n) all += pw[i];
    A[all] = B[all] = m;
    FOR (i, 1, m) ha[i] = hb[i] = all;
    FOR (r, 1, n) {
        add(r);
//        FOR (i, 1, m) {
//        	cout << ha[i] << ' ';
//		}
//		cout << '\n';
//		FOR (i, 1, m) {
//			cout << hb[i] << ' ';
//		}
//		cout << '\n';
//      cout << cnt << '\n';
        while (cnt > 0) sub(l++);
        mn[r] = l;
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> q;
    pw[0] = 1;
    FOR (i, 1, n) pw[i] = pw[i - 1] * P;
    FOR (i, 1, n) {
        FOR (j, 0, 2) {
            cin >> a[i][j];
        }
    }
    FOR (i, 1, n) {
        FOR (j, 0, 2) {
            cin >> b[i][j];
        }
    }
    solve();
    FOR (i, 1, q) {
        int l, r;
        cin >> l >> r;
        if (mn[r] <= l) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 621ms
memory: 103680kb

Pretest #12:

score: 5
Accepted
time: 635ms
memory: 99768kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 106ms
memory: 12608kb

Pretest #16:

score: 5
Accepted
time: 98ms
memory: 12688kb

Pretest #17:

score: 5
Accepted
time: 49ms
memory: 21012kb

Pretest #18:

score: 5
Accepted
time: 42ms
memory: 24216kb

Pretest #19:

score: 5
Accepted
time: 748ms
memory: 101152kb

Pretest #20:

score: 5
Accepted
time: 686ms
memory: 97320kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 631ms
memory: 99964kb

Test #12:

score: 5
Accepted
time: 574ms
memory: 95108kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 115ms
memory: 12604kb

Test #16:

score: 5
Accepted
time: 101ms
memory: 10584kb

Test #17:

score: 5
Accepted
time: 39ms
memory: 22852kb

Test #18:

score: 5
Accepted
time: 42ms
memory: 22736kb

Test #19:

score: 5
Accepted
time: 721ms
memory: 98036kb

Test #20:

score: 5
Accepted
time: 686ms
memory: 98272kb

Extra Test:

score: 0
Extra Test Passed