QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#491931#9155. 集合5toubun_no_hanayome#100 ✓191ms31316kbC++144.0kb2024-07-26 01:27:212024-07-26 01:27:22

Judging History

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

  • [2024-07-26 01:27:22]
  • 评测
  • 测评结果:100
  • 用时:191ms
  • 内存:31316kb
  • [2024-07-26 01:27:21]
  • 提交

answer

#include<bits/stdc++.h>
#define rep(i, a, b) for(int i = (a);i <= (b);++i)
#define per(i, a, b) for(int i = (a);i >= (b);--i)
#define lc (k << 1)
#define rc (k << 1 | 1)
#define lowbit(x) ((x) & -(x))
#define odd(x) ((x) & 1)
#define even(x) (!odd(x))
#define fir first
#define sec second
#define pb push_back
#define il inline
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define i128 __int128
#define f128 __float128
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define SZ(x) ((int)(x).size())
#define debug(x) cerr << "In Line " << __LINE__ << " the " << #x << " = " << (x) << "\n"
using namespace std;
using ll = long long;
using ull = unsigned long long;
template<class T> using vc = vector<T>;
template<class Tx, class Ty>
il void chkmx(Tx& x, const Ty y) {x = max<common_type_t<Tx, Ty>>(x, y);}
template<class Tx, class Ty>
il void chkmn(Tx& x, const Ty y) {x = min<common_type_t<Tx, Ty>>(x, y);}
const int inf = 0x3f3f3f3f;
const ll llinf = 0x3f3f3f3f3f3f3f3fll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
bool ms;

const int N = 2e5 + 5, M = 6e5 + 5;
int a[N][3], b[N][3];
ull pos1[M][2], pos2[M][2];
ull w[N][2], s[2], t[2];
int f[N];

bool mt;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);
    cerr << fabs(&ms - &mt) / 1024 / 1024 << "\n";
    int n, m, q;
    cin >> n >> m >> q;
    rep(i, 1, n)
        w[i][0] = rnd() % 998244353, w[i][1] = rnd() % 998244353;
    rep(i, 1, n)
        cin >> a[i][0] >> a[i][1] >> a[i][2];
    rep(i, 1, n)
        cin >> b[i][0] >> b[i][1] >> b[i][2];
    for(int l = 1, r = 1;l <= n;++l) {
        while(r <= n && s[0] == t[0] && s[1] == t[1]) {
            rep(i, 0, 2) {
                s[0] -= pos1[a[r][i]][0];
                s[1] -= pos1[a[r][i]][1];
                t[0] -= pos2[b[r][i]][0];
                t[1] -= pos2[b[r][i]][1];
            }
            rep(i, 0, 2) {
                pos1[a[r][i]][0] ^= w[r][0];
                pos1[a[r][i]][1] ^= w[r][1];
                pos2[b[r][i]][0] ^= w[r][0];
                pos2[b[r][i]][1] ^= w[r][1];
            }
            rep(i, 0, 2) {
                s[0] += pos1[a[r][i]][0];
                s[1] += pos1[a[r][i]][1];
                t[0] += pos2[b[r][i]][0];
                t[1] += pos2[b[r][i]][1];
            }
            if(s[0] == t[0] && s[1] == t[1])
                ++r;
            else {
                rep(i, 0, 2) {
                    s[0] -= pos1[a[r][i]][0];
                    s[1] -= pos1[a[r][i]][1];
                    t[0] -= pos2[b[r][i]][0];
                    t[1] -= pos2[b[r][i]][1];
                }
                rep(i, 0, 2) {
                    pos1[a[r][i]][0] ^= w[r][0];
                    pos1[a[r][i]][1] ^= w[r][1];
                    pos2[b[r][i]][0] ^= w[r][0];
                    pos2[b[r][i]][1] ^= w[r][1];
                }
                rep(i, 0, 2) {
                    s[0] += pos1[a[r][i]][0];
                    s[1] += pos1[a[r][i]][1];
                    t[0] += pos2[b[r][i]][0];
                    t[1] += pos2[b[r][i]][1];
                }
                break;
            }
        }
        f[l] = r;
        rep(i, 0, 2) {
            s[0] -= pos1[a[l][i]][0];
            s[1] -= pos1[a[l][i]][1];
            t[0] -= pos2[b[l][i]][0];
            t[1] -= pos2[b[l][i]][1];
        }
        rep(i, 0, 2) {
            pos1[a[l][i]][0] ^= w[l][0];
            pos1[a[l][i]][1] ^= w[l][1];
            pos2[b[l][i]][0] ^= w[l][0];
            pos2[b[l][i]][1] ^= w[l][1];
        }
        rep(i, 0, 2) {
            s[0] += pos1[a[l][i]][0];
            s[1] += pos1[a[l][i]][1];
            t[0] += pos2[b[l][i]][0];
            t[1] += pos2[b[l][i]][1];
        }
    }
    while(q--) {
        int l, r;
        cin >> l >> r;
        if(r < f[l])
            cout << "Yes\n";
        else
            cout << "No\n";
    }
    cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
    return 0;
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 69ms
memory: 14924kb

Pretest #12:

score: 5
Accepted
time: 63ms
memory: 14716kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 100ms
memory: 8104kb

Pretest #16:

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

Pretest #17:

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

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 175ms
memory: 14744kb

Pretest #20:

score: 5
Accepted
time: 191ms
memory: 31316kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

score: 5
Accepted
time: 60ms
memory: 14924kb

Test #12:

score: 5
Accepted
time: 59ms
memory: 14904kb

Test #13:

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

Test #14:

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

Test #15:

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

Test #16:

score: 5
Accepted
time: 104ms
memory: 8288kb

Test #17:

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

Test #18:

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

Test #19:

score: 5
Accepted
time: 164ms
memory: 14744kb

Test #20:

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

Extra Test:

score: 0
Extra Test Passed