oj.uz

Submission #134033

# Submission time Handle Problem Language Result Execution time Memory
134033 2019-07-22T01:19:34 Z ly20 Brunhilda’s Birthday (BOI13_brunhilda) C++17
20 / 100
 382 ms 262148 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e7+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 215 ms 235440 KB Output is correct
2 Correct 221 ms 235512 KB Output is correct
3 Correct 218 ms 235356 KB Output is correct
4 Correct 216 ms 235256 KB Output is correct
5 Correct 213 ms 235172 KB Output is correct
6 Correct 215 ms 235280 KB Output is correct
7 Correct 218 ms 235332 KB Output is correct
8 Correct 222 ms 235512 KB Output is correct
9 Correct 213 ms 235128 KB Output is correct
10 Correct 219 ms 235360 KB Output is correct
11 Correct 220 ms 235512 KB Output is correct
12 Correct 215 ms 235124 KB Output is correct
13 Correct 221 ms 235512 KB Output is correct
14 Correct 249 ms 235564 KB Output is correct
15 Correct 219 ms 235492 KB Output is correct
16 Correct 220 ms 235380 KB Output is correct
17 Correct 224 ms 235408 KB Output is correct
18 Correct 230 ms 235316 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 359 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 321 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 242 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 254 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 243 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 236 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 360 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 314 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 244 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 246 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 239 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 238 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 256 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 251 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 241 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 326 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 236 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 254 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 250 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 261 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 250 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 272 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 373 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 251 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 294 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 246 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 249 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 242 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 244 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 240 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 250 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 247 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 243 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 241 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 249 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)
19 Runtime error 244 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 243 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Runtime error 259 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Runtime error 260 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Runtime error 382 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
24 Runtime error 302 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Runtime error 249 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
26 Runtime error 253 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
27 Runtime error 267 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
28 Runtime error 250 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Runtime error 300 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Runtime error 304 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Runtime error 266 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
32 Runtime error 257 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
33 Runtime error 327 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
34 Runtime error 291 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
35 Runtime error 269 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
36 Runtime error 288 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
37 Runtime error 379 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
38 Runtime error 257 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Runtime error 319 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Runtime error 253 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
41 Runtime error 264 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
42 Runtime error 247 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)