oj.uz

Submission #134045

# Submission time Handle Problem Language Result Execution time Memory
134045 2019-07-22T01:43:56 Z ly20 Brunhilda’s Birthday (BOI13_brunhilda) C++17
2.53968 / 100
 347 ms 241844 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
1.11111111111 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 214 ms 235332 KB Output isn't correct
2 Incorrect 219 ms 235128 KB Output isn't correct
3 Incorrect 215 ms 235212 KB Output isn't correct
4 Incorrect 215 ms 235384 KB Output isn't correct
5 Incorrect 213 ms 235304 KB Output isn't correct
6 Incorrect 213 ms 235256 KB Output isn't correct
7 Incorrect 213 ms 235128 KB Output isn't correct
8 Incorrect 214 ms 235124 KB Output isn't correct
9 Incorrect 219 ms 235128 KB Output isn't correct
10 Incorrect 217 ms 235128 KB Output isn't correct
11 Incorrect 215 ms 235228 KB Output isn't correct
12 Correct 214 ms 235300 KB Output is correct
13 Incorrect 215 ms 235244 KB Output isn't correct
14 Incorrect 215 ms 235384 KB Output isn't correct
15 Incorrect 215 ms 235236 KB Output isn't correct
16 Incorrect 213 ms 235188 KB Output isn't correct
17 Incorrect 216 ms 235324 KB Output isn't correct
18 Incorrect 216 ms 235484 KB Output isn't correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 274 ms 235864 KB Output isn't correct
2 Incorrect 286 ms 239864 KB Output isn't correct
3 Incorrect 258 ms 238724 KB Output isn't correct
4 Incorrect 244 ms 235476 KB Output isn't correct
5 Incorrect 245 ms 237820 KB Output isn't correct
6 Incorrect 231 ms 235384 KB Output isn't correct
7 Incorrect 254 ms 235972 KB Output isn't correct
8 Incorrect 227 ms 235256 KB Output isn't correct
9 Incorrect 257 ms 238808 KB Output isn't correct
10 Incorrect 259 ms 238984 KB Output isn't correct
11 Incorrect 266 ms 237176 KB Output isn't correct
12 Incorrect 280 ms 235500 KB Output isn't correct
13 Incorrect 257 ms 235444 KB Output isn't correct
14 Incorrect 296 ms 235356 KB Output isn't correct
15 Incorrect 268 ms 237480 KB Output isn't correct
16 Incorrect 304 ms 239896 KB Output isn't correct
17 Incorrect 283 ms 235396 KB Output isn't correct
18 Incorrect 309 ms 240408 KB Output isn't correct

Subtask #3
1.42857142857 / 60.0

# Verdict Execution time Memory Grader output
1 Incorrect 280 ms 238328 KB Output isn't correct
2 Incorrect 276 ms 238252 KB Output isn't correct
3 Incorrect 270 ms 238584 KB Output isn't correct
4 Incorrect 277 ms 236668 KB Output isn't correct
5 Incorrect 347 ms 241744 KB Output isn't correct
6 Incorrect 283 ms 237120 KB Output isn't correct
7 Incorrect 294 ms 241144 KB Output isn't correct
8 Incorrect 281 ms 238240 KB Output isn't correct
9 Incorrect 290 ms 238400 KB Output isn't correct
10 Incorrect 252 ms 235768 KB Output isn't correct
11 Incorrect 255 ms 235792 KB Output isn't correct
12 Incorrect 257 ms 235844 KB Output isn't correct
13 Incorrect 260 ms 238072 KB Output isn't correct
14 Incorrect 301 ms 236620 KB Output isn't correct
15 Incorrect 257 ms 235768 KB Output isn't correct
16 Incorrect 257 ms 235896 KB Output isn't correct
17 Incorrect 271 ms 237660 KB Output isn't correct
18 Incorrect 276 ms 238200 KB Output isn't correct
19 Incorrect 269 ms 235768 KB Output isn't correct
20 Incorrect 273 ms 238628 KB Output isn't correct
21 Incorrect 269 ms 236664 KB Output isn't correct
22 Incorrect 324 ms 241656 KB Output isn't correct
23 Incorrect 292 ms 238260 KB Output isn't correct
24 Incorrect 278 ms 236536 KB Output isn't correct
25 Incorrect 290 ms 236716 KB Output isn't correct
26 Incorrect 279 ms 236700 KB Output isn't correct
27 Incorrect 291 ms 241016 KB Output isn't correct
28 Incorrect 274 ms 236656 KB Output isn't correct
29 Incorrect 326 ms 241844 KB Output isn't correct
30 Incorrect 313 ms 240264 KB Output isn't correct
31 Incorrect 276 ms 236664 KB Output isn't correct
32 Incorrect 282 ms 236632 KB Output isn't correct
33 Incorrect 276 ms 236536 KB Output isn't correct
34 Incorrect 314 ms 241100 KB Output isn't correct
35 Incorrect 312 ms 236764 KB Output isn't correct
36 Incorrect 324 ms 241332 KB Output isn't correct
37 Incorrect 320 ms 241636 KB Output isn't correct
38 Incorrect 283 ms 236904 KB Output isn't correct
39 Incorrect 310 ms 236764 KB Output isn't correct
40 Incorrect 280 ms 236924 KB Output isn't correct
41 Correct 305 ms 241144 KB Output is correct
42 Incorrect 270 ms 236764 KB Output isn't correct