Submission #72545

#	Time	Username	Problem	Language	Result	Execution time	Memory
72545		신딩없는 신딩팀 (#118)	Easy Data Structure Problem (FXCUP3_easy)	C++11	0 / 100	3 ms	432 KiB

easy

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
#define M 100005
int n,q;
int A[M];
int H[M];
int L[M], Lcnt;

int seg[M];
void updt(int idx,int s,int e,int x,int v) {
    if(s==e) {
        seg[idx] = v;
        return;
    }
    if(x<=(s+e)/2) updt(idx*2,s,(s+e)/2,x,v);
    else updt(idx*2+1,(s+e)/2+1,e,x,v);
    seg[idx] = min(seg[idx*2], seg[idx*2+1]);
}
int query(int idx,int s,int e,int l,int r) {
    if(e<l || r<s) return M;
    if(l<=s&&e<=r) return seg[idx];
    return min(query(idx*2,s,(s+e)/2,l,r) , query(idx*2+1,(s+e)/2+1,e,l,r));
}
pii P[M];
pii upp(pii a) {
    pii ret;
    int len = a.second - a.first + 1;
    if((a.second + len) % (2*len) == 0) {
        return pii(a.first , a.second + len);
    }
    return pii(a.first - len , a.second);
}
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++) {
        cin>>A[i];
        H[A[i]] = i;
        updt(1,1,n,i,A[i]);
    }
    while(q--) {
        cin>>Lcnt;
        for(int i=0;i<Lcnt;i++) {
            cin>>L[i];
        }
        sort(L,L+Lcnt,[](int a,int b){return H[a] < H[b];});
        int flag = 0;
        if(Lcnt == 1) {
            cout<<H[L[0]]<<' '<<H[L[0]]<<'\n';
            continue;
        }
        for(int i=1;i<Lcnt-1;i++) {
            P[i] = pii(H[L[i]],H[L[i]]);
            while(1) {
                pii u = upp(P[i]);
                if(u.first < 1 || n < u.second) break;
                if(H[L[i-1]] >= u.first || u.second >= H[L[i+1]]) break;
                if(query(1,1,n,u.first,u.second) != L[i]) {
                    flag = 1;
                    break;
                }
                P[i] = u;
            }
        }
        P[0] = pii(H[L[0]],H[L[0]]);
        P[Lcnt-1] = pii(H[L[Lcnt-1]],H[L[Lcnt-1]]);
        while(1) {
            pii u = upp(P[0]);
            if(u.first < 1 || n < u.second) break;
            if(u.second >= P[1].first) break;
            if(query(1,1,n,u.first,u.second) != L[0]) {
                break;
            }
            P[0] = u;
        }
        while(1) {
            pii u = upp(P[Lcnt-1]);
            if(u.first < 1 || n < u.second) break;
            if(u.first <= P[Lcnt-2].second) break;
            if(query(1,1,n,u.first,u.second) != L[Lcnt-1]) {
                break;
            }
            P[Lcnt-1] = u;
        }
        for(int i=0;i<Lcnt-1;i++) {
            if(P[i].second + 1 != P[i+1].first) flag = 1;
            if(upp(P[i]) == upp(P[i+1])) flag = 1;
        }
        if(flag) cout<<-1<<'\n';
        else {
            cout<<P[0].first<<' '<<P[Lcnt-1].second<<'\n';
        }
        for(int i=0;i<Lcnt;i++) {
            //cout<<P[i].first<<' '<<P[i].second<<'\n';
        }
        //cout<<'\n';
    }
    return 0;
}

• Subtask 1: 0 / 33
• Subtask 2: 0 / 67