oj.uz

Submission #122137

# Submission time Handle Problem Language Result Execution time Memory
122137 2019-06-27T16:37:06 Z rajarshi_basu Long Mansion (JOI17_long_mansion) C++14
10 / 100
 3000 ms 28844 KB 
#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <fstream>
#include <complex>
#include <random>
#include <stack>
#include <chrono>
#include <set>

#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double> 
#define ld long double
#define pld pair<ld,ld>
#define iii pair<ii,int>
#define vv vector

using namespace std;

const int MAXN = 5e5+10;
int C[MAXN];
int leftNeeded[MAXN];
int rightNeeded[MAXN];
vi keys[MAXN];
int L[MAXN];
int R[MAXN];
int last[MAXN];

#define endl '\n'
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    FOR(i,n-1)cin >> C[i];
    FOR(i,n){
        int x;cin >> x;
        FOR(j,x){
            int y;cin >> y;
            keys[i].pb(y);
        }
    }

    // input taking is done, now find left and right needed values for each edge.
    FOR(i,MAXN)last[i] = -1;
    FOR(i,n-1){
        for(auto e : keys[i]){
            last[e] = i;
        }
        leftNeeded[i] = last[C[i]];
    }
    FOR(i,MAXN)last[i] = n;
    for(int i = n-1;i>0;i--){
        for(auto e : keys[i])last[e] = i;
        rightNeeded[i-1] = last[C[i-1]];
    }
    FOR(i,n-1){
      //  cout << leftNeeded[i] << " " << rightNeeded[i] << endl;
    }
    //cout << endl;
    // we have found out the left and right needed. now we need to compute all the ranges.
    FOR(i,n){
        int rightl = (i == 0)?-1:R[i-1];
        if(rightl >= i and 0){
            // we know that we cannot escape from this box anyway. 
            // now try to go left once.
            int minR = rightNeeded[i-1];
            int ind = -1;
            FORE(edge,i,min(rightl-1,minR-1)){
                if(leftNeeded[edge] < i){
                    ind = edge;
                }
            }
            if(ind == -1){
                L[i] = L[i-1];
                R[i] = R[i-1];
            }else{
                L[i] = i;
                R[i] = ind;
            }
        }else{
            // try increasing right ptr one by one. and for each such move, increase left pointer as much as possible.
            int lptr = i;
            int rptr = i;
            while(rptr < n){
                while(lptr > 0 and rightNeeded[lptr-1] <= rptr)lptr--;
                if(leftNeeded[rptr] < lptr)break;
                rptr++;
            }
            L[i] = lptr;
            R[i] = rptr;
        }
      //  cout << L[i] << " " << R[i] << endl;
    }
   
    int q;
    cin >> q;
    //cout << q << endl;
    FOR(i,q){
        int x,y;
        cin >> x >> y;
        x--;y--;
        if(L[x] <= y and y <= R[x]){
            cout << "YES" << endl;
        }else{
            cout << "NO" << endl;
        }
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14208 KB Output is correct
2 Correct 19 ms 14208 KB Output is correct
3 Correct 28 ms 14456 KB Output is correct
4 Correct 17 ms 14336 KB Output is correct
5 Correct 20 ms 14208 KB Output is correct
6 Correct 17 ms 14336 KB Output is correct
7 Correct 18 ms 14336 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14208 KB Output is correct
2 Correct 19 ms 14208 KB Output is correct
3 Correct 28 ms 14456 KB Output is correct
4 Correct 17 ms 14336 KB Output is correct
5 Correct 20 ms 14208 KB Output is correct
6 Correct 17 ms 14336 KB Output is correct
7 Correct 18 ms 14336 KB Output is correct
8 Correct 124 ms 20188 KB Output is correct
9 Correct 118 ms 19960 KB Output is correct
10 Correct 126 ms 20344 KB Output is correct
11 Correct 132 ms 20828 KB Output is correct
12 Correct 108 ms 19704 KB Output is correct
13 Correct 118 ms 20316 KB Output is correct
14 Correct 115 ms 20344 KB Output is correct
15 Correct 123 ms 20260 KB Output is correct
16 Correct 118 ms 20112 KB Output is correct
17 Correct 113 ms 20216 KB Output is correct
18 Correct 115 ms 20344 KB Output is correct
19 Correct 113 ms 20260 KB Output is correct
20 Correct 117 ms 20212 KB Output is correct
21 Correct 120 ms 20092 KB Output is correct
22 Correct 117 ms 20188 KB Output is correct
23 Correct 115 ms 19984 KB Output is correct
24 Correct 116 ms 20128 KB Output is correct
25 Correct 116 ms 19960 KB Output is correct
26 Correct 114 ms 20264 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 860 ms 21488 KB Output is correct
2 Correct 1696 ms 28844 KB Output is correct
3 Execution timed out 3052 ms 21228 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 14208 KB Output is correct
2 Correct 19 ms 14208 KB Output is correct
3 Correct 28 ms 14456 KB Output is correct
4 Correct 17 ms 14336 KB Output is correct
5 Correct 20 ms 14208 KB Output is correct
6 Correct 17 ms 14336 KB Output is correct
7 Correct 18 ms 14336 KB Output is correct
8 Correct 124 ms 20188 KB Output is correct
9 Correct 118 ms 19960 KB Output is correct
10 Correct 126 ms 20344 KB Output is correct
11 Correct 132 ms 20828 KB Output is correct
12 Correct 108 ms 19704 KB Output is correct
13 Correct 118 ms 20316 KB Output is correct
14 Correct 115 ms 20344 KB Output is correct
15 Correct 123 ms 20260 KB Output is correct
16 Correct 118 ms 20112 KB Output is correct
17 Correct 113 ms 20216 KB Output is correct
18 Correct 115 ms 20344 KB Output is correct
19 Correct 113 ms 20260 KB Output is correct
20 Correct 117 ms 20212 KB Output is correct
21 Correct 120 ms 20092 KB Output is correct
22 Correct 117 ms 20188 KB Output is correct
23 Correct 115 ms 19984 KB Output is correct
24 Correct 116 ms 20128 KB Output is correct
25 Correct 116 ms 19960 KB Output is correct
26 Correct 114 ms 20264 KB Output is correct
27 Correct 860 ms 21488 KB Output is correct
28 Correct 1696 ms 28844 KB Output is correct
29 Execution timed out 3052 ms 21228 KB Time limit exceeded
30 Halted 0 ms 0 KB -