oj.uz

Submission #162137

# Submission time Handle Problem Language Result Execution time Memory
162137 2019-11-06T16:12:56 Z Akashi Lottery (CEOI18_lot) C++14
0 / 100
 806 ms 4512 KB 
///better top wins
#include <bits/stdc++.h>
using namespace std;

struct query{
    int x, p;
    bool operator < (const query &aux)const{
        if(x != aux.x) return x < aux.x;
        return p < aux.p;
    }
};

query q[105];

int n, l, t;
int a[10005], f[10005];
int dp[10005][105];

void add(int p, int x){
    int st = 1, dr = t;
    while(st <= dr){
        int mij = (st + dr) / 2;

        if(q[mij].x < x) st = mij + 1;
        else dr = mij - 1;
    }

    if(q[st].x == x) ++dr;
    dp[p][dr] += 1;
}

int main()
{
//    freopen("1.in", "r", stdin);

    scanf("%d%d", &n, &l);

    for(int i = 1; i <= n ; ++i)
        scanf("%d", &a[i]);

    scanf("%d", &t);
    for(int i = 1; i <= t ; ++i){
        scanf("%d", &q[i].x);
        q[i].p = i;
    }

    sort(q + 1, q + t + 1);

    for(int start = 2; start <= n - l + 1 ; ++start){

        int i = 1, j = start, dif = 0;
        for(int t = 1; t <= l ; ++t, ++i, ++j) if(a[i] != a[j]) ++dif;

        add(1, dif);
        add(start, dif);

        while(j <= n){

            if(a[i - l] != a[j - l]) --dif;
            if(a[i] != a[j]) ++dif;

            add(i - l + 1, dif);
            add(j - l + 1, dif);

            ++i; ++j;
        }
    }

    for(int i = 1; i <= t ; ++i) f[q[i].p] = i;

    for(int i = 1; i <= n - l + 1 ; ++i){
        for(int j = 1; j <= t ; ++j)
            dp[i][j] += dp[i][j - 1];
    }

    for(int i = 1; i <= t ; ++i){
        for(int j = 1; j <= n - l + 1 ; ++j)
            printf("%d ", dp[j][f[i]]);
        printf("\n");
    }

    return 0;
}

Compilation message

lot.cpp: In function 'int main()':
lot.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &l);
     ~~~~~^~~~~~~~~~~~~~~~
lot.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
lot.cpp:41:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &t);
     ~~~~~^~~~~~~~~~
lot.cpp:43:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &q[i].x);
         ~~~~~^~~~~~~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 380 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 806 ms 4512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 806 ms 4512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 380 KB Output isn't correct
3 Halted 0 ms 0 KB -