oj.uz

Submission #251463

# Submission time Handle Problem Language Result Execution time Memory
251463 2020-07-21T10:15:09 Z 2qbingxuan Lollipop (POI11_liz) C++14
84 / 100
 752 ms 27664 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) 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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Liczba calkowita spoza zakresu
2 Halted 0 ms 0 KB -

Subtask #2
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 #3
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 6 ms 640 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 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 828 KB Output is correct
2 Correct 8 ms 896 KB Output is correct
3 Correct 35 ms 2040 KB Output is correct

Subtask #6
8.0 / 8.0

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

Subtask #7
0 / 8.0

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

Subtask #8
8.0 / 8.0

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

Subtask #9
9.0 / 9.0

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

Subtask #10
9.0 / 9.0

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

Subtask #11
9.0 / 9.0

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

Subtask #12
9.0 / 9.0

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