oj.uz

Submission #133056

# Submission time Handle Problem Language Result Execution time Memory
133056 2019-07-20T06:08:49 Z rajarshi_basu Long Mansion (JOI17_long_mansion) C++14
5 / 100
 3000 ms 28072 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];
int n;
int getMaxRightNeeded(int l,int r){
	int mx = 0;
	FORE(i,l,r)mx = max(mx,rightNeeded[i]);
	return mx;
}
int getMinLeftNeeded(int l,int r){
	int mn = n;
	FORE(i,l,r)mn = min(mn,leftNeeded[i]);
	return mn;
}
 
#define endl '\n'
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
   
    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]];
    }
    
    int q;
    cin >> q;
    //cout << q << endl;
    FOR(i,q){
        int x,y;
        cin >> x >> y;
        x--;y--;
        bool b = 1;
        if(x < y){
        	FORE(ed,x,y-1){
        		if(leftNeeded[ed] == -1 or (leftNeeded[ed] < x and getMaxRightNeeded(leftNeeded[ed],x-1)> ed)){
        			b = 0;
        			break;
        		}
        	}	
        }else if(x > y){
        	for(int ed = x-1;ed >= y;ed--){
        		if(rightNeeded[ed] == n or (rightNeeded[ed] > x and getMinLeftNeeded(x,rightNeeded[ed]-1) <= ed)){
        			//cout << rightNeeded[ed] << endl;
        			//cout << leftNeeded[rightNeeded[ed]-1] << endl;
        			//cout << ed << endl;
        			b = 0;
        			break;
        		}
        	}
        }
        

        if(b){
            cout << "YES" << endl;
        }else{
            cout << "NO" << endl;
        }
    }
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14200 KB Output is correct
2 Correct 19 ms 14328 KB Output is correct
3 Correct 22 ms 14456 KB Output is correct
4 Correct 18 ms 14200 KB Output is correct
5 Correct 21 ms 14224 KB Output is correct
6 Correct 19 ms 14200 KB Output is correct
7 Correct 381 ms 14268 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14200 KB Output is correct
2 Correct 19 ms 14328 KB Output is correct
3 Correct 22 ms 14456 KB Output is correct
4 Correct 18 ms 14200 KB Output is correct
5 Correct 21 ms 14224 KB Output is correct
6 Correct 19 ms 14200 KB Output is correct
7 Correct 381 ms 14268 KB Output is correct
8 Correct 185 ms 20332 KB Output is correct
9 Correct 163 ms 20088 KB Output is correct
10 Correct 300 ms 20564 KB Output is correct
11 Correct 531 ms 20856 KB Output is correct
12 Correct 216 ms 19832 KB Output is correct
13 Correct 222 ms 20272 KB Output is correct
14 Correct 217 ms 20264 KB Output is correct
15 Correct 326 ms 20296 KB Output is correct
16 Correct 553 ms 20260 KB Output is correct
17 Correct 189 ms 20304 KB Output is correct
18 Correct 243 ms 20344 KB Output is correct
19 Correct 238 ms 20356 KB Output is correct
20 Correct 476 ms 20348 KB Output is correct
21 Correct 549 ms 20088 KB Output is correct
22 Correct 332 ms 20216 KB Output is correct
23 Execution timed out 3049 ms 15172 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1399 ms 22324 KB Output is correct
2 Correct 2868 ms 28072 KB Output is correct
3 Execution timed out 3069 ms 24272 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 14200 KB Output is correct
2 Correct 19 ms 14328 KB Output is correct
3 Correct 22 ms 14456 KB Output is correct
4 Correct 18 ms 14200 KB Output is correct
5 Correct 21 ms 14224 KB Output is correct
6 Correct 19 ms 14200 KB Output is correct
7 Correct 381 ms 14268 KB Output is correct
8 Correct 185 ms 20332 KB Output is correct
9 Correct 163 ms 20088 KB Output is correct
10 Correct 300 ms 20564 KB Output is correct
11 Correct 531 ms 20856 KB Output is correct
12 Correct 216 ms 19832 KB Output is correct
13 Correct 222 ms 20272 KB Output is correct
14 Correct 217 ms 20264 KB Output is correct
15 Correct 326 ms 20296 KB Output is correct
16 Correct 553 ms 20260 KB Output is correct
17 Correct 189 ms 20304 KB Output is correct
18 Correct 243 ms 20344 KB Output is correct
19 Correct 238 ms 20356 KB Output is correct
20 Correct 476 ms 20348 KB Output is correct
21 Correct 549 ms 20088 KB Output is correct
22 Correct 332 ms 20216 KB Output is correct
23 Execution timed out 3049 ms 15172 KB Time limit exceeded
24 Halted 0 ms 0 KB -