QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#498637#9155. 集合CuFeO4100 ✓367ms65552kbC++141.6kb2024-07-30 17:03:572024-07-30 17:03:58

Judging History

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

  • [2024-07-30 17:03:58]
  • 评测
  • 测评结果:100
  • 用时:367ms
  • 内存:65552kb
  • [2024-07-30 17:03:57]
  • 提交

answer

#include<bits/stdc++.h>
#include<bits/extc++.h>
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;
using namespace std;
#define infile(x) freopen(x,"r",stdin)
#define outfile(x) freopen(x,"w",stdout)
#define errfile(x) freopen(x,"w",stderr)
#ifdef LOCAL
    FILE *InFile = infile("in.in"),*OutFile = outfile("out.out");
    // FILE *ErrFile=errfile("err.err");
#else
    FILE *Infile = stdin,*OutFile = stdout;
    //FILE *ErrFile = stderr;
#endif
bool StdIn = cin.tie(nullptr)->sync_with_stdio(false);
bool StdOut = cout.tie(nullptr)->sync_with_stdio(false);
using ll=long long;using ull=unsigned long long;
using db = double;using ldb = long double;
const int N = 6e5 + 10;
int n,m,q;
int a[N][4],b[N][4],tot,p[N];
ull A[N],B[N],rd[N];
mt19937_64 rnd(time(NULL));
unordered_map<ull,int> cnt;
inline void insert(ull x,int opt){
    if(cnt[x] != 0) tot--;
    if((cnt[x]+=opt)!=0) tot++;
}
inline void work(int i){
    for(int j = 1;j <= 3; ++j){
        insert(A[a[i][j]],-1),A[a[i][j]]^=rd[i],insert(A[a[i][j]],1);
        insert(B[b[i][j]],1),B[b[i][j]]^=rd[i],insert(B[b[i][j]],-1); 
    }
}
signed main(){
    cin>>n>>m>>q;
    for(int i = 1;i <= n; ++i) for(int j = 1;j <= 3; ++j) cin>>a[i][j];
    for(int i = 1;i <= n; ++i) for(int j = 1;j <= 3; ++j) cin>>b[i][j];
    for(int i = 1;i <= n; ++i) rd[i] = rnd();
    for(int l = 1,r = 0;l <= n; ++l){
        while(r <= n && tot == 0) work(++r);
        p[l] = r;
        work(l);
    }
    while(q--){
        int l,r;cin>>l>>r;
        cout<<(p[l]>r?"Yes\n":"No\n");
    }
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 268ms
memory: 64772kb

Pretest #12:

score: 5
Accepted
time: 260ms
memory: 62488kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 102ms
memory: 10256kb

Pretest #16:

score: 5
Accepted
time: 90ms
memory: 12352kb

Pretest #17:

score: 5
Accepted
time: 18ms
memory: 14204kb

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 367ms
memory: 61608kb

Pretest #20:

score: 5
Accepted
time: 361ms
memory: 64840kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 259ms
memory: 61052kb

Test #12:

score: 5
Accepted
time: 242ms
memory: 59952kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 97ms
memory: 10252kb

Test #16:

score: 5
Accepted
time: 102ms
memory: 10512kb

Test #17:

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

Test #18:

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

Test #19:

score: 5
Accepted
time: 363ms
memory: 61276kb

Test #20:

score: 5
Accepted
time: 361ms
memory: 65552kb

Extra Test:

score: 0
Extra Test Passed