// __________________
// | ________________ |
// || ____ ||
// || /\ | ||
// || /__\ | ||
// || / \ |____ ||
// ||________________||
// |__________________|
// \###################\
// \###################\
// \ ____ \
// \_______\___\_______\
// An AC a day keeps the doctor away.
#pragma GCC optimize("Ofast")
#pragma loop_opt(on)
#include <bits/extc++.h>
#ifdef local
#define safe std::cerr<<__PRETTY_FUNCTION__<<" line "<<__LINE__<<" safe\n"
#define debug(...) qqbx(#__VA_ARGS__, __VA_ARGS__)
template <typename H, typename ...T> constexpr void qqbx(const char *s, const H &h, T &&...args) {
for(; *s && *s != ','; ++s) if(*s != ' ') std::cerr << *s;
std::cerr << " = " << h << (sizeof...(T) ? ", " : "\n");
if constexpr(sizeof...(T)) qqbx(++s, args...); // C++ 17!
}
#else
#include <bits/stdc++.h>
#define debug(...) ((void)0)
#define safe ((void)0)
#endif // local
#define all(v) begin(v),end(v)
#define get_pos(v,x) int(lower_bound(begin(v),end(v),x)-begin(v))
#define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v))
#define pb emplace_back
#define ff first
#define ss second
#define mem(v,x) memset(v,x,sizeof v)
using namespace std;
using namespace __gnu_pbds;
typedef int64_t ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pld;
template <typename T> using max_heap = std::priority_queue<T,vector<T>,less<T> >;
template <typename T> using min_heap = std::priority_queue<T,vector<T>,greater<T> >;
template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
constexpr ld PI = acos(-1), eps = 1e-9;
constexpr ll N = 1000025, INF = 1e18, MOD = 1000000007, K = 125, inf = 1e9;
constexpr inline ll cdiv(ll x, ll m) { return x/m + ((x<0 ^ m>0) && (x%m)); } // ceiling divide
constexpr inline ll modpow(ll e,ll p,ll m=MOD) { ll r=1; for(e%=m;p;p>>=1,e=e*e%m) if(p&1) r=r*e%m; return r; }
int n, q, v[N], sum[N];
int Z[N];
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, 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 = 0;
for(int s = 1<<20; s; s>>=1) if(x+s < n && sum[x+s] < k) x += s;
++x;
// len == x
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) cout << "NIE\n";
else cout << L+1 << ' ' << R+1 << '\n';
}
}
}
Compilation message
liz.cpp:9:1: warning: multi-line comment [-Wcomment]
// \###################\
^
liz.cpp:16:0: warning: ignoring #pragma loop_opt [-Wunknown-pragmas]
#pragma loop_opt(on)
liz.cpp: In function 'constexpr ll cdiv(ll, ll)':
liz.cpp:50:56: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
constexpr inline ll cdiv(ll x, ll m) { return x/m + ((x<0 ^ m>0) && (x%m)); } // ceiling divide
~^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
384 KB |
Liczba calkowita spoza zakresu |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
6 ms |
640 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
512 KB |
Output is correct |
2 |
Correct |
4 ms |
512 KB |
Output is correct |
3 |
Correct |
4 ms |
640 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
8 ms |
828 KB |
Output is correct |
2 |
Correct |
8 ms |
896 KB |
Output is correct |
3 |
Correct |
35 ms |
2040 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
36 ms |
1784 KB |
Output is correct |
2 |
Correct |
152 ms |
6648 KB |
Output is correct |
3 |
Correct |
79 ms |
4088 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
31 ms |
1920 KB |
Output is correct |
2 |
Incorrect |
50 ms |
2832 KB |
Oczekiwano 'NIE', otrzymano przedzial |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
127 ms |
4216 KB |
Output is correct |
2 |
Correct |
107 ms |
5752 KB |
Output is correct |
3 |
Correct |
180 ms |
9220 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
306 ms |
9736 KB |
Output is correct |
2 |
Correct |
286 ms |
13580 KB |
Output is correct |
3 |
Correct |
382 ms |
17932 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
303 ms |
11404 KB |
Output is correct |
2 |
Correct |
367 ms |
18056 KB |
Output is correct |
3 |
Correct |
478 ms |
21648 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
707 ms |
21904 KB |
Output is correct |
2 |
Correct |
535 ms |
26036 KB |
Output is correct |
3 |
Correct |
752 ms |
25620 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
644 ms |
22160 KB |
Output is correct |
2 |
Correct |
695 ms |
26344 KB |
Output is correct |
3 |
Correct |
504 ms |
27664 KB |
Output is correct |