Submission #251468

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
251468	2020-07-21T10:42:59 Z	2qbingxuan	Lollipop (POI11_liz)	C++14	100 / 100	558 ms	31504 KB

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1000025;
int n, q, v[N], sum[N];
int Z[N], lb[N*2];
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    string s;
    cin >> n >> q >> s;
    for(int i = 0; i < n; i++) v[i] = (s[i]=='T' ? 2 : 1);
    for(int i = 0; i < n; i++) sum[i+1] = sum[i] + v[i];
    for(int i = 1, j = 0; i <= n*2; i++) {
        while(j < n && sum[j] < i) ++j;
        lb[i] = j;
    }
    for(int i = 1, j = 0, r = 0; i < n; i++) {
        Z[i] = max(0, min(r-i, Z[i-j]));
        while(i+Z[i] < n && v[Z[i]] == v[i+Z[i]]) ++Z[i];
        if(i+Z[i] > r) j = i, r = i+Z[i];
    }
    Z[0] = n;
    while(q--) {
        int k;
        cin >> k;
        int x = lb[k];
        if(sum[x] == k) cout << 1 << ' ' << x << '\n';
        else {
            // sum[x] == k+1
            int L = Z[x]; // v[0:Z[x]-1] = v[x:x+Z[x]-1]
            // v[Z[x]] != v[x+Z[x]]
            int R = x+Z[x];
            /* debug(L, R); */
            if(v[L] == 1)
                --R;
            ++L;
            if(R >= n || sum[R+1] - sum[L] != k) cout << "NIE\n";
            else cout << L+1 << ' ' << R+1 << '\n';
        }
    }
}

Subtask #1
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct

Subtask #2
8.0 / 8.0

#	Verdict	Memory	Grader output
1	Correct	384 KB	Output is correct
2	Correct	384 KB	Output is correct
3	Correct	384 KB	Output is correct

Subtask #3
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	256 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	5 ms	512 KB	Output is correct

Subtask #4
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	512 KB	Output is correct
2	Correct	3 ms	640 KB	Output is correct
3	Correct	4 ms	640 KB	Output is correct

Subtask #5
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	7 ms	896 KB	Output is correct
2	Correct	7 ms	896 KB	Output is correct
3	Correct	27 ms	1656 KB	Output is correct

Subtask #6
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	25 ms	2168 KB	Output is correct
2	Correct	118 ms	4728 KB	Output is correct
3	Correct	64 ms	3192 KB	Output is correct

Subtask #7
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	23 ms	2432 KB	Output is correct
2	Correct	25 ms	2560 KB	Output is correct
3	Correct	60 ms	4088 KB	Output is correct

Subtask #8
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	100 ms	5196 KB	Output is correct
2	Correct	83 ms	4600 KB	Output is correct
3	Correct	131 ms	7556 KB	Output is correct

Subtask #9
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	226 ms	12172 KB	Output is correct
2	Correct	260 ms	11660 KB	Output is correct
3	Correct	319 ms	15756 KB	Output is correct

Subtask #10
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	226 ms	15200 KB	Output is correct
2	Correct	255 ms	16908 KB	Output is correct
3	Correct	357 ms	20752 KB	Output is correct

Subtask #11
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	529 ms	29000 KB	Output is correct
2	Correct	362 ms	27176 KB	Output is correct
3	Correct	518 ms	28432 KB	Output is correct

Subtask #12
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	558 ms	29940 KB	Output is correct
2	Correct	519 ms	30100 KB	Output is correct
3	Correct	359 ms	31504 KB	Output is correct

Submission #251468

Compilation message