oj.uz

Submission #134038

# Submission time Handle Problem Language Result Execution time Memory
134038 2019-07-22T01:30:10 Z ly20 Brunhilda’s Birthday (BOI13_brunhilda) C++17
0 / 100
 393 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;
    }
    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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 218 ms 235228 KB Output isn't correct
2 Incorrect 220 ms 235512 KB Output isn't correct
3 Incorrect 222 ms 235384 KB Output isn't correct
4 Incorrect 219 ms 235384 KB Output isn't correct
5 Incorrect 217 ms 235104 KB Output isn't correct
6 Incorrect 217 ms 235256 KB Output isn't correct
7 Incorrect 223 ms 235308 KB Output isn't correct
8 Incorrect 252 ms 235484 KB Output isn't correct
9 Incorrect 252 ms 235120 KB Output isn't correct
10 Incorrect 221 ms 235384 KB Output isn't correct
11 Incorrect 225 ms 235504 KB Output isn't correct
12 Incorrect 220 ms 235288 KB Output isn't correct
13 Incorrect 222 ms 235512 KB Output isn't correct
14 Incorrect 224 ms 235724 KB Output isn't correct
15 Incorrect 219 ms 235396 KB Output isn't correct
16 Incorrect 225 ms 235384 KB Output isn't correct
17 Incorrect 217 ms 235384 KB Output isn't correct
18 Incorrect 220 ms 235396 KB Output isn't 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 347 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 247 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 253 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 238 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 363 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 319 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 248 ms 262148 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 238 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 236 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 293 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 272 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 242 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 330 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 251 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 260 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 257 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 254 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 393 ms 262148 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 301 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 254 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 245 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 248 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 237 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 251 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 264 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 242 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 243 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 244 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 250 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
19 Runtime error 247 ms 262148 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 247 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Runtime error 280 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Runtime error 373 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
24 Runtime error 309 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Runtime error 259 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
26 Runtime error 258 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
27 Runtime error 258 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
28 Runtime error 257 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Runtime error 305 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Runtime error 309 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Runtime error 272 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
32 Runtime error 270 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
33 Runtime error 324 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
34 Runtime error 295 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 268 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
37 Runtime error 382 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
38 Runtime error 254 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Runtime error 324 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Runtime error 257 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
41 Runtime error 257 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)