QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#492164 | #9155. 集合 | zwh2008# | 100 ✓ | 831ms | 310956kb | C++14 | 2.2kb | 2024-07-26 10:02:45 | 2024-07-26 10:02:45 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pi=pair<int,int>;
#define fi first
#define se second
const int N=2e5+5,M=N*8;
int n,m,q,tot,L[N],mx[20][N],ps[N][8],r[M];
bool ans[M],vis[M];
array<int,3>a[N],b[N];
pair<int,vector<int>>c[M][5];
unordered_map<ll,int>mp;
int ask(int l,int r){int k=__lg(r-l+1);return max(mx[k][l],mx[k][r-(1<<k)+1]);}
inline vector<int>calc(vector<int>&a,vector<int>&b) {
vector<int>c;
for(int i:a)if(b[0]==i||b[1]==i||b[2]==i)c.push_back(i);
return c;
}
void work(array<int,3>*a,array<int,3>*b) {
for(int i=1;i<=tot;i++) {
vis[i]=0,r[i]=0;
for(int j=0;j<5;j++)c[i][j]={0,{}};
}
tot=0,mp.clear();
for(int i=1;i<=n;i++) {
vector<int>d={a[i][0],a[i][1],a[i][2]};
sort(d.begin(),d.end());
for(int j=0;j<8;j++) {
ll s=0;
for(int k=0;k<3;k++)if(j>>k&1)s=s*(m+1)+d[k];
if(!mp.count(s))mp[s]=++tot,c[tot][r[tot]=1]={0,{}};
ps[i][j]=mp[s];
}
}
for(int i=1;i<=n;i++) {
vector<int>ns={b[i][0],b[i][1],b[i][2]};
for(int j=0;j<8;j++) {
int id=ps[i][j],ct=__builtin_popcount(j);
int rr=r[id];r[id]=0;
for(int o=0;o<rr;o++) {
pair<int,vector<int>>k=c[id][o];
vector<int>t=calc(k.se,ns);
if(!r[id]||t!=c[id][r[id]-1].se)c[id][r[id]++]={k.fi,t};
c[id][r[id]-1].fi=k.fi;
}
if(!r[id]||ns!=c[id][r[id]-1].se)c[id][r[id]++]={i,ns};
c[id][r[id]-1].fi=i;
for(int k=0;k<r[id];k++)if(c[id][k].se.size()<ct)L[i]=max(L[i],c[id][k].fi);
}
}
}
int main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m>>q;
for(int i=1;i<=n;i++)cin>>a[i][0]>>a[i][1]>>a[i][2];
for(int i=1;i<=n;i++)cin>>b[i][0]>>b[i][1]>>b[i][2];
work(a,b),work(b,a);
for(int i=1;i<=n;i++)mx[0][i]=L[i];
for(int i=1;1<<i<=n;i++)for(int j=1;j<=n-(1<<i)+1;j++)mx[i][j]=max(mx[i-1][j],mx[i-1][j+(1<<i-1)]);
while(q--) {
int l,r;cin>>l>>r;
cout<<(ask(l,r)<l?"Yes":"No")<<'\n';
}
return 0;
}
Details
Pretests
Pretest #1:
score: 5
Accepted
time: 19ms
memory: 268632kb
Pretest #2:
score: 5
Accepted
time: 28ms
memory: 268664kb
Pretest #3:
score: 5
Accepted
time: 27ms
memory: 268328kb
Pretest #4:
score: 5
Accepted
time: 39ms
memory: 267616kb
Pretest #5:
score: 5
Accepted
time: 40ms
memory: 268048kb
Pretest #6:
score: 5
Accepted
time: 23ms
memory: 267924kb
Pretest #7:
score: 5
Accepted
time: 24ms
memory: 270276kb
Pretest #8:
score: 5
Accepted
time: 24ms
memory: 269148kb
Pretest #9:
score: 5
Accepted
time: 48ms
memory: 270284kb
Pretest #10:
score: 5
Accepted
time: 47ms
memory: 270928kb
Pretest #11:
score: 5
Accepted
time: 828ms
memory: 285124kb
Pretest #12:
score: 5
Accepted
time: 797ms
memory: 284124kb
Pretest #13:
score: 5
Accepted
time: 32ms
memory: 272992kb
Pretest #14:
score: 5
Accepted
time: 35ms
memory: 273708kb
Pretest #15:
score: 5
Accepted
time: 141ms
memory: 273304kb
Pretest #16:
score: 5
Accepted
time: 145ms
memory: 273188kb
Pretest #17:
score: 5
Accepted
time: 99ms
memory: 279696kb
Pretest #18:
score: 5
Accepted
time: 100ms
memory: 279852kb
Pretest #19:
score: 5
Accepted
time: 821ms
memory: 296048kb
Pretest #20:
score: 5
Accepted
time: 817ms
memory: 310764kb
Final Tests
Test #1:
score: 5
Accepted
time: 38ms
memory: 267560kb
Test #2:
score: 5
Accepted
time: 37ms
memory: 268924kb
Test #3:
score: 5
Accepted
time: 27ms
memory: 268508kb
Test #4:
score: 5
Accepted
time: 37ms
memory: 268496kb
Test #5:
score: 5
Accepted
time: 27ms
memory: 267936kb
Test #6:
score: 5
Accepted
time: 30ms
memory: 269320kb
Test #7:
score: 5
Accepted
time: 27ms
memory: 269540kb
Test #8:
score: 5
Accepted
time: 31ms
memory: 272280kb
Test #9:
score: 5
Accepted
time: 44ms
memory: 270388kb
Test #10:
score: 5
Accepted
time: 50ms
memory: 270588kb
Test #11:
score: 5
Accepted
time: 824ms
memory: 285108kb
Test #12:
score: 5
Accepted
time: 802ms
memory: 283952kb
Test #13:
score: 5
Accepted
time: 32ms
memory: 273580kb
Test #14:
score: 5
Accepted
time: 32ms
memory: 272420kb
Test #15:
score: 5
Accepted
time: 135ms
memory: 273032kb
Test #16:
score: 5
Accepted
time: 124ms
memory: 273356kb
Test #17:
score: 5
Accepted
time: 99ms
memory: 276036kb
Test #18:
score: 5
Accepted
time: 91ms
memory: 282548kb
Test #19:
score: 5
Accepted
time: 804ms
memory: 294488kb
Test #20:
score: 5
Accepted
time: 831ms
memory: 310956kb
Extra Test:
score: 0
Extra Test Passed