oj.uz

Submission #773094

# Submission time Handle Problem Language Result Execution time Memory
773094 2023-07-04T15:06:06 Z PixelCat Long Mansion (JOI17_long_mansion) C++14
0 / 100
 270 ms 262144 KB 
/*     code by PixelCat     */
/*         meow owo         */

#include <bits/stdc++.h>
#define int LL  //__int128
#define double long double
using namespace std;
using LL = long long;
// using i128 = __int128_t;
using ull = unsigned long long;
using pii = pair<int, int>;

#define For(i, a, b) for (int i = a; i <= b; i++)
#define Fors(i, a, b, s) for (int i = a; i <= b; i += s)
#define Forr(i, a, b) for (int i = a; i >= b; i--)
#define F first
#define S second

#define eb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define mkp make_pair

#define MOD (int)(998244353)
// #define MOD (int)((LL)1'000'000'007)
#define INF (int)(4e18)
#define EPS (1e-6)

namespace PixelCat {

#ifdef NYAOWO
#include "/home/pixelcat/yodayo/meow/library/debug.hpp"
inline void USACO(const string &s) {
    cerr << "USACO: " << s << "\n";
}

#else
#define debug(...)
inline void timer() {}
inline void USACO(const string &s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

#endif

inline void NYA() {
    ios::sync_with_stdio(false);
    cin.tie(0);
}
inline int gcd(int a, int b) {
    return __gcd(a, b);
}
inline int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}
int fpow(int b, int p, const int &mod = MOD) {
    int ans = 1;
    for (; p; p >>= 1, b = b * b % mod)
        if (p & 1) ans = ans * b % mod;
    return ans;
}
template <typename T>
inline void chmin(T &_a, const T &_b) {
    if (_b < _a) _a = _b;
}
template <typename T>
inline void chmax(T &_a, const T &_b) {
    if (_a < _b) _a = _b;
}
mt19937_64 rng(
    chrono::steady_clock::now().time_since_epoch().count());

} // namespace PixelCat
using namespace PixelCat;

const int MAXN = 500050;

int key[MAXN];
vector<int> pos[MAXN];
pii ans[MAXN];

// check if there's any key of type [k] in range [l, r]
bool check(int l, int r, int k) {
    return lower_bound(all(pos[k]), l) != upper_bound(all(pos[k]), r);
}

struct Ayaya {
    vector<int> start;
    int l, r, sl, sr;
    Ayaya(int s): start(1, s), l(s), r(s), sl(s), sr(s) {}
    int len() { return r - l + 1; }
    bool inside(int x) { return l <= x && x <= r; }
    void dead() { for(auto &i:start) ans[i] = pii(l, r); }
    bool expand(int n) {
        if(r < n && check(l, r, key[r])) {
            r++; return true;
        } else if(l > 1 && check(l, r, key[l - 1])) {
            l--; return true;
        }
        return false;
    }
};
Ayaya* merge(Ayaya *a, Ayaya *b) {
    if(sz(a->start) < sz(b->start)) swap(a, b);
    a->start.insert(a->start.end(), all(b->start));
    a->l = min(a->l, b->l);
    a->sl = min(a->sl, b->sl);
    a->r = max(a->r, b->r);
    a->sr = max(a->sr, b->sr);
    return a;
}
bool overlap(Ayaya *a, Ayaya *b) {
    return (a->inside(b->sl) || a->inside(b->sr)) &&
           (b->inside(a->sl) || b->inside(a->sr));
}

struct AyayaCmp {
    bool operator()(Ayaya* const& a, Ayaya* const& b) {
        if(a->len() != b->len()) return a->len() > b->len();
        return a->l > b->l;
    }
};

void solve(int n) {
    priority_queue<Ayaya*, vector<Ayaya*>, AyayaCmp> pq;
    For(i, 1, n) {
        pq.emplace(new Ayaya(i));
    }
    while(!pq.empty()) {
        Ayaya* a = pq.top();
        while(sz(pq) && overlap(a, pq.top())) {
            a = merge(a, pq.top());
            pq.pop();
        }
        if(a->expand(n)) {
            pq.emplace(a);
        } else {
            a->dead();
            delete a;
        }
    }
}

void solve_slow(int n) {
    For(i, 1, n) {
        Ayaya aya(i);
        while(aya.expand(n));
        aya.dead();
    }
}

int32_t main() {
    NYA();
    // nyaacho >/////<
    int n; cin >> n;
    For(i, 1, n - 1) cin >> key[i];
    For(i, 1, n) {
        int k; cin >> k;
        while(k--) {
            int x; cin >> x;
            pos[x].eb(i);
        }
    }

    solve(n);
    
    int q; cin >> q;
    while(q--) {
        int x, y; cin >> x >> y;
        pii &r = ans[x];
        if(r.F <= y && y <= r.S) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }

    // For(i, 1, n) {
    //     cerr << ans[i].F << ", " << ans[i].S << "\n";
    // }
    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 160 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 160 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 270 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Runtime error 160 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -