QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#498372 | #9155. 集合 | biuld# | 100 ✓ | 432ms | 19316kb | C++14 | 1.8kb | 2024-07-30 12:55:13 | 2024-07-30 12:55:14 |
Judging History
answer
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
using namespace std;
const int N = 2e5;
const int M = 6e5;
int n, m, q;
struct node{
int s[3];
}a[N + 5], b[N + 5];
int w[N + 5];
ll ha[M + 5], hb[M + 5];
ull suma, sumb;
inline void update(int x, int f){
for(int i = 0; i < 3; ++ i){
// suma -= ha[a[x].s[i]] * ha[a[x].s[i]];
suma -= ha[a[x].s[i]] * ha[a[x].s[i]] * ha[a[x].s[i]];
ha[a[x].s[i]] = ha[a[x].s[i]] + f * w[x];
// cout << a[x].s[i] << ": " << ha[a[x].s[i]] << '\n';
// suma += ha[a[x].s[i]] * ha[a[x].s[i]];
suma += ha[a[x].s[i]] * ha[a[x].s[i]] * ha[a[x].s[i]];
// cout << suma << '\n';
// sumb -= hb[b[x].s[i]] * hb[b[x].s[i]];
sumb -= hb[b[x].s[i]] * hb[b[x].s[i]] * hb[b[x].s[i]];
hb[b[x].s[i]] = hb[b[x].s[i]] + f * w[x];
// cout << b[x].s[i] << ": " << hb[b[x].s[i]] << '\n';
// sumb += hb[b[x].s[i]] * hb[b[x].s[i]];
sumb += hb[b[x].s[i]] * hb[b[x].s[i]] * hb[b[x].s[i]];
}
}
int r[N + 5];
int x, y;
int main(){
// freopen("a.out", "w", stdout);
ios::sync_with_stdio(false);
cin >> n >> m >> q;
for(int i = 1; i <= n; ++ i) cin >> a[i].s[0] >> a[i].s[1] >> a[i].s[2];
for(int i = 1; i <= n; ++ i) cin >> b[i].s[0] >> b[i].s[1] >> b[i].s[2];
for(int i = 1; i <= n; ++ i) w[i] = rand();
// for(int i = 1; i <= n; ++ i) cout << w[i] << ' '; cout << '\n';
int j = 0;
for(int i = 1; i <= n; ++ i){
// cout << i << ":\n";
// cout << suma << ' ' << sumb << '\n';
while(j < i || (j < n && suma == sumb)) update(++ j, 1);
r[i] = suma == sumb ? j : j - 1;
update(i, -1);
}
// for(int i = 1; i <= n; ++ i){
// cout << i << ' ' << r[i] << '\n';
// }
while(q --){
cin >> x >> y;
cout << (r[x] >= y ? "Yes\n" : "No\n");
}
return 0;
}
/*
双指针
判断集合相等
*/
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 1ms
memory: 7680kb
Pretest #2:
score: 5
Accepted
time: 1ms
memory: 7664kb
Pretest #3:
score: 5
Accepted
time: 1ms
memory: 9784kb
Pretest #4:
score: 5
Accepted
time: 1ms
memory: 7648kb
Pretest #5:
score: 5
Accepted
time: 1ms
memory: 7664kb
Pretest #6:
score: 5
Accepted
time: 0ms
memory: 7720kb
Pretest #7:
score: 5
Accepted
time: 0ms
memory: 9784kb
Pretest #8:
score: 5
Accepted
time: 1ms
memory: 7688kb
Pretest #9:
score: 5
Accepted
time: 72ms
memory: 9772kb
Pretest #10:
score: 5
Accepted
time: 51ms
memory: 7724kb
Pretest #11:
score: 5
Accepted
time: 108ms
memory: 11276kb
Pretest #12:
score: 5
Accepted
time: 145ms
memory: 10952kb
Pretest #13:
score: 5
Accepted
time: 3ms
memory: 7824kb
Pretest #14:
score: 5
Accepted
time: 0ms
memory: 9888kb
Pretest #15:
score: 5
Accepted
time: 280ms
memory: 7804kb
Pretest #16:
score: 5
Accepted
time: 276ms
memory: 7764kb
Pretest #17:
score: 5
Accepted
time: 7ms
memory: 9880kb
Pretest #18:
score: 5
Accepted
time: 9ms
memory: 10808kb
Pretest #19:
score: 5
Accepted
time: 432ms
memory: 10684kb
Pretest #20:
score: 5
Accepted
time: 423ms
memory: 19316kb
Final Tests
Test #1:
score: 5
Accepted
time: 2ms
memory: 9860kb
Test #2:
score: 5
Accepted
time: 1ms
memory: 7752kb
Test #3:
score: 5
Accepted
time: 1ms
memory: 9792kb
Test #4:
score: 5
Accepted
time: 1ms
memory: 7716kb
Test #5:
score: 5
Accepted
time: 0ms
memory: 9776kb
Test #6:
score: 5
Accepted
time: 0ms
memory: 7736kb
Test #7:
score: 5
Accepted
time: 0ms
memory: 7724kb
Test #8:
score: 5
Accepted
time: 2ms
memory: 9740kb
Test #9:
score: 5
Accepted
time: 47ms
memory: 7744kb
Test #10:
score: 5
Accepted
time: 100ms
memory: 7672kb
Test #11:
score: 5
Accepted
time: 91ms
memory: 11364kb
Test #12:
score: 5
Accepted
time: 96ms
memory: 11512kb
Test #13:
score: 5
Accepted
time: 0ms
memory: 7660kb
Test #14:
score: 5
Accepted
time: 0ms
memory: 9812kb
Test #15:
score: 5
Accepted
time: 308ms
memory: 7736kb
Test #16:
score: 5
Accepted
time: 363ms
memory: 7852kb
Test #17:
score: 5
Accepted
time: 7ms
memory: 9848kb
Test #18:
score: 5
Accepted
time: 2ms
memory: 10800kb
Test #19:
score: 5
Accepted
time: 407ms
memory: 10736kb
Test #20:
score: 5
Accepted
time: 383ms
memory: 19272kb
Extra Test:
score: 0
Extra Test Passed