Submission #72537

#	Time	Username	Problem	Language	Result	Execution time	Memory
72537		유애나 (#118)	Easy Data Structure Problem (FXCUP3_easy)	C++17	100 / 100	291 ms	122672 KiB

easy

#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 (stderr)

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 / 33
• Subtask 2: 67 / 67