oj.uz

Submission #134043

# Submission time Handle Problem Language Result Execution time Memory
134043 2019-07-22T01:39:32 Z ly20 Brunhilda’s Birthday (BOI13_brunhilda) C++17
17.7778 / 100
 406 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;
    }
    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
17.7777777778 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 215 ms 235256 KB Output isn't correct
2 Correct 229 ms 235524 KB Output is correct
3 Correct 216 ms 235388 KB Output is correct
4 Correct 216 ms 235256 KB Output is correct
5 Correct 214 ms 235312 KB Output is correct
6 Incorrect 215 ms 235340 KB Output isn't correct
7 Correct 215 ms 235392 KB Output is correct
8 Correct 218 ms 235340 KB Output is correct
9 Correct 214 ms 235240 KB Output is correct
10 Correct 219 ms 235356 KB Output is correct
11 Correct 218 ms 235384 KB Output is correct
12 Correct 214 ms 235316 KB Output is correct
13 Correct 224 ms 235512 KB Output is correct
14 Correct 223 ms 235640 KB Output is correct
15 Correct 219 ms 235384 KB Output is correct
16 Correct 218 ms 235484 KB Output is correct
17 Correct 219 ms 235356 KB Output is correct
18 Correct 243 ms 235384 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 390 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 367 ms 262148 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 254 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 269 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 242 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 361 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
8 Runtime error 323 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 271 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 299 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 262 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 252 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 250 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 250 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 265 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 355 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 243 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Runtime error 330 ms 262144 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 274 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Runtime error 284 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Runtime error 280 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
4 Runtime error 263 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
5 Runtime error 403 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 264 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Runtime error 343 ms 262144 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 277 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 254 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 260 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Runtime error 252 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
13 Runtime error 264 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
14 Runtime error 262 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Runtime error 250 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 268 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Runtime error 278 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 247 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
20 Runtime error 295 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
21 Runtime error 255 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Runtime error 372 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
23 Runtime error 384 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
24 Runtime error 311 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 278 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
27 Runtime error 326 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 370 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Runtime error 327 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
31 Runtime error 275 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
32 Runtime error 290 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
33 Runtime error 329 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
34 Runtime error 345 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
35 Runtime error 261 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
36 Runtime error 338 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
37 Runtime error 406 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
38 Runtime error 269 ms 262144 KB Execution killed with signal 9 (could be triggered by violating memory limits)
39 Runtime error 322 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Runtime error 269 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
41 Runtime error 332 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
42 Runtime error 261 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)