oj.uz

Submission #72537

# Submission time Handle Problem Language Result Execution time Memory
72537 2018-08-26T08:52:57 Z 유애나(#2199, kdh9949) Easy Data Structure Problem (FXCUP3_easy) C++17
100 / 100
 291 ms 122672 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 100005, sz = 131072;

int n, a[N], p[N], q, m, b[40];
int lc[2 * sz][40], ld[2 * sz][40], rc[2 * sz][40], rd[2 * sz][40];

struct Seg{
    int d[2 * sz], l[2 * sz], r[2 * sz];
    void i(int x){
        d[x] = N;
        if(x >= sz){
            l[x] = r[x] = x - sz + 1;
            return;
        }
        i(2 * x); i(2 * x + 1);
        l[x] = l[2 * x]; r[x] = r[2 * x + 1];
    }
    void u(int x, int v){
        for(x += sz - 1; x; x /= 2){
            if(r[x] > n) break;
            d[x] = min(d[x], v);
        }
    }
} S;

int lf(int x, int i){
    if(S.d[x] != b[i]) return -1;
    if(!(x & (x - 1)) && i > 0) return -1;
    if(i == 0) return S.l[x];
    if(lc[x][i] == q) return ld[x][i];
    lc[x][i] = q;
    for(int nx = ((x & 1) ? 2 * x - 1 : x - 1); nx < 2 * sz; nx = 2 * nx + 1){
        int t = lf(nx, i - 1);
        if(t > 0){ ld[x][i] = t; return t; }
    }
    return ld[x][i] = -1;
}

int rf(int x, int i){
    if(S.d[x] != b[i]) return -1;
    if(!(x & (x + 1)) && i < m - 1) return -1;
    if(i == m - 1) return S.r[x];
    if(rc[x][i] == q) return rd[x][i];
    rc[x][i] = q;
    for(int nx = ((x & 1) ? x + 1 : 2 * x + 2); nx < 2 * sz; nx = 2 * nx){
        int t = rf(nx, i + 1);
        if(t > 0){ rd[x][i] = t; return t; }
    }
    return rd[x][i] = -1;
}

int main(){
    scanf("%d%d", &n, &q);
    S.i(1);
    for(int i = 1; i <= n; i++){
        scanf("%d", a + i);
        p[a[i]] = i;
        S.u(i, a[i]);
    }
    for(; q; q--){
        scanf("%d", &m);
        for(int i = 0; i < m; i++) scanf("%d", b + i);
        sort(b, b + m, [](int x, int y){ return p[x] < p[y]; });
        int can = 0;
        for(int i = 0; i < m; i++){
            for(int j = p[b[i]] + sz - 1; j; j /= 2){
                if(S.d[j] != b[i]) break;
                if(lf(j, i) > 0 && rf(j, i) > 0){
                    printf("%d %d\n", lf(j, i), rf(j, i));
                    can = 1;
                    break;
                }
            }
            if(can) break;
        }
        if(!can) puts("-1");
    }
    return 0;
}

Compilation message

easy.cpp: In function 'int main()':
easy.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &q);
     ~~~~~^~~~~~~~~~~~~~~~
easy.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", a + i);
         ~~~~~^~~~~~~~~~~~~
easy.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &m);
         ~~~~~^~~~~~~~~~
easy.cpp:64:41: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         for(int i = 0; i < m; i++) scanf("%d", b + i);
                                    ~~~~~^~~~~~~~~~~~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3320 KB Correct
2 Correct 6 ms 3432 KB Correct
3 Correct 7 ms 3740 KB Correct
4 Correct 16 ms 3768 KB Correct
5 Correct 9 ms 3924 KB Correct
6 Correct 24 ms 4016 KB Correct
7 Correct 18 ms 4032 KB Correct
8 Correct 21 ms 4032 KB Correct

Subtask #2
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3320 KB Correct
2 Correct 6 ms 3432 KB Correct
3 Correct 7 ms 3740 KB Correct
4 Correct 16 ms 3768 KB Correct
5 Correct 9 ms 3924 KB Correct
6 Correct 24 ms 4016 KB Correct
7 Correct 18 ms 4032 KB Correct
8 Correct 21 ms 4032 KB Correct
9 Correct 31 ms 4688 KB Correct
10 Correct 45 ms 6096 KB Correct
11 Correct 50 ms 6224 KB Correct
12 Correct 199 ms 83792 KB Correct
13 Correct 181 ms 83792 KB Correct
14 Correct 273 ms 121468 KB Correct
15 Correct 274 ms 121468 KB Correct
16 Correct 291 ms 122672 KB Correct
17 Correct 240 ms 122672 KB Correct