oj.uz

Submission #134044

# Submission time Handle Problem Language Result Execution time Memory
134044 2019-07-22T01:40:10 Z ly20 Brunhilda’s Birthday (BOI13_brunhilda) C++17
20 / 100
 400 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];
map<int,int> mpa;
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]);
        mpa[p[i]]=i+1;
    }
    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(mpa[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:72:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<fat[i].size();j++)
                         ~^~~~~~~~~~~~~~
brunhilda.cpp:79:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<fat[i].size();j++)
                     ~^~~~~~~~~~~~~~
brunhilda.cpp:49: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:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&p[i]);
         ~~~~~^~~~~~~~~~~~
brunhilda.cpp:60: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 214 ms 235256 KB Output is correct
2 Correct 219 ms 235512 KB Output is correct
3 Correct 219 ms 235532 KB Output is correct
4 Correct 221 ms 235312 KB Output is correct
5 Correct 215 ms 235256 KB Output is correct
6 Correct 216 ms 235484 KB Output is correct
7 Correct 217 ms 235384 KB Output is correct
8 Correct 225 ms 235388 KB Output is correct
9 Correct 216 ms 235128 KB Output is correct
10 Correct 220 ms 235256 KB Output is correct
11 Correct 221 ms 235384 KB Output is correct
12 Correct 213 ms 235128 KB Output is correct
13 Correct 222 ms 235628 KB Output is correct
14 Correct 221 ms 235640 KB Output is correct
15 Correct 224 ms 235384 KB Output is correct
16 Correct 223 ms 235492 KB Output is correct
17 Correct 218 ms 235408 KB Output is correct
18 Correct 215 ms 235356 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 359 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 354 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 274 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 252 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 264 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 241 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 357 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 312 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 279 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 273 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 260 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 259 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 278 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 381 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 251 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 319 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 280 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 268 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 278 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 267 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 398 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 271 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 341 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 272 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 274 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 255 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 261 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 252 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 266 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 255 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 252 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 251 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 285 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 279 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 256 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 270 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Runtime error 256 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Runtime error 341 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Runtime error 377 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
24 Runtime error 304 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Runtime error 267 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
26 Runtime error 267 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
27 Runtime error 330 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
28 Runtime error 273 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Runtime error 360 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Runtime error 394 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Runtime error 272 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
32 Runtime error 271 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
33 Runtime error 325 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
34 Runtime error 341 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
35 Runtime error 259 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
36 Runtime error 337 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
37 Runtime error 400 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
38 Runtime error 264 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Runtime error 326 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Runtime error 265 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
41 Runtime error 334 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
42 Runtime error 256 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)