oj.uz

Submission #41525

# Submission time Handle Problem Language Result Execution time Memory
41525 2018-02-18T11:01:36 Z grumpy_gordon Long Mansion (JOI17_long_mansion) C++14
100 / 100
 491 ms 262144 KB 
/*
                     .:*+=%@@@@@@=-.
                 .:=@#@@@#@@#######%==*.
              .-=####@######%*-.....:%##%.
            .*@###########%+:--........-%@-
          .*@##############@+--.........-:%-
        .+##################@==%%%%=+*:----+.
      .-@####################%++%@@@@@=+**%@@*
      .%###################@%%@@@###@%+:--%@@%.
     -@###################@%%%%*::*%++:-----=@+.
    -#####################@%=++++++*:-------.-=:
   .+####################@%++*::-:::--::*:::***=:
   .@#####################%=++*::::-:::++*=##@@#@-
  ..#####################@%%=++**:::::**+%@#@%%##-..
   .%####################@@%=+++*+****::*=@######@.
  .=######################@%%==+==++**+=@%@##@###+:...
  -#######################@@@%%%===++=@@@%=++===*::--...
  -########################@@@@@@@%==%%=++==@@:::::*:--.
..:#########################@@@@@@%%======++++::-..:-.--...
%#############################@###@%%@@%==%=%*----.--.::---.
#############################################*-:*:-:---*---- .
#############################################*--*--:---*---:-.
#############################################+--::--::-*::-::.
###########################################+:*-.---.---.:---*-..
###########################################**:-----------------.
##########################################@::**:--::::::--:::::-
###########################################:--:*:::::::::**::*+*
###########################################=:::***::::::**:::*+*
############################@@@@@@#########@+****::::********+++
############################@%%%%%@@@@@@@###%+***::::::::***+==+
############################@%%%%%%%%%%%@####=+:::-::::-::*+=%%+
#############################@%%%%%%%%%%@#####=::--------:*=%@%+
%###########################@%%%%==%%%%%%@##@#=:------..-:+%@@%=
----------------------------------------------
--------------------------------------------
----------------------------------------------
--------------------------------------------
----------------------------------------------

         o###########oo
      o##"          ""##o
    o#"                "##
  o#"                    "#o
 #"  ##              ##   "##
#"                          ##
#  ###################       #
#                            #
#                            #
#                            #
#                            #
#                            #
#                            #
#o                           #
"#o                         ##
 "#o                       ##
  "#o                    o#"
   "#o                  ##
     "#o              o#"
       "#ooo      ooo#######oo
        ###############   "######o
     o###""        "###o      # ###
   o###o     oooo    ###    oo####"
 o###**#     #**#   ############"
 ""##""""""""""###########    #
    # oooooooo#"#**     ##    #
    # #       # # **    ##    #
    #o#       #o#  *****###ooo#
                        ##
                        ##   o###o
                        ## o##***##
               o########## #***#**##o
             o##"   ""###  #***##***#
 o#######o  ###   oo####   ##**####*#
o##"  ""#############""     ##****###
##"         ##              ##*##*###
##          ###              ##### ##
##           ###              # ##  #
##            ##                 #
##             ##
##             ###
##              ###oo
###              ""###
 ###
  ###
*/
#include <bits/stdc++.h>

//#pragma GCC optimize("O3")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
//float __attribute__((aligned(32)))

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef long double ld;

int mysqrt(ll x){
    int l = 0, r = 1e9 + 1;
    while (r - l > 1){
        int m = (l + r) / 2;
        if (m * (ll)m <= x)
            l = m;
        else
            r = m;
    }
    return l;
}

mt19937 rnd(1337);

ll AR = 19, BR = 13, CR = 23, XR = 228, YR = 322, MODR = 1e9 + 993;

ll myrand(){
    ll ZR = (XR * AR + YR * BR + CR) % MODR;
    XR = YR;
    YR = ZR;
    return ZR;
}

const int Mod = 1e9 + 7;

int bpow(int x, int y){
    if (y == 0)
        return 1;
    if (y == 1)
        return x;
    int ret = bpow(x, y >> 1);
    ret = (ret * (ll)ret) % Mod;
    if (y & 1)
        ret = (ret * (ll)x) % Mod;
    return ret;
}

int bdiv(int x, int y){
    return (x * (ll)bpow(y, Mod - 2)) % Mod;
}

void setmin(int &x, int y){
    x = min(x, y);
}

void setmax(int &x, int y){
    x = max(x, y);
}

void setmin(ll &x, ll y){
    x = min(x, y);
}

void setmax(ll &x, ll y){
    x = max(x, y);
}

int gcd(int a, int b){
    return a ? gcd(b % a, a) : b;
}

const ll llinf = 2e18 + 100;

const double eps = 1e-9;

const int maxn = 5e5 + 100, maxw = 1e6 + 100, inf = 2e9 + 100, sq = 300, mod = 1e9 + 7, LG = 17;

int n;

int arr[maxn];

vector<int> mas[maxn];

pair<int, int> ans[maxn];

pair<int, int> cl[maxn];

vector<int> moves[maxn];

void solve(){
    for (int i = 0; i < n - 1; i++){
        int l, r;
        int val = arr[i];
        l = -1, r = mas[val].size();
        while (r - l > 1){
            int m = (l + r) / 2;
            if (mas[val][m] <= i)
                l = m;
            else
                r = m;
        }
        cl[i + 1].first = (l == -1 ? -1 : mas[val][l]);
        l++;
        cl[i + 1].second = (l < mas[val].size() ? mas[val][l] : n);
    }
    cl[n] = make_pair(-1, n);
    cl[0] = make_pair(-1, n);
    vector<int> g;
    for (int i = n - 1; i >= 0; i--){
        while (!g.empty() && cl[g.back()].first >= cl[i + 1].first)
            moves[i].push_back(g.back()), g.pop_back();
        g.push_back(i + 1);
        moves[i].push_back(-1);
        reverse(moves[i].begin(), moves[i].end());
    }
    vector<int> q;
    for (int i = 0; i < n; i++){
        while (!q.empty() && cl[q.back()].second <= cl[i].second)
            q.pop_back();
        q.push_back(i);
        while (!q.empty()){
            int l = -1, r = g.size();
            while (r - l > 1){
                int m = (l + r) / 2;
                if (cl[g[m]].first < q.back())
                    l = m;
                else
                    r = m;
            }
            if (l >= 0 && g[l] <= cl[q.back()].second){
                ans[i] = make_pair(q.back(), g[l] - 1);
                break;
            }
            else
                q.pop_back();
        }
        for (auto x : moves[i])
            if (x == -1)
                g.pop_back();
            else
                g.push_back(x);
    }
}

int main()
{
    #ifdef ONPC
    //ifstream cin("a.in");
    //ofstream cout("a.out");
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
    #else
    //ifstream cin("sprinklers.in");
    //ofstream cout("sprinklers.out");
    //freopen("road.in", "r", stdin);
    //freopen("road.out", "w", stdout);
    #endif // ONPC
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 0; i < n - 1; i++)
        cin >> arr[i], arr[i]--;
    for (int i = 0; i < n; i++){
        int k;
        cin >> k;
        while (k--){
            int x;
            cin >> x;
            mas[x - 1].push_back(i);
        }
    }
    solve();
    //for (int i = 0; i < n; i++)
    //cout << ans[i].first << ' ' << ans[i].second << '\n';
    int zap;
    cin >> zap;
    while (zap--){
        int from, to;
        cin >> from >> to;
        from--;
        to--;
        if (ans[from].first <= to && to <= ans[from].second)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
}

Compilation message

long_mansion.cpp: In function 'void solve()':
long_mansion.cpp:195:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         cl[i + 1].second = (l < mas[val].size() ? mas[val][l] : n);
                               ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23932 KB Output is correct
2 Correct 25 ms 24160 KB Output is correct
3 Correct 25 ms 24476 KB Output is correct
4 Correct 24 ms 24476 KB Output is correct
5 Correct 24 ms 24504 KB Output is correct
6 Correct 23 ms 24580 KB Output is correct
7 Correct 23 ms 24656 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23932 KB Output is correct
2 Correct 25 ms 24160 KB Output is correct
3 Correct 25 ms 24476 KB Output is correct
4 Correct 24 ms 24476 KB Output is correct
5 Correct 24 ms 24504 KB Output is correct
6 Correct 23 ms 24580 KB Output is correct
7 Correct 23 ms 24656 KB Output is correct
8 Correct 133 ms 30576 KB Output is correct
9 Correct 148 ms 34828 KB Output is correct
10 Correct 135 ms 39872 KB Output is correct
11 Correct 137 ms 44672 KB Output is correct
12 Correct 122 ms 48292 KB Output is correct
13 Correct 129 ms 52696 KB Output is correct
14 Correct 133 ms 57200 KB Output is correct
15 Correct 124 ms 61456 KB Output is correct
16 Correct 131 ms 65680 KB Output is correct
17 Correct 132 ms 69616 KB Output is correct
18 Correct 130 ms 74028 KB Output is correct
19 Correct 122 ms 78424 KB Output is correct
20 Correct 127 ms 82680 KB Output is correct
21 Correct 130 ms 86720 KB Output is correct
22 Correct 129 ms 90880 KB Output is correct
23 Correct 127 ms 94892 KB Output is correct
24 Correct 131 ms 99132 KB Output is correct
25 Correct 124 ms 103444 KB Output is correct
26 Correct 127 ms 107772 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 114712 KB Output is correct
2 Correct 265 ms 121752 KB Output is correct
3 Correct 235 ms 128744 KB Output is correct
4 Correct 245 ms 136192 KB Output is correct
5 Correct 237 ms 143344 KB Output is correct
6 Correct 200 ms 149064 KB Output is correct
7 Correct 203 ms 155440 KB Output is correct
8 Correct 214 ms 161500 KB Output is correct
9 Correct 202 ms 167596 KB Output is correct
10 Correct 209 ms 173588 KB Output is correct
11 Correct 199 ms 179548 KB Output is correct

Subtask #4
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23932 KB Output is correct
2 Correct 25 ms 24160 KB Output is correct
3 Correct 25 ms 24476 KB Output is correct
4 Correct 24 ms 24476 KB Output is correct
5 Correct 24 ms 24504 KB Output is correct
6 Correct 23 ms 24580 KB Output is correct
7 Correct 23 ms 24656 KB Output is correct
8 Correct 133 ms 30576 KB Output is correct
9 Correct 148 ms 34828 KB Output is correct
10 Correct 135 ms 39872 KB Output is correct
11 Correct 137 ms 44672 KB Output is correct
12 Correct 122 ms 48292 KB Output is correct
13 Correct 129 ms 52696 KB Output is correct
14 Correct 133 ms 57200 KB Output is correct
15 Correct 124 ms 61456 KB Output is correct
16 Correct 131 ms 65680 KB Output is correct
17 Correct 132 ms 69616 KB Output is correct
18 Correct 130 ms 74028 KB Output is correct
19 Correct 122 ms 78424 KB Output is correct
20 Correct 127 ms 82680 KB Output is correct
21 Correct 130 ms 86720 KB Output is correct
22 Correct 129 ms 90880 KB Output is correct
23 Correct 127 ms 94892 KB Output is correct
24 Correct 131 ms 99132 KB Output is correct
25 Correct 124 ms 103444 KB Output is correct
26 Correct 127 ms 107772 KB Output is correct
27 Correct 215 ms 114712 KB Output is correct
28 Correct 265 ms 121752 KB Output is correct
29 Correct 235 ms 128744 KB Output is correct
30 Correct 245 ms 136192 KB Output is correct
31 Correct 237 ms 143344 KB Output is correct
32 Correct 200 ms 149064 KB Output is correct
33 Correct 203 ms 155440 KB Output is correct
34 Correct 214 ms 161500 KB Output is correct
35 Correct 202 ms 167596 KB Output is correct
36 Correct 209 ms 173588 KB Output is correct
37 Correct 199 ms 179548 KB Output is correct
38 Correct 458 ms 208324 KB Output is correct
39 Correct 491 ms 224696 KB Output is correct
40 Correct 368 ms 225120 KB Output is correct
41 Correct 440 ms 244224 KB Output is correct
42 Correct 210 ms 244224 KB Output is correct
43 Correct 220 ms 244224 KB Output is correct
44 Correct 329 ms 255296 KB Output is correct
45 Correct 338 ms 262144 KB Output is correct
46 Correct 336 ms 262144 KB Output is correct
47 Correct 207 ms 262144 KB Output is correct
48 Correct 216 ms 262144 KB Output is correct
49 Correct 322 ms 262144 KB Output is correct
50 Correct 322 ms 262144 KB Output is correct
51 Correct 344 ms 262144 KB Output is correct
52 Correct 309 ms 262144 KB Output is correct
53 Correct 422 ms 262144 KB Output is correct
54 Correct 459 ms 262144 KB Output is correct
55 Correct 362 ms 262144 KB Output is correct