Submission #1109626

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1109626	2024-11-07T07:42:20 Z	0pt1mus23	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	2.22222 / 100	1000 ms	262144 KB

brunhilda

#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define ins insert      
#define pb push_back
#define endl '\n'
#define putr(x) cout<<x<<endl;return; 
#define all(x) x.begin(),x.end()
int nxt(){ int x;cin>>x; return x; }
const int mod = 1e9 +7, sze = 1e7 +10, inf = INT_MAX, LG = 20;
int dp[sze];
void fast(){
    int n,q;
    cin>>n>>q;
    unordered_map<int,int> ans;
    int mx = 0;
    priority_queue<pair<int,int>> ev;
    for(int i=1;i<=n;i++){
        int p;cin>>p;
        // event[p].pb(p);
        ev.push({-p,p});
        mx=max(mx,p);
    }
    int c,prev;
    pair<int,int> beg;
    for(int i =1;i<sze;i++){
        dp[i]=inf;
        c=0;
        while(!ev.empty() && (-(ev.top().first )) ==i ) {
            beg = ev.top();
            ev.pop();
            c++;
            // cout<<i<<" "<<beg.first<<" "<<beg.second<<endl;
            if( (i + beg.second) < sze){
                ev.push({ -(i + beg.second) , beg.second });
            }
            prev=  dp[i - beg.second];
            if(i != beg.second){
                if( (--ans[prev]) < 0){
                    ans.erase(prev);
                }
            }
        }
        if( i < mx ){
            dp[i]=1;
        }
        else if(!ans.empty()){
            dp[i]= (*ans.begin()).first+1;
        }
        if(dp[i]<inf){
            ans[dp[i]]+=c;
        }
    }
 
 
    while(q--){
        int v;
        cin>>v;
        if(dp[v]>=inf){
            cout<<"oo"<<endl;
        }
        else{
            cout<<dp[v]<<endl;
        }
    }
}
 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int tt = 1; 
    // cin>>tt;
 
    while(tt--){
        fast();
    }
 
    return 0;
}

Subtask #1

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	311 ms	262144 KB	Execution killed with signal 9
2	Runtime error	465 ms	262144 KB	Execution killed with signal 9
3	Runtime error	394 ms	262144 KB	Execution killed with signal 9
4	Runtime error	338 ms	262144 KB	Execution killed with signal 9
5	Runtime error	380 ms	262144 KB	Execution killed with signal 9
6	Runtime error	339 ms	262144 KB	Execution killed with signal 9
7	Runtime error	413 ms	262144 KB	Execution killed with signal 9
8	Runtime error	440 ms	262144 KB	Execution killed with signal 9
9	Runtime error	551 ms	262144 KB	Execution killed with signal 9
10	Runtime error	639 ms	262144 KB	Execution killed with signal 9
11	Runtime error	567 ms	262144 KB	Execution killed with signal 9
12	Runtime error	309 ms	262144 KB	Execution killed with signal 9
13	Execution timed out	1073 ms	231016 KB	Time limit exceeded
14	Execution timed out	1072 ms	224112 KB	Time limit exceeded
15	Runtime error	538 ms	262144 KB	Execution killed with signal 9
16	Runtime error	474 ms	262144 KB	Execution killed with signal 9
17	Runtime error	392 ms	262144 KB	Execution killed with signal 9
18	Runtime error	337 ms	262144 KB	Execution killed with signal 9

Subtask #2

2.22222222222 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	450 ms	262144 KB	Execution killed with signal 9
2	Correct	396 ms	123356 KB	Output is correct
3	Execution timed out	1074 ms	79936 KB	Time limit exceeded
4	Runtime error	599 ms	262144 KB	Execution killed with signal 9
5	Execution timed out	1066 ms	209768 KB	Time limit exceeded
6	Runtime error	534 ms	262144 KB	Execution killed with signal 9
7	Runtime error	461 ms	262144 KB	Execution killed with signal 9
8	Runtime error	504 ms	262144 KB	Execution killed with signal 9
9	Execution timed out	1066 ms	148800 KB	Time limit exceeded
10	Execution timed out	1074 ms	78548 KB	Time limit exceeded
11	Execution timed out	1072 ms	135660 KB	Time limit exceeded
12	Runtime error	818 ms	262144 KB	Execution killed with signal 9
13	Runtime error	384 ms	262144 KB	Execution killed with signal 9
14	Runtime error	510 ms	262144 KB	Execution killed with signal 9
15	Execution timed out	1064 ms	194480 KB	Time limit exceeded
16	Correct	384 ms	123208 KB	Output is correct
17	Execution timed out	1082 ms	224800 KB	Time limit exceeded
18	Execution timed out	1046 ms	68108 KB	Time limit exceeded

Subtask #3

0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	1060 ms	181380 KB	Time limit exceeded
2	Execution timed out	1074 ms	129188 KB	Time limit exceeded
3	Execution timed out	1047 ms	117888 KB	Time limit exceeded
4	Runtime error	875 ms	262144 KB	Execution killed with signal 9
5	Runtime error	700 ms	262144 KB	Execution killed with signal 9
6	Execution timed out	1069 ms	236164 KB	Time limit exceeded
7	Execution timed out	1088 ms	210840 KB	Time limit exceeded
8	Execution timed out	1064 ms	191360 KB	Time limit exceeded
9	Execution timed out	1072 ms	193896 KB	Time limit exceeded
10	Runtime error	954 ms	262144 KB	Execution killed with signal 9
11	Runtime error	777 ms	262144 KB	Execution killed with signal 9
12	Execution timed out	1086 ms	236484 KB	Time limit exceeded
13	Execution timed out	1065 ms	146648 KB	Time limit exceeded
14	Runtime error	684 ms	262144 KB	Execution killed with signal 9
15	Execution timed out	1075 ms	224056 KB	Time limit exceeded
16	Execution timed out	1079 ms	197700 KB	Time limit exceeded
17	Execution timed out	1052 ms	207740 KB	Time limit exceeded
18	Execution timed out	1075 ms	138916 KB	Time limit exceeded
19	Runtime error	463 ms	262144 KB	Execution killed with signal 9
20	Execution timed out	1073 ms	122948 KB	Time limit exceeded
21	Runtime error	869 ms	262144 KB	Execution killed with signal 9
22	Execution timed out	1075 ms	118672 KB	Time limit exceeded
23	Runtime error	657 ms	262144 KB	Execution killed with signal 9
24	Runtime error	393 ms	262144 KB	Execution killed with signal 9
25	Runtime error	914 ms	262144 KB	Execution killed with signal 9
26	Runtime error	892 ms	262144 KB	Execution killed with signal 9
27	Execution timed out	1067 ms	80200 KB	Time limit exceeded
28	Runtime error	462 ms	262144 KB	Execution killed with signal 9
29	Execution timed out	1073 ms	146116 KB	Time limit exceeded
30	Execution timed out	1083 ms	197908 KB	Time limit exceeded
31	Runtime error	495 ms	262144 KB	Execution killed with signal 9
32	Runtime error	590 ms	262144 KB	Execution killed with signal 9
33	Runtime error	368 ms	262144 KB	Execution killed with signal 9
34	Execution timed out	1081 ms	151764 KB	Time limit exceeded
35	Runtime error	486 ms	262144 KB	Execution killed with signal 9
36	Execution timed out	1063 ms	118296 KB	Time limit exceeded
37	Runtime error	808 ms	262144 KB	Execution killed with signal 9
38	Execution timed out	1068 ms	227768 KB	Time limit exceeded
39	Runtime error	455 ms	262144 KB	Execution killed with signal 9
40	Execution timed out	1097 ms	256512 KB	Time limit exceeded
41	Execution timed out	1058 ms	85500 KB	Time limit exceeded
42	Execution timed out	1073 ms	213828 KB	Time limit exceeded