QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#508244 | #9155. 集合 | wangif424 | 100 ✓ | 196ms | 30604kb | C++14 | 2.2kb | 2024-08-07 10:47:27 | 2024-08-07 10:47:28 |
Judging History
answer
#include <bits/stdc++.h>
#define R(x) x = read()
#define int unsigned long long
#define pii pair<int,int>
#define iax INT_MAX
#define iin INT_MIN
#define lax LLONG_MAX
#define lin LLONG_MIN
#define sqrt sqrtl
bool Mbe;
using namespace std;
char pbuf[1<<20], *pp=pbuf;
inline void push(const char &c){(pp-pbuf==1<<20)?fwrite(pbuf,1,1<<20,stdout),pp=pbuf,*pp++=c:*pp++=c;}
class io {public:~io() {fwrite(pbuf, 1, pp - pbuf, stdout);}} _;
inline void write(int x) {
x<0&&(push('-'),x=-x);
static int sta[60]={},top=0;
do{sta[top++]=x%10,x/=10;}while(x);
while(top)push(sta[--top]^'0');
}
#ifndef LOCAL
char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
inline int read() {
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){ch=='-'&&(f=-1);ch=getchar();}
while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
return x*f;
}
mt19937_64 rd(time(0));
int n,m,q;
int f[600100];
int c[600100],d[600100];
int hsa,hsb;
int a[200100][3],b[200100][3];
map<int,int> gs,gm;
int tor[200100];
int hsh(int x){
if(x==0)return x;
x^=x<<11;x^=x>>4;x^=x<<5;x^=x<<14;
x+=(++x)+(x++);
return x;
}
void add(int i,int tp){
if(tp==1)for(int j=0;j<3;j++){
int x=a[i][j],y=b[i][j];
hsa-=hsh(c[x]);hsb-=hsh(d[y]);
c[x]+=f[i];d[y]+=f[i];
hsa+=hsh(c[x]);hsb+=hsh(d[y]);
}else for(int j=0;j<3;j++){
int x=a[i][j],y=b[i][j];
hsa-=hsh(c[x]);hsb-=hsh(d[y]);
c[x]-=f[i];d[y]-=f[i];
hsa+=hsh(c[x]);hsb+=hsh(d[y]);
}
}
bool Med;
signed main(){
#ifndef LOCAL
cerr << (&Med-&Mbe)/1024.0/1024 << "MB\n";
#endif
R(n);R(m);R(q);
for(int i=1;i<=n;i++)tor[i]=lax;
for(int i=1;i<=n;i++)for(int j=0;j<3;j++)R(a[i][j]);
for(int i=1;i<=n;i++)for(int j=0;j<3;j++)R(b[i][j]);
for(int T=10;T>=1;T--){
for(int i=1;i<=n;i++)c[i]=d[i]=0,f[i]=rd();
hsa=hsb=0;add(1,1);
for(int l=1,r=1;l<=n;add(l,-1),l++){
while(r<=n&&hsa==hsb){
r++;
add(r,1);
}
tor[l]=min(tor[l],r-1);
}
}
while(q--){
R(int l),R(r);
if(r<=tor[l])puts("Yes");
else puts("No");
}
return 0;
}
/*
4 4 1
1 2 3 1 2 3 1 2 4 1 2 3
1 2 4 2 3 4 1 2 3 2 3 4
2 3
*/
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 0ms
memory: 14196kb
Pretest #2:
score: 5
Accepted
time: 0ms
memory: 16216kb
Pretest #3:
score: 5
Accepted
time: 3ms
memory: 16164kb
Pretest #4:
score: 5
Accepted
time: 0ms
memory: 16236kb
Pretest #5:
score: 5
Accepted
time: 0ms
memory: 16240kb
Pretest #6:
score: 5
Accepted
time: 0ms
memory: 16016kb
Pretest #7:
score: 5
Accepted
time: 0ms
memory: 16220kb
Pretest #8:
score: 5
Accepted
time: 0ms
memory: 16104kb
Pretest #9:
score: 5
Accepted
time: 6ms
memory: 18212kb
Pretest #10:
score: 5
Accepted
time: 6ms
memory: 18280kb
Pretest #11:
score: 5
Accepted
time: 99ms
memory: 28808kb
Pretest #12:
score: 5
Accepted
time: 108ms
memory: 27856kb
Pretest #13:
score: 5
Accepted
time: 0ms
memory: 16220kb
Pretest #14:
score: 5
Accepted
time: 0ms
memory: 16252kb
Pretest #15:
score: 5
Accepted
time: 35ms
memory: 18296kb
Pretest #16:
score: 5
Accepted
time: 35ms
memory: 18316kb
Pretest #17:
score: 5
Accepted
time: 9ms
memory: 18856kb
Pretest #18:
score: 5
Accepted
time: 14ms
memory: 18352kb
Pretest #19:
score: 5
Accepted
time: 142ms
memory: 27968kb
Pretest #20:
score: 5
Accepted
time: 196ms
memory: 30084kb
Final Tests
Test #1:
score: 5
Accepted
time: 0ms
memory: 16160kb
Test #2:
score: 5
Accepted
time: 0ms
memory: 14124kb
Test #3:
score: 5
Accepted
time: 0ms
memory: 16168kb
Test #4:
score: 5
Accepted
time: 0ms
memory: 16204kb
Test #5:
score: 5
Accepted
time: 3ms
memory: 16212kb
Test #6:
score: 5
Accepted
time: 0ms
memory: 14164kb
Test #7:
score: 5
Accepted
time: 0ms
memory: 16172kb
Test #8:
score: 5
Accepted
time: 0ms
memory: 16164kb
Test #9:
score: 5
Accepted
time: 4ms
memory: 16156kb
Test #10:
score: 5
Accepted
time: 4ms
memory: 18280kb
Test #11:
score: 5
Accepted
time: 105ms
memory: 29288kb
Test #12:
score: 5
Accepted
time: 117ms
memory: 30604kb
Test #13:
score: 5
Accepted
time: 0ms
memory: 18224kb
Test #14:
score: 5
Accepted
time: 4ms
memory: 16256kb
Test #15:
score: 5
Accepted
time: 33ms
memory: 16304kb
Test #16:
score: 5
Accepted
time: 39ms
memory: 18224kb
Test #17:
score: 5
Accepted
time: 13ms
memory: 16316kb
Test #18:
score: 5
Accepted
time: 14ms
memory: 20268kb
Test #19:
score: 5
Accepted
time: 155ms
memory: 27744kb
Test #20:
score: 5
Accepted
time: 175ms
memory: 30304kb
Extra Test:
score: 0
Extra Test Passed