oj.uz

Submission #134051

# Submission time Handle Problem Language Result Execution time Memory
134051 2019-07-22T02:27:28 Z ly20 Brunhilda’s Birthday (BOI13_brunhilda) C++17
1.11111 / 100
 137 ms 61176 KB 
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+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(fat[i].size()==0 && query[atu].first!=i)continue;
        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:73:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<fat[i].size();j++)
                         ~^~~~~~~~~~~~~~
brunhilda.cpp:80: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 24 ms 23804 KB Output isn't correct
2 Incorrect 23 ms 23800 KB Output isn't correct
3 Incorrect 23 ms 23800 KB Output isn't correct
4 Incorrect 25 ms 23928 KB Output isn't correct
5 Incorrect 28 ms 23800 KB Output isn't correct
6 Incorrect 28 ms 23928 KB Output isn't correct
7 Incorrect 23 ms 23800 KB Output isn't correct
8 Incorrect 24 ms 23800 KB Output isn't correct
9 Incorrect 29 ms 23800 KB Output isn't correct
10 Incorrect 23 ms 23800 KB Output isn't correct
11 Incorrect 27 ms 23928 KB Output isn't correct
12 Correct 24 ms 23800 KB Output is correct
13 Incorrect 24 ms 23928 KB Output isn't correct
14 Incorrect 26 ms 24056 KB Output isn't correct
15 Incorrect 23 ms 23800 KB Output isn't correct
16 Incorrect 23 ms 23800 KB Output isn't correct
17 Incorrect 25 ms 24184 KB Output isn't correct
18 Incorrect 26 ms 24056 KB Output isn't correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 62 ms 49280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 100 ms 57560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 93 ms 55428 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 59 ms 48392 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 83 ms 53484 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 66 ms 48120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 73 ms 49272 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 65 ms 48008 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 94 ms 55672 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 90 ms 55416 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 73 ms 52344 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 67 ms 48120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 58 ms 48348 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 59 ms 48252 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 81 ms 52572 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 102 ms 57716 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 58 ms 48248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 105 ms 58488 KB Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 90 ms 54616 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 87 ms 54264 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 90 ms 55032 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 84 ms 50808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 137 ms 61124 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 85 ms 51704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 113 ms 60152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 89 ms 54392 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 125 ms 54472 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 62 ms 49016 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 65 ms 49144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 64 ms 49400 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 90 ms 53880 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 72 ms 50424 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 65 ms 49400 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 67 ms 49400 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 78 ms 53240 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 86 ms 54264 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 64 ms 49144 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 87 ms 55132 KB Execution killed with signal 11 (could be triggered by violating memory limits)
21 Runtime error 73 ms 50684 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Runtime error 131 ms 61176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
23 Runtime error 96 ms 53880 KB Execution killed with signal 11 (could be triggered by violating memory limits)
24 Runtime error 83 ms 50652 KB Execution killed with signal 11 (could be triggered by violating memory limits)
25 Runtime error 84 ms 50936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
26 Runtime error 83 ms 50680 KB Execution killed with signal 11 (could be triggered by violating memory limits)
27 Runtime error 117 ms 60248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
28 Runtime error 74 ms 50808 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Runtime error 135 ms 61176 KB Execution killed with signal 11 (could be triggered by violating memory limits)
30 Runtime error 116 ms 58108 KB Execution killed with signal 11 (could be triggered by violating memory limits)
31 Runtime error 82 ms 50936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
32 Runtime error 82 ms 50936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
33 Runtime error 81 ms 50680 KB Execution killed with signal 11 (could be triggered by violating memory limits)
34 Runtime error 113 ms 60024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
35 Runtime error 74 ms 50936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
36 Runtime error 131 ms 60128 KB Execution killed with signal 11 (could be triggered by violating memory limits)
37 Runtime error 136 ms 61048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
38 Runtime error 91 ms 51704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
39 Runtime error 85 ms 50936 KB Execution killed with signal 11 (could be triggered by violating memory limits)
40 Runtime error 85 ms 51704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
41 Runtime error 122 ms 60128 KB Execution killed with signal 11 (could be triggered by violating memory limits)
42 Runtime error 75 ms 51064 KB Execution killed with signal 11 (could be triggered by violating memory limits)