oj.uz

답안 #122139

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
122139 2019-06-27T16:39:59 Z rajarshi_basu Long Mansion (JOI17_long_mansion) C++14
10 / 100
 3000 ms 21596 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){
            // 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;
                    break;
                }
            }
            if(ind == -1){
                L[i] = L[i-1];
                R[i] = R[i-1];
                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;
            }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

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 14200 KB Output is correct
2 Correct 18 ms 14208 KB Output is correct
3 Correct 27 ms 14336 KB Output is correct
4 Correct 16 ms 14208 KB Output is correct
5 Correct 18 ms 14208 KB Output is correct
6 Correct 16 ms 14208 KB Output is correct
7 Correct 16 ms 14208 KB Output is correct

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 14200 KB Output is correct
2 Correct 18 ms 14208 KB Output is correct
3 Correct 27 ms 14336 KB Output is correct
4 Correct 16 ms 14208 KB Output is correct
5 Correct 18 ms 14208 KB Output is correct
6 Correct 16 ms 14208 KB Output is correct
7 Correct 16 ms 14208 KB Output is correct
8 Correct 130 ms 15908 KB Output is correct
9 Correct 119 ms 15724 KB Output is correct
10 Correct 124 ms 15856 KB Output is correct
11 Correct 130 ms 16052 KB Output is correct
12 Correct 110 ms 15868 KB Output is correct
13 Correct 117 ms 15864 KB Output is correct
14 Correct 117 ms 15864 KB Output is correct
15 Correct 116 ms 15992 KB Output is correct
16 Correct 111 ms 16120 KB Output is correct
17 Correct 113 ms 15864 KB Output is correct
18 Correct 112 ms 15868 KB Output is correct
19 Correct 113 ms 15864 KB Output is correct
20 Correct 114 ms 15992 KB Output is correct
21 Correct 116 ms 16120 KB Output is correct
22 Correct 115 ms 15984 KB Output is correct
23 Correct 114 ms 15856 KB Output is correct
24 Correct 115 ms 15972 KB Output is correct
25 Correct 115 ms 15736 KB Output is correct
26 Correct 116 ms 15736 KB Output is correct

Subtask #3
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 860 ms 21596 KB Output is correct
2 Correct 1714 ms 21440 KB Output is correct
3 Execution timed out 3034 ms 19848 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 14200 KB Output is correct
2 Correct 18 ms 14208 KB Output is correct
3 Correct 27 ms 14336 KB Output is correct
4 Correct 16 ms 14208 KB Output is correct
5 Correct 18 ms 14208 KB Output is correct
6 Correct 16 ms 14208 KB Output is correct
7 Correct 16 ms 14208 KB Output is correct
8 Correct 130 ms 15908 KB Output is correct
9 Correct 119 ms 15724 KB Output is correct
10 Correct 124 ms 15856 KB Output is correct
11 Correct 130 ms 16052 KB Output is correct
12 Correct 110 ms 15868 KB Output is correct
13 Correct 117 ms 15864 KB Output is correct
14 Correct 117 ms 15864 KB Output is correct
15 Correct 116 ms 15992 KB Output is correct
16 Correct 111 ms 16120 KB Output is correct
17 Correct 113 ms 15864 KB Output is correct
18 Correct 112 ms 15868 KB Output is correct
19 Correct 113 ms 15864 KB Output is correct
20 Correct 114 ms 15992 KB Output is correct
21 Correct 116 ms 16120 KB Output is correct
22 Correct 115 ms 15984 KB Output is correct
23 Correct 114 ms 15856 KB Output is correct
24 Correct 115 ms 15972 KB Output is correct
25 Correct 115 ms 15736 KB Output is correct
26 Correct 116 ms 15736 KB Output is correct
27 Correct 860 ms 21596 KB Output is correct
28 Correct 1714 ms 21440 KB Output is correct
29 Execution timed out 3034 ms 19848 KB Time limit exceeded
30 Halted 0 ms 0 KB -