oj.uz

Submission #251465

# Submission time Handle Problem Language Result Execution time Memory
251465 2020-07-21T10:19:23 Z 2qbingxuan Lollipop (POI11_liz) C++14
100 / 100
 804 ms 23828 KB 
//   __________________
//  | ________________ |
//  ||          ____  ||
//  ||   /\    |      ||
//  ||  /__\   |      ||
//  || /    \  |____  ||
//  ||________________||
//  |__________________|
//  \###################\
//   \###################\
//    \        ____       \
//     \_______\___\_______\
// 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 || sum[R+1] - sum[L] != k) 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
                                                       ~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory 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

Subtask #2
8.0 / 8.0

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

Subtask #3
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 7 ms 640 KB Output is correct

Subtask #4
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 4 ms 512 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 8 ms 896 KB Output is correct
2 Correct 9 ms 896 KB Output is correct
3 Correct 35 ms 1656 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 1784 KB Output is correct
2 Correct 152 ms 4344 KB Output is correct
3 Correct 74 ms 2936 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 2040 KB Output is correct
2 Correct 32 ms 2040 KB Output is correct
3 Correct 86 ms 4728 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 4344 KB Output is correct
2 Correct 121 ms 3960 KB Output is correct
3 Correct 171 ms 6536 KB Output is correct

Subtask #9
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 322 ms 9960 KB Output is correct
2 Correct 293 ms 9356 KB Output is correct
3 Correct 371 ms 12940 KB Output is correct

Subtask #10
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 11404 KB Output is correct
2 Correct 379 ms 13068 KB Output is correct
3 Correct 482 ms 16144 KB Output is correct

Subtask #11
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 691 ms 22136 KB Output is correct
2 Correct 480 ms 20492 KB Output is correct
3 Correct 793 ms 21664 KB Output is correct

Subtask #12
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 670 ms 22288 KB Output is correct
2 Correct 804 ms 22544 KB Output is correct
3 Correct 488 ms 23828 KB Output is correct