QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#693886#9155. 集合Qwerty1232100 ✓401ms190972kbC++233.5kb2024-10-31 16:55:062024-10-31 16:55:10

Judging History

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

  • [2024-10-31 16:55:10]
  • 评测
  • 测评结果:100
  • 用时:401ms
  • 内存:190972kb
  • [2024-10-31 16:55:06]
  • 提交

answer

// https://admin.contest.yandex.ru/submissions/123152263
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <bitset>
#include <iterator>
#include <iomanip>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <random>
#include <cassert>

using namespace std;

#define int long long
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

typedef long long ll;
typedef long double ld;

struct SparseTable {
    vector<int> a;
    vector<vector<int>> spmin;

    SparseTable() {}
    
    void build(vector<int> c) {
        a = c;
        int n = a.size();
        int log2n = log2(n) + 1;
        spmin.resize(log2n, vector<int>(n));
        for (int i = 0; i < n; ++i) spmin[0][i] = i;
        for (int i = 1; i < log2n; ++i) {
            for (int j = 0; j < n; ++j) {
                int t = min(j + (1<<(i-1)), n - 1);
                if (a[spmin[i - 1][j]] < a[spmin[i - 1][t]]) spmin[i][j] = spmin[i - 1][j];
                else spmin[i][j] = spmin[i - 1][t];
            }
        }
    }

    int min_ind(int l, int r) {
        int lg2 = log2(r - l + 1);
        r++;
        if (a[spmin[lg2][l]] < a[spmin[lg2][r - (1<<lg2)]]) return spmin[lg2][l];
        return spmin[lg2][r - (1<<lg2)];
    }

    int get_min(int l, int r) {
        int lg2 = log2(r - l + 1);
        r++;
        if (a[spmin[lg2][l]] < a[spmin[lg2][r - (1<<lg2)]]) return a[spmin[lg2][l]];
        return a[spmin[lg2][r - (1<<lg2)]];
    }
};

void solve() {
    int n, m, q;
    cin >> n >> m >> q;
    vector<vector<int>> a(n, vector<int>(3)), b(n, vector<int>(3));
    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];
    vector<int> fucked(n, -1);
    vector<int> lasta(m + 1, n), lastb(m + 1, n);
    vector<map<pair<int, int>, int>> lolkek(n);
    for (int i = n - 1; i >= 0; --i) {
        for (auto e : a[i]) {
            for (auto x : b[i]) {
                if (lasta[e] == lastb[x]) {
                    if (lasta[e] == n) {
                        lolkek[i][{e, x}] = n;
                        continue;
                    }
                    lolkek[i][{e, x}] = lolkek[lasta[e]][{e, x}];
                    continue;
                }
                lolkek[i][{e, x}] = min(lasta[e], lastb[x]);
            }
        }
        for (auto e : a[i]) lasta[e] = i;
        for (auto e : b[i]) lastb[e] = i;
        vector<int> ord = {0, 1, 2};
        do {
            int X = n;
            for (int j = 0; j < 3; ++j) {
                X = min(X, lolkek[i][{a[i][j], b[i][ord[j]]}]);
            }
            fucked[i] = max(fucked[i], X);
        } while (next_permutation(all(ord)));
    }
    // for (auto e : fucked) cout << e << ' '; cout << '\n';
    SparseTable lol;
    lol.build(fucked);
    for (int i = 0; i < q; ++i) {
        int l, r;
        cin >> l >> r;
        --l;
        if (lol.get_min(l, r - 1) >= r) cout << "Yes\n";
        else cout << "No\n";
    }
}

signed main() {
    int tc = 1;
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#else
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
#endif
    // cin >> tc;
    for (int t = 1; t <= tc; t++) {
        // cout << "Case #" << t  << ": ";
        solve();
    }
}

Details


Pretests

Pretest #1:

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

Pretest #2:

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

Pretest #3:

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

Pretest #4:

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

Pretest #5:

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

Pretest #6:

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

Pretest #7:

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

Pretest #8:

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

Pretest #9:

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

Pretest #10:

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

Pretest #11:

score: 5
Accepted
time: 218ms
memory: 181660kb

Pretest #12:

score: 5
Accepted
time: 206ms
memory: 181416kb

Pretest #13:

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

Pretest #14:

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

Pretest #15:

score: 5
Accepted
time: 125ms
memory: 5412kb

Pretest #16:

score: 5
Accepted
time: 129ms
memory: 5384kb

Pretest #17:

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

Pretest #18:

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

Pretest #19:

score: 5
Accepted
time: 397ms
memory: 181480kb

Pretest #20:

score: 5
Accepted
time: 399ms
memory: 190912kb

Final Tests

Test #1:

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

Test #2:

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

Test #3:

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

Test #4:

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

Test #5:

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

Test #6:

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

Test #7:

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

Test #8:

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

Test #9:

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

Test #10:

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

Test #11:

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

Test #12:

score: 5
Accepted
time: 215ms
memory: 181352kb

Test #13:

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

Test #14:

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

Test #15:

score: 5
Accepted
time: 116ms
memory: 5396kb

Test #16:

score: 5
Accepted
time: 121ms
memory: 5328kb

Test #17:

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

Test #18:

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

Test #19:

score: 5
Accepted
time: 374ms
memory: 181476kb

Test #20:

score: 5
Accepted
time: 401ms
memory: 190972kb

Extra Test:

score: 0
Extra Test Passed