oj.uz

Submission #134034

# Submission time Handle Problem Language Result Execution time Memory
134034 2019-07-22T01:20:10 Z ly20 Brunhilda’s Birthday (BOI13_brunhilda) C++17
20 / 100
 141 ms 81312 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+4,MAXQ=112345,INF=1123456789;
int resp[MAXN],p[MAXQ],r[MAXQ];
vector<int> seg,e,d;
vector<int> fat[MAXN];
int create()
{
    seg.push_back(INF);
    e.push_back(0);
    d.push_back(0);
    return seg.size()-1;
}
void update(int cur,int ini,int fim,int id,int val)
{
    if(ini>id || fim<id)return;
    if(ini==fim)
    {
        seg[cur]=val;
        return;
    }
    int m=(ini+fim)/2;
    if(id<=m)
    {
        if(e[cur]==0)
        {
            int aux=create();
            e[cur]=aux;
        }
        update(e[cur],ini,m,id,val);
    }
    else
    {
        if(d[cur]==0)
        {
            int aux=create();
            d[cur]=aux;
        }
        update(d[cur],m+1,fim,id,val);
    }
    seg[cur]=min(seg[e[cur]],seg[d[cur]]);
}
int main()
{
    create();create();
    int m,q;
    scanf("%d %d",&m,&q);
    int mp=0;
    for(int i=0;i<m;i++)
    {
        scanf("%d",&p[i]);
        mp=max(mp,p[i]);
    }
    int mq=0;
    for(int i=0;i<q;i++)
    {
        scanf("%d",&r[i]);mq=max(mq,r[i]);
    }
    for(int i=0;i<m;i++)for(int j=p[i];j<=mq;j+=p[i])fat[j].push_back(p[i]);
    for(int i=1;i<=mq;i++)
    {
        if(i>=mp)
        {
            resp[i]=INF;
            for(int j=0;j<fat[i].size();j++)
            {
                //printf("%d %d %d\n",i,fat[i][j],resp[i]);
                update(1,1,MAXN,fat[i][j],resp[i]);
            }
            resp[i]=seg[1]+1;
        }
        for(int j=0;j<fat[i].size();j++)
        {
            //printf("%d %d %d\n",i,fat[i][j],resp[i]);
            update(1,1,MAXN,fat[i][j],resp[i]);
        }
    }
    for(int i=0;i<q;i++)
    {
        if(resp[r[i]]<INF)printf("%d\n",resp[r[i]]+1);
        else printf("oo\n");
    }
    //for(int i=0;i<7;i++)printf("%d ",resp[i]);
    //printf("\n");
    return 0;
}

Compilation message

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:65:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<fat[i].size();j++)
                         ~^~~~~~~~~~~~~~
brunhilda.cpp:72:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<fat[i].size();j++)
                     ~^~~~~~~~~~~~~~
brunhilda.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&m,&q);
     ~~~~~^~~~~~~~~~~~~~~
brunhilda.cpp:51:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&p[i]);
         ~~~~~^~~~~~~~~~~~
brunhilda.cpp:57:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&r[i]);mq=max(mq,r[i]);
         ~~~~~^~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 23928 KB Output is correct
2 Correct 27 ms 24056 KB Output is correct
3 Correct 27 ms 24056 KB Output is correct
4 Correct 25 ms 23928 KB Output is correct
5 Correct 23 ms 23800 KB Output is correct
6 Correct 25 ms 23928 KB Output is correct
7 Correct 27 ms 24056 KB Output is correct
8 Correct 28 ms 24056 KB Output is correct
9 Correct 23 ms 23800 KB Output is correct
10 Correct 27 ms 24056 KB Output is correct
11 Correct 28 ms 24056 KB Output is correct
12 Correct 23 ms 23800 KB Output is correct
13 Correct 31 ms 24440 KB Output is correct
14 Correct 31 ms 24332 KB Output is correct
15 Correct 27 ms 24004 KB Output is correct
16 Correct 32 ms 24184 KB Output is correct
17 Correct 27 ms 23992 KB Output is correct
18 Correct 25 ms 23928 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 63 ms 49620 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 72 ms 51320 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 114 ms 80248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 70 ms 57080 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 96 ms 69752 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 104 ms 79736 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 58 ms 49628 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 68 ms 54776 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 102 ms 69884 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 114 ms 80220 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 109 ms 79976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 105 ms 79736 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 80 ms 57040 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 71 ms 57080 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 109 ms 79992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 72 ms 51448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 114 ms 79760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 105 ms 70136 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 120 ms 80408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 114 ms 80248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 117 ms 80632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 120 ms 80376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 83 ms 49656 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 120 ms 80504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 83 ms 53000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 118 ms 80504 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 118 ms 80380 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 77 ms 60792 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 79 ms 60920 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 108 ms 79864 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 120 ms 80632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 117 ms 80376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 108 ms 79992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 108 ms 79992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 96 ms 69692 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 115 ms 80260 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 92 ms 69264 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 118 ms 80396 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 118 ms 80376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 135 ms 81312 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 74 ms 49116 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 78 ms 52060 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 103 ms 69880 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 119 ms 80404 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 126 ms 80888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 92 ms 61512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 95 ms 54520 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 84 ms 51448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 85 ms 57720 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 94 ms 61432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 79 ms 52204 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 84 ms 53112 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 90 ms 61532 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 141 ms 81144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 85 ms 49612 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 122 ms 80556 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 77 ms 52216 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 122 ms 80424 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 126 ms 80888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Runtime error 119 ms 80504 KB Execution killed with signal 11 (could be triggered by violating memory limits)