QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#490152 | #9155. 集合 | Nangu | 100 ✓ | 185ms | 20116kb | C++14 | 1.4kb | 2024-07-25 12:07:41 | 2024-07-25 12:07:42 |
Judging History
answer
#include<bits/stdc++.h>
#define F(i, j, k) for(int i=(j); i<=(k); ++i)
#define R(i, j, k) for(int i=(j); i>=(k); --i)
#define G(v, i, u) for(int i=head[u], v=e[i].v; i; v=e[i=e[i].nxt].v)
#define de(x) cout<<#x<<" "<<x<<" "
#define nd cout<<endl
#define P cout<<"Line:"<<" "<<__LINE__<<endl
#define fin(x) freopen(x, "r", stdin)
#define fout(x) freopen(x, "w", stdout)
using namespace std;
typedef unsigned long long ull;
const int N=2e5+7, M=6e5+7;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int n, m, q, a[N][3], b[N][3], pos[N];
ull w[N], sa[M], sb[M], msk, s1, s2;
ull shf(ull x){
x^=msk, x^=x<<7, x^=x>>11, x^=x<<13;
return x;
}
void upd(int p, ull d){
for(auto x:a[p]) s1-=shf(sa[x]), sa[x]+=d*w[p], s1+=shf(sa[x]);
for(auto x:b[p]) s2-=shf(sb[x]), sb[x]+=d*w[p], s2+=shf(sb[x]);
}
signed main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin>>n>>m>>q;
F(i, 1, n) cin>>a[i][0]>>a[i][1]>>a[i][2];
F(i, 1, n) cin>>b[i][0]>>b[i][1]>>b[i][2];
F(i, 1, n) pos[i]=N;
int T=1;
while(T--){
msk=rng();
F(i, 1, n) w[i]=rng();
for(int i=1, j=1; i<=n; upd(i, -1), ++i){
while(j<=n && s1==s2) upd(j, 1), ++j;
if(s1==s2) pos[i]=min(pos[i], j-1);
else pos[i]=min(pos[i], j-2);
}
}
// F(i, 1, n) de(i), de(pos[i]), nd;
while(q--){
int a, b; cin>>a>>b;
cout<<(pos[a]<b?"No\n":"Yes\n");
}
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 1ms
memory: 9712kb
Pretest #2:
score: 5
Accepted
time: 1ms
memory: 9780kb
Pretest #3:
score: 5
Accepted
time: 1ms
memory: 11900kb
Pretest #4:
score: 5
Accepted
time: 1ms
memory: 9912kb
Pretest #5:
score: 5
Accepted
time: 1ms
memory: 9864kb
Pretest #6:
score: 5
Accepted
time: 1ms
memory: 9840kb
Pretest #7:
score: 5
Accepted
time: 1ms
memory: 11852kb
Pretest #8:
score: 5
Accepted
time: 0ms
memory: 9908kb
Pretest #9:
score: 5
Accepted
time: 20ms
memory: 11860kb
Pretest #10:
score: 5
Accepted
time: 14ms
memory: 9920kb
Pretest #11:
score: 5
Accepted
time: 60ms
memory: 12432kb
Pretest #12:
score: 5
Accepted
time: 60ms
memory: 11448kb
Pretest #13:
score: 5
Accepted
time: 2ms
memory: 9856kb
Pretest #14:
score: 5
Accepted
time: 2ms
memory: 9824kb
Pretest #15:
score: 5
Accepted
time: 101ms
memory: 9868kb
Pretest #16:
score: 5
Accepted
time: 100ms
memory: 11944kb
Pretest #17:
score: 5
Accepted
time: 6ms
memory: 9804kb
Pretest #18:
score: 5
Accepted
time: 5ms
memory: 10808kb
Pretest #19:
score: 5
Accepted
time: 159ms
memory: 10968kb
Pretest #20:
score: 5
Accepted
time: 178ms
memory: 20116kb
Final Tests
Test #1:
score: 5
Accepted
time: 1ms
memory: 9712kb
Test #2:
score: 5
Accepted
time: 1ms
memory: 9856kb
Test #3:
score: 5
Accepted
time: 1ms
memory: 9804kb
Test #4:
score: 5
Accepted
time: 0ms
memory: 11908kb
Test #5:
score: 5
Accepted
time: 1ms
memory: 9776kb
Test #6:
score: 5
Accepted
time: 1ms
memory: 11788kb
Test #7:
score: 5
Accepted
time: 1ms
memory: 11832kb
Test #8:
score: 5
Accepted
time: 1ms
memory: 9860kb
Test #9:
score: 5
Accepted
time: 16ms
memory: 9872kb
Test #10:
score: 5
Accepted
time: 21ms
memory: 9812kb
Test #11:
score: 5
Accepted
time: 60ms
memory: 12240kb
Test #12:
score: 5
Accepted
time: 64ms
memory: 11496kb
Test #13:
score: 5
Accepted
time: 2ms
memory: 9872kb
Test #14:
score: 5
Accepted
time: 2ms
memory: 9804kb
Test #15:
score: 5
Accepted
time: 101ms
memory: 9872kb
Test #16:
score: 5
Accepted
time: 107ms
memory: 9876kb
Test #17:
score: 5
Accepted
time: 6ms
memory: 9836kb
Test #18:
score: 5
Accepted
time: 8ms
memory: 10772kb
Test #19:
score: 5
Accepted
time: 170ms
memory: 12504kb
Test #20:
score: 5
Accepted
time: 185ms
memory: 20064kb
Extra Test:
score: 0
Extra Test Passed