QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#526886 | #9155. 集合 | _LSA_ | 100 ✓ | 507ms | 80840kb | C++14 | 1.9kb | 2024-08-22 00:09:14 | 2024-08-22 00:09:14 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define fi first
#define se second
#define mk make_pair
using namespace std;
ll read(){
ll X = 0,r = 1;
char ch = getchar();
while(!isdigit(ch) && ch != '-') ch = getchar();
if(ch == '-') r = -1,ch = getchar();
while(isdigit(ch)) X = X*10+ch-'0',ch = getchar();
return X*r;
}
const int N = 2e5+10;
const int M = 6e5+10;
int n,m,q;
int a[N][3],b[N][3];
ull P = 13131;
ull val[N],pw[N];
mt19937_64 rnd(time(0));
vector<pii> v[N];
bool ans[1010100];
unordered_map<ull,int> mp;
int cnt;
ull hsh[M][2];
bool add(int x,int y){
for(int k=0;k<=2;k++){
if(mp[hsh[a[x][k]][0]] == 1) cnt--;
mp[hsh[a[x][k]][0]]--;
if(mp[hsh[a[x][k]][0]] == -1) cnt++;
hsh[a[x][k]][0] += val[x]*pw[x]*y;
if(mp[hsh[a[x][k]][0]] == -1) cnt--;
mp[hsh[a[x][k]][0]]++;
if(mp[hsh[a[x][k]][0]] == 1) cnt++;
}
for(int k=0;k<=2;k++){
if(mp[hsh[b[x][k]][1]] == -1) cnt--;
mp[hsh[b[x][k]][1]]++;
if(mp[hsh[b[x][k]][1]] == 1) cnt++;
hsh[b[x][k]][1] += val[x]*pw[x]*y;
if(mp[hsh[b[x][k]][1]] == 1) cnt--;
mp[hsh[b[x][k]][1]]--;
if(mp[hsh[b[x][k]][1]] == -1) cnt++;
}
return (!cnt);
}
signed main(){
n = read(); m = read(); q = read();
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();
}
for(int i=1;i<=q;i++){
int l = read(),r = read();
v[l].push_back(mk(r,i));
}
pw[0] = 1;
for(int i=1;i<=n;i++) pw[i] = pw[i-1]*P;
for(int i=1;i<=n;i++) val[i] = rnd();
for(int l=1,r=0;l<=n;l++){
if(r < l) add(l,1),r = l;
while(r <= n && add(++r,1));
if(r <= n) add(r--,-1);
for(auto it : v[l])
ans[it.se] = it.fi <= r;
add(l,-1);
}
for(int i=1;i<=q;i++) puts(ans[i] ? "Yes" : "No");
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 15952kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 15976kb
Pretest #3:
score: 5
Accepted
time: 0ms
memory: 15956kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 15932kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 16008kb
Pretest #6:
score: 5
Accepted
time: 2ms
memory: 16016kb
Pretest #7:
score: 5
Accepted
time: 0ms
memory: 16212kb
Pretest #8:
score: 5
Accepted
time: 2ms
memory: 16004kb
Pretest #9:
score: 5
Accepted
time: 12ms
memory: 19780kb
Pretest #10:
score: 5
Accepted
time: 13ms
memory: 17748kb
Pretest #11:
score: 5
Accepted
time: 376ms
memory: 71288kb
Pretest #12:
score: 5
Accepted
time: 371ms
memory: 68560kb
Pretest #13:
score: 5
Accepted
time: 5ms
memory: 16380kb
Pretest #14:
score: 5
Accepted
time: 0ms
memory: 18400kb
Pretest #15:
score: 5
Accepted
time: 49ms
memory: 27856kb
Pretest #16:
score: 5
Accepted
time: 65ms
memory: 27988kb
Pretest #17:
score: 5
Accepted
time: 30ms
memory: 22464kb
Pretest #18:
score: 5
Accepted
time: 25ms
memory: 21188kb
Pretest #19:
score: 5
Accepted
time: 458ms
memory: 76236kb
Pretest #20:
score: 5
Accepted
time: 475ms
memory: 80296kb
Final Tests
Test #1:
score: 5
Accepted
time: 3ms
memory: 16012kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 17992kb
Test #3:
score: 5
Accepted
time: 2ms
memory: 16020kb
Test #4:
score: 5
Accepted
time: 2ms
memory: 16164kb
Test #5:
score: 5
Accepted
time: 0ms
memory: 18060kb
Test #6:
score: 5
Accepted
time: 2ms
memory: 15968kb
Test #7:
score: 5
Accepted
time: 0ms
memory: 18028kb
Test #8:
score: 5
Accepted
time: 2ms
memory: 18044kb
Test #9:
score: 5
Accepted
time: 13ms
memory: 19772kb
Test #10:
score: 5
Accepted
time: 12ms
memory: 17736kb
Test #11:
score: 5
Accepted
time: 357ms
memory: 68624kb
Test #12:
score: 5
Accepted
time: 342ms
memory: 64588kb
Test #13:
score: 5
Accepted
time: 2ms
memory: 16584kb
Test #14:
score: 5
Accepted
time: 2ms
memory: 16572kb
Test #15:
score: 5
Accepted
time: 48ms
memory: 27860kb
Test #16:
score: 5
Accepted
time: 61ms
memory: 30008kb
Test #17:
score: 5
Accepted
time: 23ms
memory: 20332kb
Test #18:
score: 5
Accepted
time: 29ms
memory: 21184kb
Test #19:
score: 5
Accepted
time: 479ms
memory: 74784kb
Test #20:
score: 5
Accepted
time: 507ms
memory: 80840kb
Extra Test:
score: 0
Extra Test Passed