QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#527389#9155. 集合bribritt100 ✓183ms36828kbC++171.4kb2024-08-22 14:50:162024-08-22 14:50:17

Judging History

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

  • [2024-08-22 14:50:17]
  • 评测
  • 测评结果:100
  • 用时:183ms
  • 内存:36828kb
  • [2024-08-22 14:50:16]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using i128 = __int128;
const int N = 200069;
const int M = 600069;
const int BUC = 600;
#define what(x) cerr<<#x<<" is "<<(x)<<endl
main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m, q;
#ifdef TEST
  n=2e5;m=6e5;q=1e6;
#else
  cin >> n >> m >> q;
#endif
  mt19937_64 rng(12102010);
  vector<i64> val(n);
  for(int i=0;i<n;i++) val[i]=rng();
  vector<vector<int>> A(n,vector<int>(3,0)), B(n,vector<int>(3,0));
#ifdef TEST
  for(int i=0;i<n;i++) {
    A[i][0]=rng()%m;
    A[i][1]=rng()%m;
    A[i][2]=rng()%m;
    B[i][0]=rng()%m;
    B[i][1]=rng()%m;
    B[i][2]=rng()%m;
  }
#else
  for(int i=0;i<n;i++) cin>>A[i][0]>>A[i][1]>>A[i][2];
  for(int i=0;i<n;i++) cin>>B[i][0]>>B[i][1]>>B[i][2];
  for(int i=0;i<n;i++) for(int j=0;j<3;j++) A[i][j]--,B[i][j]--;
#endif
  i64 diff = 0;
  vector<i64> av(m,0), bv(m,0);
  auto toggle = [&val,&A,&B,&av,&bv,&diff](int x) {
    for(int i=0;i<3;++i) {
      diff -= av[A[x][i]];
      diff += (av[A[x][i]]^=val[x]);
      diff += bv[B[x][i]];
      diff -= (bv[B[x][i]]^=val[x]);
    }
  };
  int fst[n];
  for(int i=0,j=0;i<n;i++) {
    toggle(i);
    while(diff) toggle(j++);
    fst[i]=j;
  }
  for(int l,r,i=0;i<q;i++) {
#ifdef TEST
    l=rng()%n, r=rng()%n;
    if(l>r) swap(l,r);
#else
    cin >> l >> r;
    --l; --r;
#endif
    cout << (l<fst[r]?"No\n":"Yes\n");
  }
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 72ms
memory: 27280kb

Pretest #12:

score: 5
Accepted
time: 57ms
memory: 27532kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 99ms
memory: 3892kb

Pretest #16:

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

Pretest #17:

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

Pretest #18:

score: 5
Accepted
time: 5ms
memory: 6484kb

Pretest #19:

score: 5
Accepted
time: 178ms
memory: 27572kb

Pretest #20:

score: 5
Accepted
time: 183ms
memory: 36828kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 68ms
memory: 27404kb

Test #12:

score: 5
Accepted
time: 67ms
memory: 27264kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 105ms
memory: 4056kb

Test #16:

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

Test #17:

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

Test #18:

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

Test #19:

score: 5
Accepted
time: 162ms
memory: 27784kb

Test #20:

score: 5
Accepted
time: 180ms
memory: 36764kb

Extra Test:

score: 0
Extra Test Passed