QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#492164#9155. 集合zwh2008#100 ✓831ms310956kbC++142.2kb2024-07-26 10:02:452024-07-26 10:02:45

Judging History

你现在查看的是最新测评结果

  • [2024-07-26 10:02:45]
  • 评测
  • 测评结果:100
  • 用时:831ms
  • 内存:310956kb
  • [2024-07-26 10:02:45]
  • 提交

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