oj.uz

Submission #204513

# Submission time Handle Problem Language Result Execution time Memory
204513 2020-02-26T08:00:17 Z balbit Long Mansion (JOI17_long_mansion) C++14
10 / 100
 3000 ms 41812 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define SZ(x) x.size()
#define pii pair<int, int>
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#ifdef BALBIT
#define bug(...) cerr<<"#"<<#__VA_ARGS__<<" : ", _do(__VA_ARGS__)
template<typename T> void _do(T && x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S && ...y){cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0),cin.tie(0)
#define endl '\n'
#endif // BALBIT

const int mod = 1e9+7;

const int maxn = 5e5+3;

struct que{
    int pos, id;
};
int ans[maxn], ed[maxn], far[maxn]; // ed is color of the one to the left, far is the farthest right it can go
//set<int> key[maxn], rset[maxn]; // set of the things that go to its right
vector<int> keyat[maxn]; // Where the keys are for this color
bool have[maxn]; // keys i have
vector<que> QQ[maxn];

bool is(int x, int l, int r) { // is there x between l and r (inclusive)?
    return upper_bound(ALL(keyat[x]),r) != lower_bound(ALL(keyat[x]),l);
}

void merg(set<int> &a, set<int> &b) {
    if (SZ(a)<SZ(b)) a.swap(b);
    for (int x : b) a.insert(x);
    b.clear();
}

pii rch[maxn];

signed main(){
    IOS();
    int n,q; cin>>n;
    for (int i = 1; i<n; i++) {
        cin>>ed[i];
    }
    for (int i = 0; i<n; i++){
        int m; cin>>m;
        for (int j = 0;j<m; j++){
            int x; cin>>x; // Colors are 1-based
//            key[i].insert(x);
//            rset[i].insert(x);
            keyat[x].pb(i);
        }
    }
//    for (int i = n-1; i>=0 ; i--) {
//        far[i] = i;
//        while (far[i] < n-1 && rset[i].count(ed[far[i]+1])) {
//            merg(rset[i],rset[far[i]+1]);
//            far[i] = far[far[i]+1];
//        }
//        bug(i,far[i]);
//        for (int x : rset[i]) {
//            bug(x);
//        }
//    }
    cin>>q;
    for (int i = 0; i<q; i++) {
        int fr, to;
        cin>>fr>>to; --fr; --to;
        QQ[fr].pb({to,i});
    }
    for (int i = 0; i<n; i++) rch[i] = {i,i};
    for (int i = 0; i<n; i++) {
        bool B = 1;
        int L = rch[i].f, R = rch[i].s;
        while (B) {
            B=0;
            if (is(ed[L], L, R)) {
                // can reach L-1
                L = min (L, rch[L-1].f);
                R = max (R, rch[L-1].s);
                B = 1;
            }
            if (is (ed[R+1], L, R)){
                // can reach R+1
                L = min(L,rch[R+1].f);
                R = max(R,rch[R+1].s);
                B = 1;
            }
        }
        for (que ele : QQ[i]) {
            if (ele.pos>=L && ele.pos<=R) {
                ans[ele.id] = 1;
            }
        }
    }
    for (int i = 0; i<q; i++) {
        if (ans[i]) {
            cout<<"YES"<<endl;
        }else{
            cout<<"NO"<<endl;
        }
    }
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 24056 KB Output is correct
2 Correct 265 ms 24056 KB Output is correct
3 Correct 1210 ms 24292 KB Output is correct
4 Correct 28 ms 24056 KB Output is correct
5 Correct 265 ms 24056 KB Output is correct
6 Correct 41 ms 24056 KB Output is correct
7 Correct 37 ms 24056 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 24056 KB Output is correct
2 Correct 265 ms 24056 KB Output is correct
3 Correct 1210 ms 24292 KB Output is correct
4 Correct 28 ms 24056 KB Output is correct
5 Correct 265 ms 24056 KB Output is correct
6 Correct 41 ms 24056 KB Output is correct
7 Correct 37 ms 24056 KB Output is correct
8 Correct 196 ms 38140 KB Output is correct
9 Correct 182 ms 38008 KB Output is correct
10 Correct 403 ms 38776 KB Output is correct
11 Correct 1365 ms 38112 KB Output is correct
12 Correct 192 ms 37496 KB Output is correct
13 Correct 164 ms 38648 KB Output is correct
14 Correct 166 ms 38776 KB Output is correct
15 Correct 257 ms 38520 KB Output is correct
16 Correct 378 ms 38264 KB Output is correct
17 Correct 173 ms 38780 KB Output is correct
18 Correct 171 ms 38520 KB Output is correct
19 Correct 175 ms 38776 KB Output is correct
20 Correct 332 ms 37340 KB Output is correct
21 Correct 391 ms 38392 KB Output is correct
22 Correct 200 ms 38648 KB Output is correct
23 Correct 183 ms 38136 KB Output is correct
24 Correct 170 ms 38136 KB Output is correct
25 Correct 184 ms 38092 KB Output is correct
26 Correct 163 ms 37940 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3023 ms 41812 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 24056 KB Output is correct
2 Correct 265 ms 24056 KB Output is correct
3 Correct 1210 ms 24292 KB Output is correct
4 Correct 28 ms 24056 KB Output is correct
5 Correct 265 ms 24056 KB Output is correct
6 Correct 41 ms 24056 KB Output is correct
7 Correct 37 ms 24056 KB Output is correct
8 Correct 196 ms 38140 KB Output is correct
9 Correct 182 ms 38008 KB Output is correct
10 Correct 403 ms 38776 KB Output is correct
11 Correct 1365 ms 38112 KB Output is correct
12 Correct 192 ms 37496 KB Output is correct
13 Correct 164 ms 38648 KB Output is correct
14 Correct 166 ms 38776 KB Output is correct
15 Correct 257 ms 38520 KB Output is correct
16 Correct 378 ms 38264 KB Output is correct
17 Correct 173 ms 38780 KB Output is correct
18 Correct 171 ms 38520 KB Output is correct
19 Correct 175 ms 38776 KB Output is correct
20 Correct 332 ms 37340 KB Output is correct
21 Correct 391 ms 38392 KB Output is correct
22 Correct 200 ms 38648 KB Output is correct
23 Correct 183 ms 38136 KB Output is correct
24 Correct 170 ms 38136 KB Output is correct
25 Correct 184 ms 38092 KB Output is correct
26 Correct 163 ms 37940 KB Output is correct
27 Execution timed out 3023 ms 41812 KB Time limit exceeded
28 Halted 0 ms 0 KB -