Submission #72422

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
72422	2018-08-26T08:01:45 Z	김동현보다 잘함(#2226, tlwpdus)	Easy Data Structure Problem (FXCUP3_easy)	C++17	0 / 100	5 ms	2680 KB

easy

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
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<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(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;
        while(a<cur.size()&&b<lis[vec[i]].size()) {
            if (cur[a].second+1<lis[vec[i]][b].first) a++;
            else if (cur[a].second+1>lis[vec[i]][b].first) b++;
            else {
                tmp.push_back(pii(cur[a].first,lis[vec[i]][b].second));
                b++;
            }
        }
        cur = tmp;
    }
    if (cur.empty()) {
        printf("-1\n");
    }
    else {
        printf("%d %d\n",cur[0].first+1,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

easy.cpp: In function 'void solve()':
easy.cpp:53:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=0;i<lis[vec[0]].size();i++) cur.push_back(lis[vec[0]][i]);
              ~^~~~~~~~~~~~~~~~~~~
easy.cpp:54:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (i=1;i<vec.size();i++) {
              ~^~~~~~~~~~~
easy.cpp:58:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(a<cur.size()&&b<lis[vec[i]].size()) {
               ~^~~~~~~~~~~
easy.cpp:58:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(a<cur.size()&&b<lis[vec[i]].size()) {
                             ~^~~~~~~~~~~~~~~~~~~
easy.cpp: In function 'int main()':
easy.cpp:79: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:82: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:89:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&c);
         ~~~~~^~~~~~~~~
easy.cpp:93: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.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	2680 KB	Correct
2	Incorrect	4 ms	2680 KB	Wrong
3	Halted	0 ms	0 KB	-

Subtask #2

0 / 67.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	2680 KB	Correct
2	Incorrect	4 ms	2680 KB	Wrong
3	Halted	0 ms	0 KB	-