QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#535542#9155. 集合lyx123886a123886#100 ✓589ms58784kbC++142.1kb2024-08-28 09:36:002024-08-28 09:36:02

Judging History

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

  • [2024-08-28 09:36:02]
  • 评测
  • 测评结果:100
  • 用时:589ms
  • 内存:58784kb
  • [2024-08-28 09:36:00]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define LOCAL 0
#define open_file if(LOCAL) {freopen("set.in","r",stdin);freopen("set.out","w",stdout);}
// using LL=__int128;
using LL=unsigned long long;
mt19937_64 rd(304);
LL rng() {
    LL hi=rd();if(hi<0) hi*=-1;hi<<=60;
    LL lo=rd();if(lo<0) lo*=-1;
    return hi^lo;
}
const int MAXN=2e5+50;
const int MAXM=6e5+50;
array<int,3> P[MAXN],Q[MAXN];LL hbs[MAXN];
LL hval0[MAXM],hval1[MAXM];

namespace c_wr {
    // map<LL,int> ma;
    unordered_map<LL,int> ma;
    int count_wrong=0;  
    void upd(LL val,int type) {
        // auto it=ma.find(val);
        int curv=ma[val];
        if(curv) count_wrong--;
        if(curv+type) count_wrong++;
        ma[val]+=type;
    }
    bool test() {
        return !count_wrong;
    }
};
int L,R;//[L,R)
namespace shift {
    void r_shift() {
        R++;
        for(auto pos:P[R]) {
            c_wr::upd(hval0[pos],-1);
            hval0[pos]^=hbs[R];
            c_wr::upd(hval0[pos],1);
        } 
        for(auto pos:Q[R]) {
            c_wr::upd(hval1[pos],1);
            hval1[pos]^=hbs[R];
            c_wr::upd(hval1[pos],-1);
        }
    }
    void l_shift() {
        for(auto pos:P[L]) {
            c_wr::upd(hval0[pos],-1);
            hval0[pos]^=hbs[L];
            c_wr::upd(hval0[pos],1);
        } 
        for(auto pos:Q[L]) {
            c_wr::upd(hval1[pos],1);
            hval1[pos]^=hbs[L];
            c_wr::upd(hval1[pos],-1);
        }
        L++;
    }
};
using shift::l_shift;
using shift::r_shift;

int rpos[MAXN];
void sol() {
    int n,m,q;scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;++i) hbs[i]=rng();
    for(int i=1;i<=n;++i) {
        scanf("%d%d%d",&P[i][0],&P[i][1],&P[i][2]);
    }
    for(int i=1;i<=n;++i) {
        scanf("%d%d%d",&Q[i][0],&Q[i][1],&Q[i][2]);
    }
    // R=0;
    for(L=1,R=0;L<=n;l_shift()) {
        while(R<=n&&c_wr::test()) r_shift();
        rpos[L]=R-1;
    }
    for(;q;q--) {
        int l,r;scanf("%d%d",&l,&r);
        puts((r<=rpos[l])?"Yes":"No");
    }
}

int main() {
    open_file 
    sol() ;
    return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

score: 5
Accepted
time: 2ms
memory: 10104kb

Pretest #4:

score: 5
Accepted
time: 2ms
memory: 11876kb

Pretest #5:

score: 5
Accepted
time: 2ms
memory: 9868kb

Pretest #6:

score: 5
Accepted
time: 1ms
memory: 7828kb

Pretest #7:

score: 5
Accepted
time: 2ms
memory: 10128kb

Pretest #8:

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

Pretest #9:

score: 5
Accepted
time: 17ms
memory: 7824kb

Pretest #10:

score: 5
Accepted
time: 17ms
memory: 8048kb

Pretest #11:

score: 5
Accepted
time: 518ms
memory: 58748kb

Pretest #12:

score: 5
Accepted
time: 479ms
memory: 56448kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

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

Pretest #16:

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

Pretest #17:

score: 5
Accepted
time: 25ms
memory: 14072kb

Pretest #18:

score: 5
Accepted
time: 20ms
memory: 15268kb

Pretest #19:

score: 5
Accepted
time: 589ms
memory: 57164kb

Pretest #20:

score: 5
Accepted
time: 589ms
memory: 58780kb

Final Tests

Test #1:

score: 5
Accepted
time: 1ms
memory: 7812kb

Test #2:

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

Test #3:

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

Test #4:

score: 5
Accepted
time: 1ms
memory: 8056kb

Test #5:

score: 5
Accepted
time: 1ms
memory: 9808kb

Test #6:

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

Test #7:

score: 5
Accepted
time: 2ms
memory: 12172kb

Test #8:

score: 5
Accepted
time: 1ms
memory: 7792kb

Test #9:

score: 5
Accepted
time: 17ms
memory: 7824kb

Test #10:

score: 5
Accepted
time: 21ms
memory: 11904kb

Test #11:

score: 5
Accepted
time: 469ms
memory: 56680kb

Test #12:

score: 5
Accepted
time: 395ms
memory: 54360kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 103ms
memory: 12532kb

Test #16:

score: 5
Accepted
time: 108ms
memory: 12328kb

Test #17:

score: 5
Accepted
time: 16ms
memory: 14116kb

Test #18:

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

Test #19:

score: 5
Accepted
time: 492ms
memory: 53716kb

Test #20:

score: 5
Accepted
time: 486ms
memory: 58784kb

Extra Test:

score: 0
Extra Test Passed