oj.uz

Submission #251461

# Submission time Handle Problem Language Result Execution time Memory
251461 2020-07-21T10:10:30 Z 2qbingxuan Lollipop (POI11_liz) C++14
0 / 100
 697 ms 27764 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];
    }
    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
            --x; // x is 0-base now
            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] == 2)
                ++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)

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
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 Incorrect 0 ms 384 KB Oczekiwano przedzialu o koszcie 62 otrzymano przedzial wartosci 61

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 512 KB Oczekiwano przedzial, otrzymano 'NIE'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 512 KB Oczekiwano przedzialu o koszcie 7693 otrzymano przedzial wartosci 7692
2 Halted 0 ms 0 KB -

Subtask #5
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 896 KB Oczekiwano przedzialu o koszcie 31964 otrzymano przedzial wartosci 31963
2 Halted 0 ms 0 KB -

Subtask #6
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 2292 KB Oczekiwano przedzialu o koszcie 50189 otrzymano przedzial wartosci 50188
2 Halted 0 ms 0 KB -

Subtask #7
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 2424 KB Oczekiwano przedzialu o koszcie 76689 otrzymano przedzial wartosci 76688
2 Halted 0 ms 0 KB -

Subtask #8
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 128 ms 6212 KB Oczekiwano przedzialu o koszcie 151261 otrzymano przedzial wartosci 151260
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 337 ms 14092 KB Oczekiwano przedzialu o koszcie 259779 otrzymano przedzial wartosci 259778
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 329 ms 15156 KB Oczekiwano przedzialu o koszcie 8939 otrzymano przedzial wartosci 8938
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 697 ms 27764 KB Oczekiwano przedzialu o koszcie 8015 otrzymano przedzial wartosci 8014
2 Halted 0 ms 0 KB -

Subtask #12
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 685 ms 27756 KB Oczekiwano przedzialu o koszcie 1457821 otrzymano przedzial wartosci 1457820
2 Halted 0 ms 0 KB -