QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#488510#9155. 集合huangzirui100 ✓1678ms426548kbC++143.0kb2024-07-24 08:57:542024-07-24 08:57:55

Judging History

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

  • [2024-07-24 08:57:55]
  • 评测
  • 测评结果:100
  • 用时:1678ms
  • 内存:426548kb
  • [2024-07-24 08:57:54]
  • 提交

answer

#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
using namespace std;
const int maxn=600010;
int i,j,k,n,m,q;
int Ans[maxn];
int A[maxn][3],B[maxn][3];
int Num=0;
bool check(){
    return Num==0;
}
unordered_map<ll,int>M;int cnt=0;
unordered_map<int,int>mS[2400010];
map<ll,int>id3,mp3;
multiset<int>S[2400010];int occ[maxn],tp[maxn];
bool isok(int id){
    if(!occ[id])return true;
    int num=tp[id];
    for(auto x:S[id]){
        if(-x==occ[id])--num;
        else break;
        if(num<=0)return true;
    }
    return false;
}
void EraseSet(int id,int id2){
    Num-=!isok(id);occ[id]--;
    for(int i=0;i<3;i++){
        int w=B[id2][i];
        S[id].erase(S[id].lower_bound(-mS[id][w]));
        mS[id][w]--;if(mS[id][w])S[id].insert(-mS[id][w]);
    }
    Num+=!isok(id);
}
void InsertSet(int id,int id2){
    Num-=!isok(id);occ[id]++;
    for(int i=0;i<3;i++){
        int w=B[id2][i];
        if(mS[id][w])S[id].erase(S[id].lower_bound(-mS[id][w]));
        mS[id][w]++;S[id].insert(-mS[id][w]);
    }
    Num+=!isok(id);
}
int getVal(int op,int id){
    if(op==0)return 1ll*A[id][0]*m*m+1ll*A[id][1]*m+A[id][2];
    if(op==1)return 1ll*B[id][0]*m*m+1ll*B[id][1]*m+B[id][2];
    assert(0);
}
void Erase(int id){
    for(int i=0;i<3;i++)
        for(int j=i;j<3;j++){
            ll sum=0;
            for(int k=0;k<3;k++)
                if(k==i || k==j)
                    sum=sum*(m+1)+A[id][k];
            if(!M[sum])assert(0);
            int tid=M[sum];
            EraseSet(tid,id);
        }
}
void Insert(int id){
    for(int i=0;i<3;i++)
        for(int j=i;j<3;j++){
            ll sum=0;
            for(int k=0;k<3;k++)
                if(k==i || k==j)
                    sum=sum*(m+1)+A[id][k];
            if(!M[sum]){
                M[sum]=++cnt;
                tp[cnt]=1+(i!=j);
            }
            int tid=M[sum];
            InsertSet(tid,id);
        }
}
void solve(){
    M.clear();
    map<ll,int>Mp;
    for(int i=1;i<=n;i++){
        ll val=getVal(0,i);
        if(Mp[val]){
            if(getVal(1,i)!=getVal(1,Mp[val]))
                Ans[Mp[val]]=min(Ans[Mp[val]],i-1);
        }Mp[val]=i;
    }
    for(int i=n-1;i>=1;i--)Ans[i]=min(Ans[i],Ans[i+1]);
    int L=n;
    for(int R=n;R>=1;R--){
        Insert(R);
        while(!check())Erase(L--);
        Ans[R]=min(Ans[R],L);
    }
    while(L)Erase(L--);
}
void getAns(){
    for(int i=1;i<=q;i++){
        int l,r;
        scanf("%d%d",&l,&r);
        if(Ans[l]>=r)puts("Yes");
        else puts("No");
    }
}
int main(){
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)Ans[i]=n;
    for(int i=1;i<=n;i++){
        for(int j=0;j<3;j++)
            scanf("%d",&A[i][j]);
        sort(A[i],A[i]+3);
    }
    for(int i=1;i<=n;i++){
        for(int j=0;j<3;j++)
            scanf("%d",&B[i][j]);
        sort(B[i],B[i]+3);
    }
    solve();
    for(int i=1;i<=n;i++)
        for(int j=0;j<3;j++)
            swap(A[i][j],B[i][j]);
    solve();
    getAns();
}

Details


Pretests

Pretest #1:

score: 5
Accepted
time: 39ms
memory: 249476kb

Pretest #2:

score: 5
Accepted
time: 31ms
memory: 249776kb

Pretest #3:

score: 5
Accepted
time: 39ms
memory: 249496kb

Pretest #4:

score: 5
Accepted
time: 42ms
memory: 249484kb

Pretest #5:

score: 5
Accepted
time: 33ms
memory: 249556kb

Pretest #6:

score: 5
Accepted
time: 28ms
memory: 249484kb

Pretest #7:

score: 5
Accepted
time: 35ms
memory: 249480kb

Pretest #8:

score: 5
Accepted
time: 28ms
memory: 249488kb

Pretest #9:

score: 5
Accepted
time: 54ms
memory: 249476kb

Pretest #10:

score: 5
Accepted
time: 51ms
memory: 249444kb

Pretest #11:

score: 5
Accepted
time: 882ms
memory: 253868kb

Pretest #12:

score: 5
Accepted
time: 913ms
memory: 253208kb

Pretest #13:

score: 5
Accepted
time: 44ms
memory: 249708kb

Pretest #14:

score: 5
Accepted
time: 48ms
memory: 251584kb

Pretest #15:

score: 5
Accepted
time: 153ms
memory: 249744kb

Pretest #16:

score: 5
Accepted
time: 166ms
memory: 251508kb

Pretest #17:

score: 5
Accepted
time: 158ms
memory: 256956kb

Pretest #18:

score: 5
Accepted
time: 152ms
memory: 264164kb

Pretest #19:

score: 5
Accepted
time: 1580ms
memory: 345292kb

Pretest #20:

score: 0
Wrong Answer
time: 1674ms
memory: 426548kb

Final Tests

Test #1:

score: 5
Accepted
time: 32ms
memory: 253636kb

Test #2:

score: 5
Accepted
time: 27ms
memory: 253564kb

Test #3:

score: 5
Accepted
time: 37ms
memory: 253576kb

Test #4:

score: 5
Accepted
time: 31ms
memory: 253536kb

Test #5:

score: 5
Accepted
time: 35ms
memory: 253524kb

Test #6:

score: 5
Accepted
time: 31ms
memory: 253592kb

Test #7:

score: 5
Accepted
time: 43ms
memory: 253556kb

Test #8:

score: 5
Accepted
time: 36ms
memory: 253640kb

Test #9:

score: 5
Accepted
time: 52ms
memory: 253504kb

Test #10:

score: 5
Accepted
time: 42ms
memory: 255616kb

Test #11:

score: 5
Accepted
time: 868ms
memory: 259704kb

Test #12:

score: 5
Accepted
time: 898ms
memory: 259748kb

Test #13:

score: 5
Accepted
time: 35ms
memory: 253812kb

Test #14:

score: 5
Accepted
time: 47ms
memory: 255500kb

Test #15:

score: 5
Accepted
time: 135ms
memory: 254120kb

Test #16:

score: 5
Accepted
time: 161ms
memory: 255164kb

Test #17:

score: 5
Accepted
time: 152ms
memory: 260104kb

Test #18:

score: 5
Accepted
time: 159ms
memory: 269264kb

Test #19:

score: 5
Accepted
time: 1553ms
memory: 336528kb

Test #20:

score: 5
Accepted
time: 1678ms
memory: 426036kb