Submission #72437

#	Time	Username	Problem	Language	Result	Execution time	Memory
72437		김동현보다 잘함 (#118)	Easy Data Structure Problem (FXCUP3_easy)	C++17	0 / 100	5 ms	2680 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<pii> 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(pii(st[i],en[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<piii> 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(piii(lis[vec[0]][i],lis[vec[0]][i].second-lis[vec[0]][i].first));
    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<piii> tmp;
        for (b=0;b<lis[vec[i]].size();b++) {
            for (a=0;a<cur.size();a++) {
                if (cur[a].first.second+1==lis[vec[i]][b].first&&
                    lis[vec[i]][b].second-lis[vec[i]][b].first!=cur[a].second) {
                        tmp.push_back(piii(pii(cur[a].first.first,lis[vec[i]][b].second),lis[vec[i]][b].second-lis[vec[i]][b].first));
                        break;
                    }
            }
        }
        cur = tmp;
    }
    if (cur.empty()) {
        printf("-1\n");
    }
    else {
        printf("%d %d\n",cur[0].first.first+1,cur[0].first.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(piii(lis[vec[0]][i],lis[vec[0]][i].second-lis[vec[0]][i].first));
              ~^~~~~~~~~~~~~~~~~~~
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: 0 / 33
• Subtask 2: 0 / 67