oj.uz

Submission #134039

# Submission time Handle Problem Language Result Execution time Memory
134039 2019-07-22T01:32:21 Z ly20 Brunhilda’s Birthday (BOI13_brunhilda) C++17
20 / 100
 416 ms 262148 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e7+4,MAXQ=112345,INF=1123456789;
int p[MAXQ],r[MAXQ],resp;
pair<int,int> query[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]);
        query[i]=make_pair(r[i],i);
        r[i]=INF;
    }
    sort(query,query+q);
    for(int i=0;i<m;i++)for(int j=p[i];j<=mq;j+=p[i])fat[j].push_back(p[i]);
    int atu=0;
    for(int i=1;i<=mq;i++)
    {
        if(i>=mp)
        {
            resp=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);
            }
            resp=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);
        }
        if(i==query[atu].first)
        {
            r[query[atu].second]=resp;
            atu++;
        }
    }
    for(int i=0;i<q;i++)
    {
        if(r[i]<INF)printf("%d\n",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:70:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<fat[i].size();j++)
                         ~^~~~~~~~~~~~~~
brunhilda.cpp:77:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<fat[i].size();j++)
                     ~^~~~~~~~~~~~~~
brunhilda.cpp:48: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:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&p[i]);
         ~~~~~^~~~~~~~~~~~
brunhilda.cpp:58: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 217 ms 235384 KB Output is correct
2 Correct 221 ms 235512 KB Output is correct
3 Correct 221 ms 235308 KB Output is correct
4 Correct 219 ms 235388 KB Output is correct
5 Correct 218 ms 235244 KB Output is correct
6 Correct 216 ms 235180 KB Output is correct
7 Correct 217 ms 235300 KB Output is correct
8 Correct 224 ms 235484 KB Output is correct
9 Correct 217 ms 235172 KB Output is correct
10 Correct 219 ms 235376 KB Output is correct
11 Correct 221 ms 235424 KB Output is correct
12 Correct 221 ms 235328 KB Output is correct
13 Correct 233 ms 235512 KB Output is correct
14 Correct 224 ms 235640 KB Output is correct
15 Correct 219 ms 235384 KB Output is correct
16 Correct 223 ms 235384 KB Output is correct
17 Correct 224 ms 235420 KB Output is correct
18 Correct 218 ms 235384 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 365 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 332 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 244 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 300 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 246 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 240 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 358 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 310 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 244 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 241 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 254 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 236 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 289 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 247 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 239 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 338 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 234 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 259 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 267 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 257 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 286 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 257 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 381 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 259 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 297 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 251 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 282 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 244 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 250 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 254 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 253 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 243 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 244 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 248 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 247 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 246 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 245 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 263 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Runtime error 252 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Runtime error 271 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Runtime error 377 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
24 Runtime error 303 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Runtime error 278 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
26 Runtime error 416 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
27 Runtime error 253 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
28 Runtime error 255 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Runtime error 307 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Runtime error 314 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Runtime error 267 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
32 Runtime error 278 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
33 Runtime error 326 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
34 Runtime error 301 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
35 Runtime error 253 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
36 Runtime error 274 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
37 Runtime error 384 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
38 Runtime error 256 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Runtime error 321 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Runtime error 261 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
41 Runtime error 263 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
42 Runtime error 261 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)