QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#497382#9155. 集合tosivan100 ✓1317ms188924kbC++144.0kb2024-07-29 03:47:542024-07-29 03:47:54

Judging History

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

  • [2024-07-29 03:47:54]
  • 评测
  • 测评结果:100
  • 用时:1317ms
  • 内存:188924kb
  • [2024-07-29 03:47:54]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll a[200005][3],b[200005][3];
ll lasta[600005],lastb[600005];
ll theleft[600005];
bool exista[600005],existb[600005],exist[600005];
map<ll,vector<pair<ll,ll> > >mp,mp2;
map<ll,vector<pair<ll,ll> > >rng[600005];

void reconstruct(ll x, ll it, ll cur){
    // cout<<"hi\n";
   vector<pair<ll,ll> >bruh;
    for(auto& u: mp[x]){
        if(u.first!=it)bruh.push_back(u);
        else{
            rng[x][u.first].push_back({u.second,cur-1});
            // cout<<x<<" "<<u.first<<' '<<u.second<<' '<<cur-1<<'\n';
        }
    }
    mp[x].swap(bruh);
}
void reconstruct2(ll x, ll it){
    // cout<<"hi\n";
    vector<pair<ll,ll> >bruh;
    for(auto& u: mp2[x]){
        if(u.first!=it)bruh.push_back(u);
    }
    mp2[x].swap(bruh);
}

void kill(ll id){
    for(int i=0;i<3;i++){
        exista[a[id][i]]=1,existb[b[id][i]]=1;
    }
    for(int i=0;i<3;i++){
        vector<ll>bb;
        for(auto& [u,lef]: mp[a[id][i]]){
            if(!existb[u])bb.push_back(u);
        }
        for(auto& u: bb){
            reconstruct(a[id][i],u,id),reconstruct2(u,a[id][i]);
        }
    }
    for(int i=0;i<3;i++){
        vector<ll>bb;
        for(auto& [u,lef]: mp2[b[id][i]]){
            if(!exista[u])bb.push_back(u);
        }
        for(auto& u: bb){
            reconstruct(u,b[id][i],id),reconstruct2(b[id][i],u);
        }
    }
    for(int i=0;i<3;i++){
        exista[a[id][i]]=0,existb[b[id][i]]=0;
    }
    for(int i=0;i<3;i++){
        for(auto& [u,lef]: mp[a[id][i]])exist[u]=1;
        for(int j=0;j<3;j++){
            if(!exist[b[id][j]]){mp[a[id][i]].push_back({b[id][j],max(lasta[a[id][i]],lastb[b[id][j]])+1});}
        }
        for(auto& [u,lef]: mp[a[id][i]])exist[u]=0;
    }
    for(int i=0;i<3;i++){
        for(auto& [u,lef]: mp2[b[id][i]])exist[u]=1;
        for(int j=0;j<3;j++){
            if(!exist[a[id][j]]){mp2[b[id][i]].push_back({a[id][j],max(lasta[a[id][j]],lastb[b[id][i]])+1});}
        }
        for(auto& [u,lef]: mp2[b[id][i]])exist[u]=0;
    }
}

bool test(ll id1, ll id2, ll lef, ll righ){
    if(rng[id1][id2].size()==0)return 0;
    // cout<<"nigger\n";
    if(rng[id1][id2][0].first>lef)return 0;
    ll l=0,r=rng[id1][id2].size()-1;
    while(l<r){
        ll mid=(l+r+1)>>1;
        if(rng[id1][id2][mid].first<=lef){
            l=mid;
        }
        else{
            r=mid-1;
        }
    }
    if(rng[id1][id2][l].second>=righ)return 1;
    return 0;
}
bool ok(vector<ll>v, ll l, ll r){
    for(int i=0;i<3;i++){
        if(!test(v[i],b[r][i],l,r))return 0;
    }
    return 1;
}
bool tameshi(ll l, ll r){
    vector<ll>v;
    for(int i=0;i<3;i++)v.push_back(a[r][i]);
    sort(v.begin(),v.end());
    if(ok(v,l,r))return 1;
    while(next_permutation(v.begin(),v.end())){
        if(ok(v,l,r))return 1;
    }
    return 0;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0); 
    for(int i=0;i<2;i++){
        for(int j=0;j<600005;j++){
            exist[j]=0;
        }
    }
    ll n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++){
        lasta[i]=0,lastb[i]=0;
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<3;j++){
            cin>>a[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<3;j++){
            cin>>b[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        kill(i);
        for(int j=0;j<3;j++){
            lasta[a[i][j]]=i,lastb[b[i][j]]=i;
        }
    }
    for(int i=1;i<=m;i++){
        for(auto& [u,lef]: mp[i]){
            rng[i][u].push_back({lef,n});
            // cout<<i<<" "<<u<<" "<<lef<<" "<<n<<" "<<'\n';
        }
    }
    ll leftest[n+5];
    leftest[1]=1;
    ll ptr=1;
    for(int i=2;i<=n;i++){
       while(!tameshi(ptr,i))ptr++;
        leftest[i]=ptr;
    }
    while(q--){
        ll l,r;
        cin>>l>>r;
        if(leftest[r]>l)cout<<"No\n";
        else cout<<"Yes\n";
    }
}

Details


Pretests

Pretest #1:

score: 5
Accepted
time: 0ms
memory: 42872kb

Pretest #2:

score: 5
Accepted
time: 0ms
memory: 41944kb

Pretest #3:

score: 5
Accepted
time: 0ms
memory: 41868kb

Pretest #4:

score: 5
Accepted
time: 0ms
memory: 42564kb

Pretest #5:

score: 5
Accepted
time: 3ms
memory: 41356kb

Pretest #6:

score: 5
Accepted
time: 0ms
memory: 41684kb

Pretest #7:

score: 5
Accepted
time: 3ms
memory: 42036kb

Pretest #8:

score: 5
Accepted
time: 0ms
memory: 42096kb

Pretest #9:

score: 5
Accepted
time: 19ms
memory: 41352kb

Pretest #10:

score: 5
Accepted
time: 24ms
memory: 41892kb

Pretest #11:

score: 5
Accepted
time: 461ms
memory: 59392kb

Pretest #12:

score: 5
Accepted
time: 517ms
memory: 64428kb

Pretest #13:

score: 5
Accepted
time: 7ms
memory: 41876kb

Pretest #14:

score: 5
Accepted
time: 14ms
memory: 43644kb

Pretest #15:

score: 5
Accepted
time: 112ms
memory: 42592kb

Pretest #16:

score: 5
Accepted
time: 107ms
memory: 42520kb

Pretest #17:

score: 5
Accepted
time: 79ms
memory: 46760kb

Pretest #18:

score: 5
Accepted
time: 89ms
memory: 59096kb

Pretest #19:

score: 5
Accepted
time: 1073ms
memory: 89688kb

Pretest #20:

score: 5
Accepted
time: 1292ms
memory: 188248kb

Final Tests

Test #1:

score: 5
Accepted
time: 4ms
memory: 42324kb

Test #2:

score: 5
Accepted
time: 0ms
memory: 41780kb

Test #3:

score: 5
Accepted
time: 0ms
memory: 42096kb

Test #4:

score: 5
Accepted
time: 4ms
memory: 42156kb

Test #5:

score: 5
Accepted
time: 0ms
memory: 41412kb

Test #6:

score: 5
Accepted
time: 3ms
memory: 41460kb

Test #7:

score: 5
Accepted
time: 0ms
memory: 42172kb

Test #8:

score: 5
Accepted
time: 0ms
memory: 41640kb

Test #9:

score: 5
Accepted
time: 23ms
memory: 43164kb

Test #10:

score: 5
Accepted
time: 24ms
memory: 42072kb

Test #11:

score: 5
Accepted
time: 451ms
memory: 59596kb

Test #12:

score: 5
Accepted
time: 542ms
memory: 64008kb

Test #13:

score: 5
Accepted
time: 11ms
memory: 41632kb

Test #14:

score: 5
Accepted
time: 8ms
memory: 44060kb

Test #15:

score: 5
Accepted
time: 106ms
memory: 42200kb

Test #16:

score: 5
Accepted
time: 110ms
memory: 43288kb

Test #17:

score: 5
Accepted
time: 76ms
memory: 48732kb

Test #18:

score: 5
Accepted
time: 88ms
memory: 58080kb

Test #19:

score: 5
Accepted
time: 1065ms
memory: 86564kb

Test #20:

score: 5
Accepted
time: 1317ms
memory: 188924kb

Extra Test:

score: 0
Extra Test Passed