oj.uz

Submission #72448

# Submission time Handle Problem Language Result Execution time Memory
72448 2018-08-26T08:14:41 Z 김동현보다 잘함(#2226, tlwpdus) Easy Data Structure Problem (FXCUP3_easy) C++17
100 / 100
 190 ms 10396 KB 
#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

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.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Correct
2 Correct 4 ms 2792 KB Correct
3 Correct 4 ms 2868 KB Correct
4 Correct 13 ms 3072 KB Correct
5 Correct 7 ms 3072 KB Correct
6 Correct 22 ms 3072 KB Correct
7 Correct 24 ms 3072 KB Correct
8 Correct 32 ms 3072 KB Correct

Subtask #2
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Correct
2 Correct 4 ms 2792 KB Correct
3 Correct 4 ms 2868 KB Correct
4 Correct 13 ms 3072 KB Correct
5 Correct 7 ms 3072 KB Correct
6 Correct 22 ms 3072 KB Correct
7 Correct 24 ms 3072 KB Correct
8 Correct 32 ms 3072 KB Correct
9 Correct 73 ms 10052 KB Correct
10 Correct 34 ms 10052 KB Correct
11 Correct 50 ms 10052 KB Correct
12 Correct 108 ms 10052 KB Correct
13 Correct 114 ms 10052 KB Correct
14 Correct 143 ms 10136 KB Correct
15 Correct 135 ms 10268 KB Correct
16 Correct 146 ms 10396 KB Correct
17 Correct 190 ms 10396 KB Correct