oj.uz

Submission #727347

# Submission time Handle Problem Language Result Execution time Memory
727347 2023-04-20T12:34:39 Z TB_ Brunhilda’s Birthday (BOI13_brunhilda) C++17
0 / 100
 493 ms 262144 KB 
#include <bits/stdc++.h>
using namespace std;

// #undef _GLIBCXX_DEBUG                // disable run-time bound checking, etc
// #pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
// #pragma GCC optimize ("unroll-loops")

// #pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
// #pragma GCC target("movbe")                                      // byte swap
// #pragma GCC target("aes,pclmul,rdrnd")                           // encryption
// #pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2") // SIMD

// #include <bits/extc++.h>
// using namespace __gnu_pbds;
// template<class T>using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
// template<class T>using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define ll long long
#define INF (ll)1e9+7
#define fo(i, n) for(int i=0;i<(int)n;i++)
#define Fo(i, k, n) for(i=k;k<n?i<n:i>n;k<n?i+=1:i-=1)
#define deb(x) cout << #x << " = " << x << endl;
#define deb2(x, y) cout << #x << " = " << x << ", " << #y << " = " << y << endl
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define LSOne(S) ((S) & (-S))
#define sp(x, y) fixed<<setprecision(y)<<x
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define clr(x) memset(x, 0, sizeof(x))
#define tr(it, x) for(auto it = x.begin(); it != x.end(); it++)
#define trr(it, x) for(auto it = x.rbegin(); it != x.rend(); it+)
inline int readint(){ int v = 0; char c; while((c = getchar()) != EOF && c != ' ' && c != '\n'){ v *= 10; v += c - '0'; } return v; }
inline int readintsigned() { int v = 0; int sign = 1; char c = getchar(); if (c == '-') { sign = -1; } else { v += c - '0'; } while ((c = getchar()) != EOF && c != ' ' && c != '\n') { v *= 10; v += c - '0'; } return v * sign; }
inline string readstring() { string s; char c; while ((c = getchar()) != EOF && c != '\n' && c != ' ') { s.push_back(c); } return s; }
template <class result_t=std::chrono::milliseconds,class clock_t=std::chrono::steady_clock,class duration_t = std::chrono::milliseconds>
auto since(std::chrono::time_point<clock_t, duration_t> const& start){return std::chrono::duration_cast<result_t>(clock_t::now() - start);}
typedef pair<int, int> pii;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpii;
typedef vector<pl> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vpii> vvpii;
typedef vector<vpl> vvpl;

struct Node{ // borde testa att bara ha med noder som behövs
    int lo, hi, val = INF, rset = INF;
    Node *lnode, *rnode; 
    Node(int lo, int hi) : lo(lo), hi(hi){
        if(hi-lo != 1){
            int mid = (hi+lo) / 2;
            lnode = new Node(lo, mid);
            rnode = new Node(mid, hi);
        }
    }

    void update(int l, int r, int x){
        if(hi <= l || r <= lo) return;
        if(hi <= r && l <= lo) {
            rset = min(rset, x);
            val = min(val, rset);
            return;
        }
        push();
        lnode->update(l, r, x); rnode->update(l, r, x);
    }

    int query(int l, int r){
        if(hi <= l || r <= lo) return 0;
        if(hi <= r && l <= lo) {
            return val = min(val, rset);
        }
        push();
        return max(lnode->query(l, r), rnode->query(l, r));
    }

    void push(){
        if(rset != INF){
            val = min(val, rset);
            lnode->rset = min(lnode->rset, rset);
            rnode->rset = min(rnode->rset, rset);
            rset = INF;
        }
    }
    
};

int main() {
    // cout << fixed << setprecision(20);
    // auto start = std::chrono::steady_clock::now(); // since(start).count()
    cin.tie(0)->sync_with_stdio(0);
    cin.exceptions(cin.failbit); // remove if to endof file

    int n, q, val;
    cin >> n >> q;
    vi v;
    fo(i, n){
        cin >> val;
        v.pb(val);
    }
    int siz = 10000000;
    vi biggest(siz+1, 0);
    fo(i, v.size()){
        for(int j = 0; j<=siz; j+=v[i]) biggest[j] = max(biggest[j], v[i]);
    }
    Node st(0, siz+2);
    st.update(0, 1, 0);
    fo(i, siz+1){
        if(biggest[i] == 0) continue;
        st.update(i+1, i+biggest[i], st.query(i, i+1)+1);
    }
    while(q--){
        cin >> val;
        int ans = st.query(val, val+1);
        if(ans > 1e9) cout << "oo\n";
        else cout << ans << "\n";
    }

    return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 284 ms 262144 KB Execution killed with signal 9
2 Runtime error 260 ms 262144 KB Execution killed with signal 9
3 Runtime error 257 ms 262144 KB Execution killed with signal 9
4 Runtime error 229 ms 262144 KB Execution killed with signal 9
5 Runtime error 255 ms 262144 KB Execution killed with signal 9
6 Runtime error 250 ms 262144 KB Execution killed with signal 9
7 Runtime error 260 ms 262144 KB Execution killed with signal 9
8 Runtime error 439 ms 262144 KB Execution killed with signal 9
9 Runtime error 273 ms 262144 KB Execution killed with signal 9
10 Runtime error 311 ms 262144 KB Execution killed with signal 9
11 Runtime error 352 ms 262144 KB Execution killed with signal 9
12 Runtime error 237 ms 262144 KB Execution killed with signal 9
13 Runtime error 397 ms 262144 KB Execution killed with signal 9
14 Runtime error 390 ms 262144 KB Execution killed with signal 9
15 Runtime error 332 ms 262144 KB Execution killed with signal 9
16 Runtime error 296 ms 262144 KB Execution killed with signal 9
17 Runtime error 311 ms 262144 KB Execution killed with signal 9
18 Runtime error 220 ms 262144 KB Execution killed with signal 9

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 257 ms 262144 KB Execution killed with signal 9
2 Runtime error 260 ms 262144 KB Execution killed with signal 9
3 Runtime error 475 ms 262144 KB Execution killed with signal 9
4 Runtime error 252 ms 262144 KB Execution killed with signal 9
5 Runtime error 338 ms 262144 KB Execution killed with signal 9
6 Runtime error 255 ms 262144 KB Execution killed with signal 9
7 Runtime error 254 ms 262144 KB Execution killed with signal 9
8 Runtime error 275 ms 262144 KB Execution killed with signal 9
9 Runtime error 458 ms 262144 KB Execution killed with signal 9
10 Runtime error 433 ms 262144 KB Execution killed with signal 9
11 Runtime error 412 ms 262144 KB Execution killed with signal 9
12 Runtime error 317 ms 262144 KB Execution killed with signal 9
13 Runtime error 241 ms 262144 KB Execution killed with signal 9
14 Runtime error 292 ms 262144 KB Execution killed with signal 9
15 Runtime error 412 ms 262144 KB Execution killed with signal 9
16 Runtime error 249 ms 262144 KB Execution killed with signal 9
17 Runtime error 384 ms 262144 KB Execution killed with signal 9
18 Runtime error 369 ms 262144 KB Execution killed with signal 9

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 410 ms 262144 KB Execution killed with signal 9
2 Runtime error 493 ms 262144 KB Execution killed with signal 9
3 Runtime error 474 ms 262144 KB Execution killed with signal 9
4 Runtime error 326 ms 262144 KB Execution killed with signal 9
5 Runtime error 258 ms 262144 KB Execution killed with signal 9
6 Runtime error 393 ms 262144 KB Execution killed with signal 9
7 Runtime error 333 ms 262144 KB Execution killed with signal 9
8 Runtime error 364 ms 262144 KB Execution killed with signal 9
9 Runtime error 371 ms 262144 KB Execution killed with signal 9
10 Runtime error 312 ms 262144 KB Execution killed with signal 9
11 Runtime error 298 ms 262144 KB Execution killed with signal 9
12 Runtime error 368 ms 262144 KB Execution killed with signal 9
13 Runtime error 450 ms 262144 KB Execution killed with signal 9
14 Runtime error 307 ms 262144 KB Execution killed with signal 9
15 Runtime error 381 ms 262144 KB Execution killed with signal 9
16 Runtime error 393 ms 262144 KB Execution killed with signal 9
17 Runtime error 427 ms 262144 KB Execution killed with signal 9
18 Runtime error 462 ms 262144 KB Execution killed with signal 9
19 Runtime error 280 ms 262144 KB Execution killed with signal 9
20 Runtime error 440 ms 262144 KB Execution killed with signal 9
21 Runtime error 354 ms 262144 KB Execution killed with signal 9
22 Runtime error 413 ms 262144 KB Execution killed with signal 9
23 Runtime error 260 ms 262144 KB Execution killed with signal 9
24 Runtime error 240 ms 262144 KB Execution killed with signal 9
25 Runtime error 330 ms 262144 KB Execution killed with signal 9
26 Runtime error 291 ms 262144 KB Execution killed with signal 9
27 Runtime error 459 ms 262144 KB Execution killed with signal 9
28 Runtime error 258 ms 262144 KB Execution killed with signal 9
29 Runtime error 430 ms 262144 KB Execution killed with signal 9
30 Runtime error 420 ms 262144 KB Execution killed with signal 9
31 Runtime error 262 ms 262144 KB Execution killed with signal 9
32 Runtime error 283 ms 262144 KB Execution killed with signal 9
33 Runtime error 222 ms 262144 KB Execution killed with signal 9
34 Runtime error 323 ms 262144 KB Execution killed with signal 9
35 Runtime error 273 ms 262144 KB Execution killed with signal 9
36 Runtime error 396 ms 262144 KB Execution killed with signal 9
37 Runtime error 265 ms 262144 KB Execution killed with signal 9
38 Runtime error 337 ms 262144 KB Execution killed with signal 9
39 Runtime error 214 ms 262144 KB Execution killed with signal 9
40 Runtime error 335 ms 262144 KB Execution killed with signal 9
41 Runtime error 300 ms 262144 KB Execution killed with signal 9
42 Runtime error 378 ms 262144 KB Execution killed with signal 9