oj.uz

Submission #72158

# Submission time Handle Problem Language Result Execution time Memory
72158 2018-08-26T05:37:38 Z IDxTree(#2155, TAMREF, imeimi2000, Diuven) Easy Data Structure Problem (FXCUP3_easy) C++17
100 / 100
 139 ms 13672 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

int n;
int arr[100001];
int rev[100001];
int sz = 1;
int idx[1 << 18];
int st[1 << 18];
int ed[1 << 18];
int hi[1 << 18];

int contain(int x, int y) {
    return st[x] <= st[y] && ed[y] <= ed[x];
}

int check(const vector<int> &qs, int s, int e) {
    s += sz; e += sz;
    vector<int> ans;
    while (s <= e) {
        if ((s & 1) == 1) ans.push_back(idx[s++]);
        if ((e & 1) == 0) ans.push_back(idx[e--]);
        s >>= 1; e >>= 1;
    }
    sort(ans.begin(), ans.end(), [&](int i, int j) { return rev[i] < rev[j]; });
    ans.erase(unique(ans.begin(), ans.end()), ans.end());
    if (qs.size() != ans.size()) return 0;
    for (int i = 0; i < qs.size(); ++i) {
        if (qs[i] != ans[i]) return 0;
    }
    return 1;
}

pii calc() {
    vector<int> qs;
    int c;
    scanf("%d", &c);
    for (int i = 0; i < c; ++i) {
        int x;
        scanf("%d", &x);
        qs.push_back(x);
    }
    sort(qs.begin(), qs.end(), [&](int i, int j) { return rev[i] < rev[j]; });
    
    vector<int> nd(c);
    for (int i = 0; i < c; ++i) {
        int tp = rev[qs[i]] + sz;
        while (tp > 1) {
            int nxt = tp >> 1;
            if (idx[nxt] != idx[tp]) break;
            if (i && contain(nxt, rev[qs[i - 1]] + sz)) break;
            if (i + 1 < c && contain(nxt, rev[qs[i + 1]] + sz)) break;
            tp = nxt;
        }
        nd[i] = tp;
        for (int j = i; j--; ) {
            int x = rev[qs[j]] + sz;
            while (x > 1) {
                int nxt = x >> 1;
                if (idx[nxt] != idx[x]) break;
                if (hi[nd[j + 1]] < hi[nxt]) break;
                if (nd[j + 1] == (nxt ^ 1)) break;
                if (j && contain(nxt, rev[qs[j - 1]] + sz)) break;
                x = nxt;
            }
            nd[j] = x;
        }
        
        for (int j = i + 1; j < c; ++j) {
            int x = rev[qs[j]] + sz;
            while (x > 1) {
                int nxt = x >> 1;
                if (idx[nxt] != idx[x]) break;
                if (hi[nd[j - 1]] < hi[nxt]) break;
                if (nd[j - 1] == (nxt ^ 1)) break;
                if (j + 1 < c && contain(nxt, rev[qs[j + 1]] + sz)) break;
                x = nxt;
            }
            nd[j] = x;
        }
        int s = st[nd[0]], e = ed[nd[c - 1]];
        if (check(qs, s, e)) return pii(s, e);
    }
    return pii(-1, -1);

}

int main() {
    int q;
    scanf("%d%d", &n, &q);
    for (int i = 0; i < n; ++i) {
        scanf("%d", arr + i);
        rev[arr[i]] = i;
    }
    while (sz < n) sz <<= 1;
    for (int i = 0; i < n; ++i) idx[i + sz] = arr[i];
    for (int i = sz; --i; ) idx[i] = min(idx[i << 1], idx[i << 1 | 1]);
    
    for (int i = 0; i < sz; ++i) st[i + sz] = ed[i + sz] = i;
    for (int i = sz; --i; ) {
        st[i] = st[i << 1];
        ed[i] = ed[i << 1 | 1];
        hi[i] = hi[i << 1] + 1;
    }
    
    for (int i = 0; i < q; ++i) {
        int x, y;
        tie(x, y) = calc();
        if (x != -1) printf("%d %d\n", x + 1, y + 1);
        else printf("-1\n");
    }
 	return 0;
}

Compilation message

easy.cpp: In function 'int check(const std::vector<int>&, int, int)':
easy.cpp:45:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < qs.size(); ++i) {
                     ~~^~~~~~~~~~~
easy.cpp: In function 'pii calc()':
easy.cpp:54:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &c);
     ~~~~~^~~~~~~~~~
easy.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
         ~~~~~^~~~~~~~~~
easy.cpp: In function 'int main()':
easy.cpp:107:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &q);
     ~~~~~^~~~~~~~~~~~~~~~
easy.cpp:109:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", arr + i);
         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Correct
2 Correct 2 ms 484 KB Correct
3 Correct 4 ms 484 KB Correct
4 Correct 26 ms 728 KB Correct
5 Correct 6 ms 728 KB Correct
6 Correct 30 ms 820 KB Correct
7 Correct 18 ms 976 KB Correct
8 Correct 43 ms 1132 KB Correct

Subtask #2
67.0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Correct
2 Correct 2 ms 484 KB Correct
3 Correct 4 ms 484 KB Correct
4 Correct 26 ms 728 KB Correct
5 Correct 6 ms 728 KB Correct
6 Correct 30 ms 820 KB Correct
7 Correct 18 ms 976 KB Correct
8 Correct 43 ms 1132 KB Correct
9 Correct 42 ms 5900 KB Correct
10 Correct 48 ms 5900 KB Correct
11 Correct 51 ms 5900 KB Correct
12 Correct 95 ms 6024 KB Correct
13 Correct 105 ms 6848 KB Correct
14 Correct 139 ms 10060 KB Correct
15 Correct 104 ms 11284 KB Correct
16 Correct 105 ms 12580 KB Correct
17 Correct 101 ms 13672 KB Correct