QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#487939#9155. 集合thangthang100 ✓194ms20024kbC++201.4kb2024-07-23 13:40:372024-07-23 13:40:38

Judging History

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

  • [2024-07-23 13:40:38]
  • 评测
  • 测评结果:100
  • 用时:194ms
  • 内存:20024kb
  • [2024-07-23 13:40:37]
  • 提交

answer

#include <bits/stdc++.h>
#define u64 unsigned long long

using namespace std;

const int N = 2e5 + 5, M = 3 * N, P = 2e5 + 7;

int n, m, q, a[2][N][3], f[N];
u64 h[2][M], Pw[N];
vector <int> com[2];

bool check(int id){
    for (int t = 0; t < 2; ++ t){
        com[t] = {};
        for (int i = 0; i < 3; ++ i) com[t].push_back(h[t][a[t][id][i]]);
        sort(com[t].begin(), com[t].end());
    }
    for (int i = 0; i < 3; ++ i) if (com[0][i] != com[1][i]) return false;
    return true;
}

void add(int id, int v){
    for (int t = 0; t < 2; ++ t){
        for (int i = 0; i < 3; ++ i) h[t][a[t][id][i]] += (Pw[id] * v);
    }
}

void solve(){
    cin >> n >> m >> q;
    for (int i = 1; i <= n; ++ i) for (int j = 0; j < 3; ++ j) cin >> a[0][i][j];
    for (int i = 1; i <= n; ++ i) for (int j = 0; j < 3; ++ j) cin >> a[1][i][j];
    Pw[0] = 1;
    for (int i = 1; i <= n; ++ i) Pw[i] = Pw[i - 1] * P;

    for (int i = 1, j = 1; i <= n; ++ i){
        while (j <= n && check(j)){
            add(j, 1);
            ++ j;
        }
        f[i] = j - 1;
        add(i, -1);
    }

    while (q --){
        int l, r; cin >> l >> r;
        if (f[l] >= r) cout << "Yes" << '\n';
        else cout << "No" << '\n';
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    solve();

    return 0;
}

详细


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 17ms
memory: 7824kb

Pretest #10:

score: 5
Accepted
time: 17ms
memory: 7696kb

Pretest #11:

score: 5
Accepted
time: 65ms
memory: 11868kb

Pretest #12:

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

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 104ms
memory: 7772kb

Pretest #16:

score: 5
Accepted
time: 113ms
memory: 7844kb

Pretest #17:

score: 5
Accepted
time: 7ms
memory: 10012kb

Pretest #18:

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

Pretest #19:

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

Pretest #20:

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

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 5
Accepted
time: 17ms
memory: 7668kb

Test #10:

score: 5
Accepted
time: 21ms
memory: 7724kb

Test #11:

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

Test #12:

score: 5
Accepted
time: 74ms
memory: 13916kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 104ms
memory: 7680kb

Test #16:

score: 5
Accepted
time: 104ms
memory: 9916kb

Test #17:

score: 5
Accepted
time: 7ms
memory: 7984kb

Test #18:

score: 5
Accepted
time: 8ms
memory: 10892kb

Test #19:

score: 5
Accepted
time: 176ms
memory: 11952kb

Test #20:

score: 5
Accepted
time: 182ms
memory: 19968kb

Extra Test:

score: 0
Extra Test Passed