QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#511397 | #9155. 集合 | songke | 100 ✓ | 1135ms | 85736kb | C++14 | 1.2kb | 2024-08-09 20:28:34 | 2024-08-09 20:28:34 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
#define F(i,l,r) for(int i=(l),i##end=(r);i<=i##end;++i)
#define G(i,l,r) for(int i=(l),i##end=(r);i>=i##end;--i)
#define x first
#define y second
#define int long long
#define pii pair<int,int>
#define mp(x,y) make_pair(x,y)
#define ep emplace_back
using namespace std;
int base=1233,m,q,qp[600009],has[12000009],mod=1e18+3;
unordered_map<ll,int> ma;mt19937_64 rnd(time(0));
int f[200009];int err;
vector<int> a[200009],b[200009];
void add(int i)
{
for(auto u:a[i])
{
err-=ma[has[u]]==1;
err+=ma[has[u]]==0;
ma[has[u]]--;
has[u]^=qp[i];
err+=ma[has[u]]==0;
err-=ma[has[u]]==-1;
ma[has[u]]++;
}
for(auto u:b[i])
{
err-=ma[has[u+m]]==-1;
err+=ma[has[u+m]]==0;
ma[has[u+m]]++;
has[u+m]^=qp[i];
err+=ma[has[u+m]]==0;
err-=ma[has[u+m]]==1;
ma[has[u+m]]--;
}
}
main()
{
int n;
cin>>n>>m>>q;
qp[0]=1;
F(i,1,n) qp[i]=rnd();
F(i,1,n)F(j,0,2){int x;cin>>x;a[i].ep(x);}
F(i,1,n)F(j,0,2){int x;cin>>x;b[i].ep(x);}
F(i,1,n)
{
f[i]=f[i-1];
add(i);
while(err && f[i]<i) add(++f[i]);
}
F(i,1,q)
{
int l,r;
cin>>l>>r;
if(l>f[r]) cout<<"Yes\n";
else cout<<"No\n";
}
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 16952kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 17220kb
Pretest #3:
score: 5
Accepted
time: 3ms
memory: 18256kb
Pretest #4:
score: 5
Accepted
time: 4ms
memory: 17388kb
Pretest #5:
score: 5
Accepted
time: 3ms
memory: 18456kb
Pretest #6:
score: 5
Accepted
time: 3ms
memory: 17984kb
Pretest #7:
score: 5
Accepted
time: 0ms
memory: 17392kb
Pretest #8:
score: 5
Accepted
time: 3ms
memory: 18048kb
Pretest #9:
score: 5
Accepted
time: 91ms
memory: 18344kb
Pretest #10:
score: 5
Accepted
time: 103ms
memory: 17140kb
Pretest #11:
score: 5
Accepted
time: 497ms
memory: 83920kb
Pretest #12:
score: 5
Accepted
time: 522ms
memory: 81288kb
Pretest #13:
score: 5
Accepted
time: 4ms
memory: 19416kb
Pretest #14:
score: 5
Accepted
time: 4ms
memory: 19016kb
Pretest #15:
score: 5
Accepted
time: 464ms
memory: 18524kb
Pretest #16:
score: 5
Accepted
time: 520ms
memory: 18912kb
Pretest #17:
score: 5
Accepted
time: 41ms
memory: 23628kb
Pretest #18:
score: 5
Accepted
time: 38ms
memory: 23816kb
Pretest #19:
score: 5
Accepted
time: 1032ms
memory: 81000kb
Pretest #20:
score: 5
Accepted
time: 1131ms
memory: 85524kb
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 16936kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 17204kb
Test #3:
score: 5
Accepted
time: 3ms
memory: 18048kb
Test #4:
score: 5
Accepted
time: 0ms
memory: 18880kb
Test #5:
score: 5
Accepted
time: 0ms
memory: 17816kb
Test #6:
score: 5
Accepted
time: 2ms
memory: 17272kb
Test #7:
score: 5
Accepted
time: 3ms
memory: 18376kb
Test #8:
score: 5
Accepted
time: 0ms
memory: 18648kb
Test #9:
score: 5
Accepted
time: 92ms
memory: 18312kb
Test #10:
score: 5
Accepted
time: 92ms
memory: 18644kb
Test #11:
score: 5
Accepted
time: 447ms
memory: 79404kb
Test #12:
score: 5
Accepted
time: 465ms
memory: 78420kb
Test #13:
score: 5
Accepted
time: 8ms
memory: 17448kb
Test #14:
score: 5
Accepted
time: 8ms
memory: 18812kb
Test #15:
score: 5
Accepted
time: 494ms
memory: 17812kb
Test #16:
score: 5
Accepted
time: 492ms
memory: 18132kb
Test #17:
score: 5
Accepted
time: 30ms
memory: 23692kb
Test #18:
score: 5
Accepted
time: 37ms
memory: 23824kb
Test #19:
score: 5
Accepted
time: 947ms
memory: 78760kb
Test #20:
score: 5
Accepted
time: 1135ms
memory: 85736kb
Extra Test:
score: 0
Extra Test Passed