Submission #632676

#	Time	Username	Problem	Language	Result	Execution time	Memory
632676		AA_Surely	Dabbeh (INOI20_dabbeh)	C++14	Compilation error	0 ms	0 KiB

Main

#define FOR(i, x, n) for(int i = x; i < n; i++)
#define F0R(i, n) FOR(i, 0, n)
#define ROF(i, x, n) for(int i = n - 1; i >= x; i--)
#define R0F(i, n) ROF(i, 0, n)

#define WTF cout << "WTF" << endl

#define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define F first
#define S second
#define PB push_back

#define ALL(x) x.begin(), x.end()
#define RALL(x) x.rbegin(), x.rend()

using namespace std;

typedef long long LL;

typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;

typedef vector<int> VI;
typedef vector<LL> VLL;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;

const int Q = 1e6 + 7;
const int N = 1e6 + 7;
const int L = 1e6 + 7;
const int MOD = 1e9 + 7;
const int LOG = 22;

#define endl '\n'
#define lc now << 1
#define rc now << 1 | 1

int q, m, n, pw, l;
int tmp[N], mid[L];
int rnk[L][LOG];
PII p[L];
string ts[Q], s, ns;

struct IntMaxSeg {
    int tree[N << 2];
 
    int build(int now = 1, int ls = 0, int rs = n) {
        if (ls == rs) return tree[now] = tmp[ls];
        int mid = (ls + rs) >> 1;
        return tree[now] = max(build(lc, ls, mid), build(rc, mid + 1, rs));
    }
 
    int get(int lq, int rq, int now = 1, int ls = 0, int rs = n) {
        if (rq < lq || rq < ls || rs < lq) return 0;
        if (lq <= ls && rs <= rq) return tree[now];
        int mid = (ls + rs) >> 1;
        return max(get(lq, rq, lc, ls, mid), get(lq, rq, rc, mid + 1, rs));
    }
} dp[LOG];

void init() {
    cin >> q >> m;
    F0R(i, q) {
        cin >> ts[i];
        ns += "#" + ts[i];
    }

    cin >> s;
    n = s.length();

    ns += "#" + s;
    l = ns.length();
}

inline bool cmp(const PII &a, const PII &b) {
    if (rnk[pw - 1][a.F] != rnk[pw - 1][b.F]) return rnk[pw - 1][a.F] < rnk[pw - 1][b.F];
    if (max(a.F, b.F) + (1 << (pw - 1)) >= l) return a.F > b.F;
    return rnk[pw - 1][a.F + (1 << (pw - 1))] < rnk[pw - 1][b.F + (1 << (pw - 1))];
}

void buildSA() {
    F0R(i, l) rnk[0][i] = ns[i];
    int c = -1;
    FOR(i, 1, l) p[i] = {i, (ns[i - 1] == '#' ? c-- : 0)};

    c = n;
    R0F(i, l) {
        if (ns[i] == '#') break;
        p[i].S = c--;
    }

    for(pw = 1; pw < LOG; pw++) {
        sort(p, p + l, cmp);

        rnk[pw][ p[0].F ] = 0;
        FOR(i, 1, l) rnk[pw][ p[i].F ] = rnk[pw][ p[i - 1].F ] + cmp(p[i - 1], p[i]);
    }
    
    return;
}

inline int lcp(int a, int b) {
    int ret = 0;
    R0F(i, LOG) {
        if (max(a, b) + (1 << i) > l + 1) continue;
        if (rnk[i][a] != rnk[i][b]) continue;

        ret |= (1 << i);
        a += (1 << i);
        b += (1 << i);
    }

    return ret;
}

void dpBase() {
    /*
    int lst = -1;
    F0R(i, l) {
        if (p[i].S < 0) 
            lst = p[i].F;
        if (p[i].S > 0 && lst != -1)
            tmp[ p[i].S - 1 ] = lcp(lst, p[i].F);
    }

    lst = -1;
    R0F(i, l) {
        if (p[i].S < 0) 
            lst = p[i].F;
        if (p[i].S > 0 && lst != -1) 
            tmp[ p[i].S - 1 ] = max(tmp[ p[i].S - 1], lcp(lst, p[i].F));
    }*/

    //F0R(i, n) cout << tmp[i] << ' '; cout << endl;

    F0R(i, l) if (p[i].S > 0) F0R(j, l) if (p[j].S < 0) {
        tmp[ p[i].S - 1 ] = max(tmp[ p[i].S - 1 ], lcp(p[i].F, p[j].F));
    }

    F0R(i, n) tmp[i] += i;
    dp[0].build();

    return;
}

void calcLayer(int id) {
    F0R(i, n + 1) {
        int x = dp[id - 1].get(i, i);
        tmp[i] = dp[id - 1].get(i, x);
    }
 
    dp[id].build();
}
 
void handleQuery() {
    int ll, r; 
    cin >> ll >> r;
    r--;
 
    int now = ll, sum = 0;
    if (dp[LOG - 1].get(ll, ll) <= r) {
        cout << -1 << endl;
        return;
    }
 
    R0F(i, LOG) {
        int x = dp[i].get(ll, now);
        if (x <= r) {
            sum += (1 << i);
            now = x;
        }
    }
    
    cout << sum + 1 << endl;
}
 
int main() {
    IOS;
 
    init();
 
    buildSA();
    dpBase();
 
    FOR(i, 1, LOG) calcLayer(i);
    while(m--) handleQuery();
 
    return 0;
}

Compilation message (stderr)

Main.cpp:21:9: error: 'pair' does not name a type
   21 | typedef pair<int, int> PII;
      |         ^~~~
Main.cpp:22:9: error: 'pair' does not name a type
   22 | typedef pair<LL, LL> PLL;
      |         ^~~~
Main.cpp:24:9: error: 'vector' does not name a type
   24 | typedef vector<int> VI;
      |         ^~~~~~
Main.cpp:25:9: error: 'vector' does not name a type
   25 | typedef vector<LL> VLL;
      |         ^~~~~~
Main.cpp:26:9: error: 'vector' does not name a type
   26 | typedef vector<PII> VPII;
      |         ^~~~~~
Main.cpp:27:9: error: 'vector' does not name a type
   27 | typedef vector<PLL> VPLL;
      |         ^~~~~~
Main.cpp:42:1: error: 'PII' does not name a type
   42 | PII p[L];
      | ^~~
Main.cpp:43:1: error: 'string' does not name a type
   43 | string ts[Q], s, ns;
      | ^~~~~~
Main.cpp: In member function 'int IntMaxSeg::build(int, int, int)':
Main.cpp:51:28: error: 'max' was not declared in this scope
   51 |         return tree[now] = max(build(lc, ls, mid), build(rc, mid + 1, rs));
      |                            ^~~
Main.cpp: In member function 'int IntMaxSeg::get(int, int, int, int, int)':
Main.cpp:58:16: error: 'max' was not declared in this scope
   58 |         return max(get(lq, rq, lc, ls, mid), get(lq, rq, rc, mid + 1, rs));
      |                ^~~
Main.cpp: In function 'void init()':
Main.cpp:63:5: error: 'cin' was not declared in this scope
   63 |     cin >> q >> m;
      |     ^~~
Main.cpp:1:1: note: 'std::cin' is defined in header '<iostream>'; did you forget to '#include <iostream>'?
  +++ |+#include <iostream>
    1 | 
Main.cpp:65:16: error: 'ts' was not declared in this scope
   65 |         cin >> ts[i];
      |                ^~
Main.cpp:66:9: error: 'ns' was not declared in this scope; did you mean 'n'?
   66 |         ns += "#" + ts[i];
      |         ^~
      |         n
Main.cpp:69:12: error: 's' was not declared in this scope
   69 |     cin >> s;
      |            ^
Main.cpp:72:5: error: 'ns' was not declared in this scope; did you mean 'n'?
   72 |     ns += "#" + s;
      |     ^~
      |     n
Main.cpp: At global scope:
Main.cpp:76:23: error: 'PII' does not name a type
   76 | inline bool cmp(const PII &a, const PII &b) {
      |                       ^~~
Main.cpp:76:37: error: 'PII' does not name a type
   76 | inline bool cmp(const PII &a, const PII &b) {
      |                                     ^~~
Main.cpp: In function 'bool cmp(const int&, const int&)':
Main.cpp:10:11: error: request for member 'first' in 'a', which is of non-class type 'const int'
   10 | #define F first
      |           ^~~~~
Main.cpp:77:23: note: in expansion of macro 'F'
   77 |     if (rnk[pw - 1][a.F] != rnk[pw - 1][b.F]) return rnk[pw - 1][a.F] < rnk[pw - 1][b.F];
      |                       ^
Main.cpp:10:11: error: request for member 'first' in 'b', which is of non-class type 'const int'
   10 | #define F first
      |           ^~~~~
Main.cpp:77:43: note: in expansion of macro 'F'
   77 |     if (rnk[pw - 1][a.F] != rnk[pw - 1][b.F]) return rnk[pw - 1][a.F] < rnk[pw - 1][b.F];
      |                                           ^
Main.cpp:10:11: error: request for member 'first' in 'a', which is of non-class type 'const int'
   10 | #define F first
      |           ^~~~~
Main.cpp:77:68: note: in expansion of macro 'F'
   77 |     if (rnk[pw - 1][a.F] != rnk[pw - 1][b.F]) return rnk[pw - 1][a.F] < rnk[pw - 1][b.F];
      |                                                                    ^
Main.cpp:10:11: error: request for member 'first' in 'b', which is of non-class type 'const int'
   10 | #define F first
      |           ^~~~~
Main.cpp:77:87: note: in expansion of macro 'F'
   77 |     if (rnk[pw - 1][a.F] != rnk[pw - 1][b.F]) return rnk[pw - 1][a.F] < rnk[pw - 1][b.F];
      |                                                                                       ^
Main.cpp:10:11: error: request for member 'first' in 'a', which is of non-class type 'const int'
   10 | #define F first
      |           ^~~~~
Main.cpp:78:15: note: in expansion of macro 'F'
   78 |     if (max(a.F, b.F) + (1 << (pw - 1)) >= l) return a.F > b.F;
      |               ^
Main.cpp:10:11: error: request for member 'first' in 'b', which is of non-class type 'const int'
   10 | #define F first
      |           ^~~~~
Main.cpp:78:20: note: in expansion of macro 'F'
   78 |     if (max(a.F, b.F) + (1 << (pw - 1)) >= l) return a.F > b.F;
      |                    ^
Main.cpp:78:9: error: 'max' was not declared in this scope
   78 |     if (max(a.F, b.F) + (1 << (pw - 1)) >= l) return a.F > b.F;
      |         ^~~
Main.cpp:10:11: error: request for member 'first' in 'a', which is of non-class type 'const int'
   10 | #define F first
      |           ^~~~~
Main.cpp:78:56: note: in expansion of macro 'F'
   78 |     if (max(a.F, b.F) + (1 << (pw - 1)) >= l) return a.F > b.F;
      |                                                        ^
Main.cpp:10:11: error: request for member 'first' in 'b', which is of non-class type 'const int'
   10 | #define F first
      |           ^~~~~
Main.cpp:78:62: note: in expansion of macro 'F'
   78 |     if (max(a.F, b.F) + (1 << (pw - 1)) >= l) return a.F > b.F;
      |                                                              ^
Main.cpp:10:11: error: request for member 'first' in 'a', which is of non-class type 'const int'
   10 | #define F first
      |           ^~~~~
Main.cpp:79:26: note: in expansion of macro 'F'
   79 |     return rnk[pw - 1][a.F + (1 << (pw - 1))] < rnk[pw - 1][b.F + (1 << (pw - 1))];
      |                          ^
Main.cpp:10:11: error: request for member 'first' in 'b', which is of non-class type 'const int'
   10 | #define F first
      |           ^~~~~
Main.cpp:79:63: note: in expansion of macro 'F'
   79 |     return rnk[pw - 1][a.F + (1 << (pw - 1))] < rnk[pw - 1][b.F + (1 << (pw - 1))];
      |                                                               ^
Main.cpp: In function 'void buildSA()':
Main.cpp:83:27: error: 'ns' was not declared in this scope; did you mean 'n'?
   83 |     F0R(i, l) rnk[0][i] = ns[i];
      |                           ^~
      |                           n
Main.cpp:85:18: error: 'p' was not declared in this scope
   85 |     FOR(i, 1, l) p[i] = {i, (ns[i - 1] == '#' ? c-- : 0)};
      |                  ^
Main.cpp:85:30: error: 'ns' was not declared in this scope; did you mean 'n'?
   85 |     FOR(i, 1, l) p[i] = {i, (ns[i - 1] == '#' ? c-- : 0)};
      |                              ^~
      |                              n
Main.cpp:89:13: error: 'ns' was not declared in this scope; did you mean 'n'?
   89 |         if (ns[i] == '#') break;
      |             ^~
      |             n
Main.cpp:90:9: error: 'p' was not declared in this scope
   90 |         p[i].S = c--;
      |         ^
Main.cpp:94:14: error: 'p' was not declared in this scope
   94 |         sort(p, p + l, cmp);
      |              ^
Main.cpp:94:9: error: 'sort' was not declared in this scope; did you mean 'short'?
   94 |         sort(p, p + l, cmp);
      |         ^~~~
      |         short
Main.cpp: In function 'int lcp(int, int)':
Main.cpp:106:13: error: 'max' was not declared in this scope
  106 |         if (max(a, b) + (1 << i) > l + 1) continue;
      |             ^~~
Main.cpp: In function 'void dpBase()':
Main.cpp:137:19: error: 'p' was not declared in this scope
  137 |     F0R(i, l) if (p[i].S > 0) F0R(j, l) if (p[j].S < 0) {
      |                   ^
Main.cpp:138:29: error: 'max' was not declared in this scope
  138 |         tmp[ p[i].S - 1 ] = max(tmp[ p[i].S - 1 ], lcp(p[i].F, p[j].F));
      |                             ^~~
Main.cpp: In function 'void handleQuery()':
Main.cpp:158:5: error: 'cin' was not declared in this scope
  158 |     cin >> ll >> r;
      |     ^~~
Main.cpp:158:5: note: 'std::cin' is defined in header '<iostream>'; did you forget to '#include <iostream>'?
Main.cpp:163:9: error: 'cout' was not declared in this scope
  163 |         cout << -1 << endl;
      |         ^~~~
Main.cpp:163:9: note: 'std::cout' is defined in header '<iostream>'; did you forget to '#include <iostream>'?
Main.cpp:175:5: error: 'cout' was not declared in this scope
  175 |     cout << sum + 1 << endl;
      |     ^~~~
Main.cpp:175:5: note: 'std::cout' is defined in header '<iostream>'; did you forget to '#include <iostream>'?
Main.cpp: In function 'int main()':
Main.cpp:9:13: error: 'ios_base' has not been declared
    9 | #define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
      |             ^~~~~~~~
Main.cpp:179:5: note: in expansion of macro 'IOS'
  179 |     IOS;
      |     ^~~
Main.cpp:9:43: error: 'cin' was not declared in this scope
    9 | #define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
      |                                           ^~~
Main.cpp:179:5: note: in expansion of macro 'IOS'
  179 |     IOS;
      |     ^~~
Main.cpp:9:43: note: 'std::cin' is defined in header '<iostream>'; did you forget to '#include <iostream>'?
    9 | #define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
      |                                           ^~~
Main.cpp:179:5: note: in expansion of macro 'IOS'
  179 |     IOS;
      |     ^~~
Main.cpp:9:55: error: 'cout' was not declared in this scope
    9 | #define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
      |                                                       ^~~~
Main.cpp:179:5: note: in expansion of macro 'IOS'
  179 |     IOS;
      |     ^~~
Main.cpp:9:55: note: 'std::cout' is defined in header '<iostream>'; did you forget to '#include <iostream>'?
    9 | #define IOS ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
      |                                                       ^~~~
Main.cpp:179:5: note: in expansion of macro 'IOS'
  179 |     IOS;
      |     ^~~