Submission #26993

#	Time	Username	Problem	Language	Result	Execution time	Memory
26993		zoomswk	Brunhilda’s Birthday (BOI13_brunhilda)	C++14	17.78 / 100	1000 ms	178152 KiB

brunhilda

#include <bits/stdc++.h>
using namespace std;

int m;
vector<int> di[3000005];
int p[100005];
int t[200005];
int dp[3000005];

int qr(int l, int r){
    int res = 1e9;
    for(l+=m, r+=m; l<r; l>>=1, r>>=1){
        if(l&1) res = min(res, t[l++]);
        if(r&1) res = min(res, t[--r]);
    }
    return res;
}

void upd(int idx, int v){
    for(t[idx+=m]=v; idx>1; idx>>=1) t[idx>>1] = min(t[idx], t[idx^1]);
    return;
}

int main(){
    int Q;
    scanf("%d%d", &m, &Q);
    for(int i=1; i<=m; i++){
        scanf("%d", &p[i]);
        for(int j=p[i]; j<=(int)(3e6); j+=p[i]) di[j].push_back(i);
    }
    for(int i=1; i<=(int)(3e6); i++){
        for(int x : di[i]) upd(x, 1e9);
        dp[i] = qr(1, m+1) + 1;
        for(int x : di[i]) upd(x, dp[i]);
    }
    while(Q--){
        int x;
        scanf("%d", &x);
        if(dp[x] <= 1e7) printf("%d\n", dp[x]);
        else printf("oo\n");
    }
    return 0;
}

Compilation message (stderr)

brunhilda.cpp: In function 'int main()':
brunhilda.cpp:26:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &m, &Q);
                          ^
brunhilda.cpp:28:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &p[i]);
                           ^
brunhilda.cpp:38:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
                        ^

• Subtask 1: 17.77777777777778 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 60