oj.uz

Submission #162139

# Submission time Handle Problem Language Result Execution time Memory
162139 2019-11-06T16:15:27 Z Akashi Lottery (CEOI18_lot) C++14
20 / 100
 1168 ms 4600 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;
    if(x > q[dr].x) return ;

    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:38: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:41:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]);
         ~~~~~^~~~~~~~~~~~~
lot.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &t);
     ~~~~~^~~~~~~~~~
lot.cpp:45: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 252 KB Output is correct
2 Incorrect 2 ms 376 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 252 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 935 ms 4504 KB Output is correct
2 Correct 1168 ms 4600 KB Output is correct
3 Correct 659 ms 4580 KB Output is correct
4 Correct 571 ms 4484 KB Output is correct
5 Correct 181 ms 2552 KB Output is correct
6 Correct 508 ms 4380 KB Output is correct
7 Correct 256 ms 2680 KB Output is correct
8 Correct 472 ms 3372 KB Output is correct
9 Correct 559 ms 4472 KB Output is correct
10 Correct 575 ms 4600 KB Output is correct
11 Correct 35 ms 1144 KB Output is correct
12 Correct 346 ms 3448 KB Output is correct
13 Correct 244 ms 2908 KB Output is correct
14 Correct 262 ms 2936 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 935 ms 4504 KB Output is correct
2 Correct 1168 ms 4600 KB Output is correct
3 Correct 659 ms 4580 KB Output is correct
4 Correct 571 ms 4484 KB Output is correct
5 Correct 181 ms 2552 KB Output is correct
6 Correct 508 ms 4380 KB Output is correct
7 Correct 256 ms 2680 KB Output is correct
8 Correct 472 ms 3372 KB Output is correct
9 Correct 559 ms 4472 KB Output is correct
10 Correct 575 ms 4600 KB Output is correct
11 Correct 35 ms 1144 KB Output is correct
12 Correct 346 ms 3448 KB Output is correct
13 Correct 244 ms 2908 KB Output is correct
14 Correct 262 ms 2936 KB Output is correct
15 Incorrect 670 ms 4404 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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