QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#487939 | #9155. 集合 | thangthang | 100 ✓ | 194ms | 20024kb | C++20 | 1.4kb | 2024-07-23 13:40:37 | 2024-07-23 13:40:38 |
Judging History
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