oj.uz

Submission #134032

# Submission time Handle Problem Language Result Execution time Memory
134032 2019-07-22T01:18:58 Z ly20 Brunhilda’s Birthday (BOI13_brunhilda) C++17
0 / 100
 246 ms 262148 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN=11234567,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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 213 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 210 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 214 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 206 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 217 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 234 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 206 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 207 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 206 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 210 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 206 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 206 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 208 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 220 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 219 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 231 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 232 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 243 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 211 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 217 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 246 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 210 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 209 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 212 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 203 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 206 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 208 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 208 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 234 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 213 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 210 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 203 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 208 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 206 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 204 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 211 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 196 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 210 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 205 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 208 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 212 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 206 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 209 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 214 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 217 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 204 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 211 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 208 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 213 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 207 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 212 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 209 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 206 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 212 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 211 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 212 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Runtime error 212 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Runtime error 207 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Runtime error 207 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
24 Runtime error 211 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Runtime error 209 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
26 Runtime error 207 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
27 Runtime error 206 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
28 Runtime error 212 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Runtime error 209 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Runtime error 240 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Runtime error 207 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
32 Runtime error 216 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
33 Runtime error 207 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
34 Runtime error 209 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
35 Runtime error 207 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
36 Runtime error 209 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
37 Runtime error 206 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
38 Runtime error 210 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Runtime error 209 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Runtime error 211 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
41 Runtime error 208 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
42 Runtime error 206 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)