Submission #69454

#	Time	Username	Problem	Language	Result	Execution time	Memory
69454		Benq	Long Mansion (JOI17_long_mansion)	C++14	100 / 100	1277 ms	177720 KiB

long_mansion

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()

const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 500005;

int N, C[MX], L[MX], R[MX];
int needL[MX], needR[MX];
vi posi[MX], Rneed[MX], Lneed[MX];
priority_queue<int> p[MX];

set<int> s;
deque<pi> d;

void tri0(int i) {
    auto it = s.lb(needL[i]); if (it == s.begin()) return;
    int j = *prev(it); if (i > j) return;
    if (i == 1) { d.pb({i,N}); return; }
    int num = j-i+1; int lef = num;
    while (lef) {
        int LEF = min(d.front().s,lef);
        d.front().s -= LEF, lef -= LEF;
        if (d.front().s == 0) d.pop_front();
    }
    d.push_front({i,num});
}

void tri1(int i) {
    auto it = s.ub(needR[i]); if (it == s.end()) return;
    int j = *it; if (j > i) return;
    if (i == N) { d.pb({i,N}); return; }
    int num = i-j+1; int lef = num;
    while (lef) {
        int LEF = min(d.front().s,lef);
        d.front().s -= LEF, lef -= LEF;
        if (d.front().s == 0) d.pop_front();
    }
    d.push_front({i,num});
}

void del() {
    d.front().s --;
    if (!d.front().s) d.pop_front();
}

void gen() {
    FOR(i,1,N+1) for (int j: posi[i]) p[j].push(-i);
    FOR(i,1,N+1) {
        needL[i] = (sz(p[C[i-1]]) ? -p[C[i-1]].top() : N+1);
        Lneed[needL[i]].pb(i);
        for (int j: posi[i]) p[j].pop();
    }
    FOR(i,1,N+1) for (int j: posi[i]) p[j].push(i);
    FORd(i,1,N+1) {
        needR[i] = (sz(p[C[i]]) ? p[C[i]].top() : 0);
        Rneed[needR[i]].pb(i);
        for (int j: posi[i]) p[j].pop();
    }
    FOR(i,1,N+1) {
        for (int j: Rneed[i-1]) s.insert(j);
        tri0(i);
        L[i] = d.front().f; 
        del();
    }
    s.clear(); assert(!sz(d));
    FORd(i,1,N+1) {
        for (int j: Lneed[i+1]) s.insert(j);
        tri1(i);
        R[i] = d.front().f; 
        del();
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> N; FOR(i,1,N) cin >> C[i];
    FOR(i,1,N+1) {
        int B; cin >> B;
        F0R(j,B) {
            int A; cin >> A;
            posi[i].pb(A);
        }
    }
    gen();
    
    int Q; cin >> Q;
    F0R(i,Q) {
        int X,Y; cin >> X >> Y;
        if (L[X] <= Y && Y <= R[X]) cout << "YES";
        else cout << "NO";
        cout << "\n";
    }
}

/* Look for:
* the exact constraints (multiple sets are too slow for n=10^6 :( ) 
* special cases (n=1?)
* overflow (ll vs int?)
* array bounds
* if you have no idea just guess the appropriate well-known algo instead of doing nothing :/
*/

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 15 / 15
• Subtask 4: 75 / 75