Submission #72448

#	Time	Username	Problem	Language	Result	Execution time	Memory
72448		김동현보다 잘함 (#118)	Easy Data Structure Problem (FXCUP3_easy)	C++17	100 / 100	190 ms	10396 KiB

easy

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii,int> piii;
typedef pair<ll,ll> pll;

int INF = 1e8;
int n, m;
int tree[270000], key;
int st[270000], en[270000];
vector<int> lis[100100];
void init() {
    int i;
    for (key=1;key<n;key*=2);
    for (i=1;i<key*2;i++) tree[i] = INF;
    for (i=key;i<key*2;i++) st[i] = en[i] = i-key;
    for (i=key-1;i;i--) {
        st[i] = min(st[i*2],st[i*2+1]);
        en[i] = max(en[i*2],en[i*2+1]);
    }
}
void upd(int idx, int val) {
    idx += key;
    while(idx) {
        tree[idx] = min(tree[idx],val);
        idx/=2;
    }
}
void calc() {
    int i;
    for (i=1;i<key+n;i++) {
        if (en[i]<n) lis[tree[i]].push_back(i);
    }
    for (i=0;i<n;i++) {
        sort(lis[i].begin(),lis[i].end());
        //printf("%d : ",i);
        //for (pii &v :lis[i]) printf("%d, %d  ",v.first, v.second);
        //printf("\n");
    }
}

int arr[100100];
int loc[100100];
vector<int> vec;
vector<pii> cur;

void solve() {
    cur.clear();
    sort(vec.begin(),vec.end(),[](int a, int b){return loc[a]<loc[b];});
    int i, a, b;
    for (i=0;i<lis[vec[0]].size();i++) cur.push_back(pii(lis[vec[0]][i],lis[vec[0]][i]));
    for (i=1;i<vec.size();i++) {
        //sort(cur.begin(),cur.end(),[](pii a, pii b){return a.second<b.second;});
        a = b = 0;
        vector<pii> tmp;
        for (b=0;b<lis[vec[i]].size();b++) {
            for (a=0;a<cur.size();a++) {
                if (en[cur[a].second]+1==st[lis[vec[i]][b]]&&
                    (cur[a].second^1)!=lis[vec[i]][b]) {
                        tmp.push_back(pii(cur[a].first,lis[vec[i]][b]));
                        break;
                    }
            }
        }
        cur = tmp;
    }
    if (cur.empty()) {
        printf("-1\n");
    }
    else {
        printf("%d %d\n",st[cur[0].first]+1,en[cur[0].second]+1);
    }
}

int main() {
    int i, j;

    scanf("%d%d",&n,&m);
    init();
    for (i=0;i<n;i++) {
        scanf("%d",&arr[i]); arr[i]--;
        loc[arr[i]] = i;
        upd(i,arr[i]);
    }
    calc();
    for (i=0;i<m;i++) {
        int c;
        scanf("%d",&c);
        vec.clear();
        for (j=0;j<c;j++) {
            int a;
            scanf("%d",&a); --a;
            vec.push_back(a);
        }
        solve();
    }

    return 0;
}

Compilation message (stderr)

easy.cpp: In function 'void solve()':
easy.cpp:54:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<lis[vec[0]].size();i++) cur.push_back(pii(lis[vec[0]][i],lis[vec[0]][i]));
              ~^~~~~~~~~~~~~~~~~~~
easy.cpp:55:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=1;i<vec.size();i++) {
              ~^~~~~~~~~~~
easy.cpp:59:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (b=0;b<lis[vec[i]].size();b++) {
                  ~^~~~~~~~~~~~~~~~~~~
easy.cpp:60:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (a=0;a<cur.size();a++) {
                      ~^~~~~~~~~~~
easy.cpp: In function 'int main()':
easy.cpp:81:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~
easy.cpp:84:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&arr[i]); arr[i]--;
         ~~~~~^~~~~~~~~~~~~~
easy.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&c);
         ~~~~~^~~~~~~~~
easy.cpp:95:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&a); --a;
             ~~~~~^~~~~~~~~

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