Submission #95197

#	Time	Username	Problem	Language	Result	Execution time	Memory
95197		onjo0127	Lottery (CEOI18_lot)	C++11	100 / 100	499 ms	8488 KiB

lot

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

int A[10009], K[111], ch[10009], D[10009][111];

int main() {
    int l, N; scanf("%d%d",&N,&l);
    for(int i=1; i<=N; i++) scanf("%d",&A[i]);
    vector<int> S;
    int Q; scanf("%d",&Q);
    for(int i=1; i<=Q; i++) {
        scanf("%d",&K[i]);
        S.push_back(K[i]);
    } S.push_back(1e9);
    sort(S.begin(), S.end()); S.resize(unique(S.begin(), S.end()) - S.begin());
    for(int i=0; i<=l; i++) ch[i] = (int)S.size() - 1;
    for(int i=0, j=0; i<(int)S.size()-1; i++) {
        while(j <= S[i]) ch[j++] = i;
    }
    for(int i=1; i<=N-l; i++) {
        int s = 0;
        for(int j=1; j<=l; j++) s += (A[j] != A[j+i]);
        for(int j=1; j+i+l-1<=N; j++) {
            ++D[j][ch[s]]; ++D[j+i][ch[s]];
            s -= (A[j] != A[j+i]);
            s += (A[j+l] != A[j+i+l]);
        }
    }
    for(int i=1; i<=N-l+1; i++) for(int j=0, s=0; j<=Q; j++) s += D[i][j], D[i][j] = s;
    for(int i=1; i<=Q; i++) {
        int x = lower_bound(S.begin(), S.end(), K[i]) - S.begin();
        for(int j=1; j<=N-l+1; j++) printf("%d ",D[j][x]);
        puts("");
    }
    return 0;
}

Compilation message (stderr)

lot.cpp: In function 'int main()':
lot.cpp:7:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int l, N; scanf("%d%d",&N,&l);
               ~~~~~^~~~~~~~~~~~~~
lot.cpp:8:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i=1; i<=N; i++) scanf("%d",&A[i]);
                             ~~~~~^~~~~~~~~~~~
lot.cpp:10:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     int Q; scanf("%d",&Q);
            ~~~~~^~~~~~~~~
lot.cpp:12:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&K[i]);
         ~~~~~^~~~~~~~~~~~

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20