QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#552330#9155. 集合Coder-Osman100 ✓388ms60388kbC++142.4kb2024-09-07 22:04:202024-09-07 22:04:21

Judging History

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

  • [2024-09-07 22:04:21]
  • 评测
  • 测评结果:100
  • 用时:388ms
  • 内存:60388kb
  • [2024-09-07 22:04:20]
  • 提交

answer

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <unordered_map>
#include <random>
#include <cstdlib>
#define int long long
#define ull unsigned int
#define endl '\n'
#define lson 2*i
#define rson 2*i+1
#define debug(x) cerr << #x << " = " <<  x << "\n";
#define debug2(l,r) cerr << "[" #l "," #r "] = [" << l << "," << r << "]\n";
#define debug3(x,y,z) cerr << "{" #x "," #y "," #z "} = " << "{" << x << "," << y << "," << z << "}\n";
#define debugv(v) cerr << #v": size= " << v.size() << "\nelement: " ; for(auto p:v)  cerr << p << " ";
using namespace std;
const int N = 2e5 + 55, M = 6e5 + 55, Q = 1e6 + 55, MOD = 1e9 + 7, INF = 1e18;
int n, m, q, a[N][4], b[N][4];
ull c[M], d[M], ar[N], br[N];
bool ans[Q];
bool func(int x) {
    ull ha = 0, hb = 0;
    for (int i = 1; i <= 3; i++) {
        int t = a[x][i];
        ha -= c[t];
        c[t] ^= ar[x];
        ha += c[t];
    }
    for (int i = 1; i <= 3; i++) {
        int t = b[x][i];
        hb -= d[t];
        d[t] ^= ar[x];
        hb += d[t];
    }
    if (ha == hb) return true;
    for (int i = 1; i <= 3; i++)
        c[a[x][i]] ^= ar[x];
    for (int i = 1; i <= 3; i++)
        d[b[x][i]] ^= ar[x];
    return false;
}
void Delete(int x) {
   for (int i = 1; i <= 3; i++)
        c[a[x][i]] ^= ar[x];
    for (int i = 1; i <= 3; i++)
        d[b[x][i]] ^= ar[x];
}
mt19937_64 rd(random_device{}());
struct node {
    int x, i;
};
vector<node> g[N];
signed main() {
	cin.tie(0), ios_base::sync_with_stdio(false);
	cin >> n >> m >> q;
	for (int i = 1; i <= n; i++)
        ar[i] = rd();
	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, l, r; i <= q; i++) {
        cin >> l >> r;
        g[l].push_back({r, i});
    }
    for (int i = 1, j = 0; i <= n; i++) {
        while (j < n) {
            if (func(j + 1)) j++;
            else break;
        }
        for (int k = 0; k < g[i].size(); k++) {
            int x = g[i][k].x;
            ans[g[i][k].i] = x <= j;
        }
        Delete(i);
    }
    for (int i = 1; i <= q; i++) {
        if (ans[i]) cout << "Yes" << endl;
        else cout << "No" << endl;
    }
	return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 98ms
memory: 29320kb

Pretest #12:

score: 5
Accepted
time: 98ms
memory: 31412kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 131ms
memory: 38608kb

Pretest #16:

score: 5
Accepted
time: 126ms
memory: 38820kb

Pretest #17:

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

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 383ms
memory: 54156kb

Pretest #20:

score: 5
Accepted
time: 350ms
memory: 60024kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

score: 5
Accepted
time: 22ms
memory: 20068kb

Test #10:

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

Test #11:

score: 5
Accepted
time: 93ms
memory: 31632kb

Test #12:

score: 5
Accepted
time: 95ms
memory: 29328kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 123ms
memory: 37204kb

Test #16:

score: 5
Accepted
time: 114ms
memory: 38436kb

Test #17:

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

Test #18:

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

Test #19:

score: 5
Accepted
time: 326ms
memory: 52024kb

Test #20:

score: 5
Accepted
time: 388ms
memory: 60388kb

Extra Test:

score: 0
Extra Test Passed