답안 #74562 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
74562	2018-09-03T17:26:00 Z	SpeedOfMagic	Brunhilda’s Birthday (BOI13_brunhilda)	C++17	3.33333 / 100	1000 ms	42660 KB

brunhilda

/** MIT License Copyright (c) 2018 Vasilyev Daniil **/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
#pragma GCC optimize("Ofast")
template<typename T> using v = vector<T>;
template<typename T, typename U>  using hmap = __gnu_pbds::gp_hash_table<T, U>;
//#define int long long
typedef long double ld;
typedef string str;
typedef vector<int> vint;
#define rep(a, l, r) for(int a = (l); a < (r); a++)
#define pb push_back
#define fs first
#define sc second
#define sz(a) ((int) a.size())
const long long inf = 4611686018427387903; //2^62 - 1
#if 0  //FileIO
const string fileName = "";
ifstream fin ((fileName == "" ? "input.txt"  : fileName + ".in" ));
ofstream fout((fileName == "" ? "output.txt" : fileName + ".out"));
#define get fin>>
#define put fout<<
#else
#define get cin>>
#define put cout<<
#endif
#define eol put endl
#define check(a) put #a << ": " << a << endl;
void read() {}     template<typename Arg,typename... Args> void read (Arg& arg,Args&... args){get (arg)     ;read(args...) ;}
void print(){}     template<typename Arg,typename... Args> void print(Arg  arg,Args...  args){put (arg)<<" ";print(args...);}
void debug(){eol;} template<typename Arg,typename... Args> void debug(Arg  arg,Args...  args){put (arg)<<" ";debug(args...);}
int getInt(){int a; get a; return a;}
//code goes here
//you want to set 2 functions: f(int a, int b) and segTreeNode::update(int val) and 1 parameter: nothing

const int nothing = 0; //nothing means that f(x, nothing) = x

struct segTreeNode {
    int val = nothing;

    segTreeNode(int _val) : val(_val) {}

    void update(int _val) { //function that updates node based on val
        this -> val = _val;
    }
};

vector<segTreeNode> segTree;
int n, tot;

int f(int a, int b) { //f - query you need to calculate, but for two values
    return max(segTree[a].val, segTree[b].val);
}

void update(int nodeToUpdate, int value, int cur = 1, int ll = 1, int rr = tot) {
    if (ll == rr) {
        segTree[cur].update(value);
        return;
    }

    int p = (ll + rr) / 2;

    if (nodeToUpdate <= p)
        update(nodeToUpdate, value, cur * 2, ll, p);
    else
        update(nodeToUpdate, value, cur * 2 + 1, p + 1, rr);

    segTree[cur] = f(cur * 2, cur * 2 + 1);
}

int query(int l, int r, int cur = 1, int ll = 1, int rr = tot) {
    if (l > r)
        return nothing;

    if (l == ll && r == rr)
        return segTree[cur].val;

    int mid = (ll + rr) / 2;
    return f(query(l, min(r, mid), cur * 2, ll, mid), query(max(l, mid + 1), r, cur * 2 + 1, mid + 1, rr));
}

void init(vector<int> vals) {
    n = vals.size();

    tot = n;
    while (tot & (tot - 1))
        tot++;

    segTree = vector<segTreeNode>(tot * 2, segTreeNode(nothing));

    for (int i = 0; i < n; i++)
        segTree[i + tot].val = vals[i];

    for (int i = tot - 1; i; i--)
        segTree[i] = f(i * 2, i * 2 + 1);
}

const long long N = 1e7 + 1;
const int LIM = 1;
int dp[N];

void run() {
    int m, q;
    read(m, q);

    vint primes;

    priority_queue<pair<int, int>> nxt;
    int p[m];
    rep(i, 0, m) {
        get p[i];
        if (p[i] > LIM)
            nxt.push({-p[i], i});
        else
            primes.pb(p[i]);
    }

    long long mul = 1;
    rep(i, 0, m) {
        mul *= p[i];
        if (mul > N) {
            mul = 1e9;
            break;
        }
    }

    dp[0] = 0;
    
    int pen = 0;

    init(vint(m, 1));

    rep(i, 1, N) {
        while (!nxt.empty() && -nxt.top().fs == i) {
            int j = nxt.top().sc;
            int val = -nxt.top().fs;
            nxt.pop();
            nxt.push({-(val + p[j]), j});

            update(j + 1, -pen);
        }
        int d = query(1, tot) + pen;
        dp[i] = dp[i - d] + 1;

        pen++;
    }

    rep(i, 0, q) {
        int n;
        get n;
        if (n >= mul)
            put "oo";
        else
            put dp[n];
        eol;
    }
}
int32_t main() {srand(time(0)); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); put fixed; put setprecision(15); run(); return 0;}

Subtask #1
1.11111111111 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	129 ms	39416 KB	Output isn't correct
2	Incorrect	796 ms	39644 KB	Output isn't correct
3	Incorrect	423 ms	39644 KB	Output isn't correct
4	Incorrect	226 ms	39692 KB	Output isn't correct
5	Incorrect	278 ms	39692 KB	Output isn't correct
6	Incorrect	125 ms	39692 KB	Output isn't correct
7	Incorrect	392 ms	39692 KB	Output isn't correct
8	Incorrect	510 ms	39692 KB	Output isn't correct
9	Incorrect	964 ms	39752 KB	Output isn't correct
10	Execution timed out	1075 ms	39752 KB	Time limit exceeded
11	Execution timed out	1008 ms	39816 KB	Time limit exceeded
12	Correct	131 ms	39816 KB	Output is correct
13	Execution timed out	1084 ms	39816 KB	Time limit exceeded
14	Execution timed out	1079 ms	39816 KB	Time limit exceeded
15	Incorrect	827 ms	39856 KB	Output isn't correct
16	Incorrect	865 ms	39856 KB	Output isn't correct
17	Incorrect	441 ms	39856 KB	Output isn't correct
18	Incorrect	168 ms	39856 KB	Output isn't correct

Subtask #2
2.22222222222 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	517 ms	40180 KB	Output isn't correct
2	Correct	687 ms	42212 KB	Output is correct
3	Execution timed out	1072 ms	42212 KB	Time limit exceeded
4	Execution timed out	1020 ms	42212 KB	Time limit exceeded
5	Execution timed out	1083 ms	42212 KB	Time limit exceeded
6	Incorrect	962 ms	42212 KB	Output isn't correct
7	Incorrect	465 ms	42212 KB	Output isn't correct
8	Incorrect	797 ms	42212 KB	Output isn't correct
9	Execution timed out	1088 ms	42212 KB	Time limit exceeded
10	Execution timed out	1070 ms	42212 KB	Time limit exceeded
11	Execution timed out	1090 ms	42212 KB	Time limit exceeded
12	Execution timed out	1072 ms	42212 KB	Time limit exceeded
13	Incorrect	451 ms	42212 KB	Output isn't correct
14	Execution timed out	1018 ms	42212 KB	Time limit exceeded
15	Execution timed out	1055 ms	42212 KB	Time limit exceeded
16	Correct	734 ms	42360 KB	Output is correct
17	Execution timed out	1084 ms	42360 KB	Time limit exceeded
18	Execution timed out	1073 ms	42360 KB	Time limit exceeded

Subtask #3
0 / 60.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	1078 ms	42360 KB	Time limit exceeded
2	Execution timed out	1081 ms	42360 KB	Time limit exceeded
3	Execution timed out	1084 ms	42360 KB	Time limit exceeded
4	Execution timed out	1077 ms	42360 KB	Time limit exceeded
5	Execution timed out	1076 ms	42660 KB	Time limit exceeded
6	Execution timed out	1079 ms	42660 KB	Time limit exceeded
7	Execution timed out	1076 ms	42660 KB	Time limit exceeded
8	Execution timed out	1081 ms	42660 KB	Time limit exceeded
9	Execution timed out	1078 ms	42660 KB	Time limit exceeded
10	Execution timed out	1090 ms	42660 KB	Time limit exceeded
11	Execution timed out	1079 ms	42660 KB	Time limit exceeded
12	Execution timed out	1078 ms	42660 KB	Time limit exceeded
13	Execution timed out	1086 ms	42660 KB	Time limit exceeded
14	Execution timed out	1093 ms	42660 KB	Time limit exceeded
15	Execution timed out	1084 ms	42660 KB	Time limit exceeded
16	Execution timed out	1070 ms	42660 KB	Time limit exceeded
17	Execution timed out	1087 ms	42660 KB	Time limit exceeded
18	Execution timed out	1085 ms	42660 KB	Time limit exceeded
19	Incorrect	793 ms	42660 KB	Output isn't correct
20	Execution timed out	1073 ms	42660 KB	Time limit exceeded
21	Execution timed out	1065 ms	42660 KB	Time limit exceeded
22	Execution timed out	1093 ms	42660 KB	Time limit exceeded
23	Execution timed out	1084 ms	42660 KB	Time limit exceeded
24	Incorrect	570 ms	42660 KB	Output isn't correct
25	Execution timed out	1068 ms	42660 KB	Time limit exceeded
26	Execution timed out	1074 ms	42660 KB	Time limit exceeded
27	Execution timed out	1084 ms	42660 KB	Time limit exceeded
28	Incorrect	765 ms	42660 KB	Output isn't correct
29	Execution timed out	1081 ms	42660 KB	Time limit exceeded
30	Execution timed out	1074 ms	42660 KB	Time limit exceeded
31	Execution timed out	1031 ms	42660 KB	Time limit exceeded
32	Execution timed out	1089 ms	42660 KB	Time limit exceeded
33	Incorrect	387 ms	42660 KB	Output isn't correct
34	Execution timed out	1072 ms	42660 KB	Time limit exceeded
35	Incorrect	939 ms	42660 KB	Output isn't correct
36	Execution timed out	1073 ms	42660 KB	Time limit exceeded
37	Execution timed out	1026 ms	42660 KB	Time limit exceeded
38	Execution timed out	1087 ms	42660 KB	Time limit exceeded
39	Incorrect	755 ms	42660 KB	Output isn't correct
40	Execution timed out	1082 ms	42660 KB	Time limit exceeded
41	Execution timed out	1079 ms	42660 KB	Time limit exceeded
42	Execution timed out	1075 ms	42660 KB	Time limit exceeded

답안 #74562

Compilation message

Subtask #1 1.11111111111 / 20.0

Subtask #2 2.22222222222 / 20.0

Subtask #3 0 / 60.0

Subtask #1
1.11111111111 / 20.0

Subtask #2
2.22222222222 / 20.0

Subtask #3
0 / 60.0