oj.uz

Submission #307538

# Submission time Handle Problem Language Result Execution time Memory
307538 2020-09-28T14:55:49 Z wildturtle Lottery (CEOI18_lot) C++14
100 / 100
 1167 ms 12408 KB 
#include<bits/stdc++.h>
using namespace std;
int a,n,l,A[10004],C[10004],D[10004][102],ans[10004][102],t,r,st[10004];
pair <int,int> B[10004];
int main() {
    cin>>n>>l;
    for(int i=1;i<=n;i++) {
        cin>>A[i];
    }
    cin>>t;
    for(int i=1;i<=t;i++) {
        cin>>B[i].first;
        B[i].second=i;
    }
    sort(B+1,B+1+t);
    /*for(int i=1;i<=t;i++) {
        st.insert({B[i].first,i});
    }*/
    for(int i=0;i<=n;i++) {
        while(B[r].first<i && r<=t) r++;
        st[i]=r;
    }
    for(int d=1;d<=n-l;d++) {
        for(long long i=1;i<=n;i++)
        C[i]=0;
        for(int i=1;i<=n-d;i++) {
            r=i+d;
            if(A[i]!=A[r]) { C[i]=1; }
        }
        for(long long i=1;i<=n;i++) {
            //cout<<C[i]<<" ";
            C[i]+=C[i-1];
        }
        //cout<<endl;
        for(long long i=1;i+d+l-1<=n;i++) {
            r=i+l-1;
            a=C[r]-C[i-1];
            //cout<<a<<"-";
            /*it=st.upper_bound({a,-1});
            if(it==st.end()) { cout<<"*"; continue; }*/
            //cout<<(*it).second<<" ";
            D[i][st[a]]++;
            D[i+d][st[a]]++;
        }
        //cout<<endl;
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=t;j++) {
            D[i][j]+=D[i][j-1];
        }
    }
    for(int i=1;i<=t;i++) {
        for(int j=1;j<=n;j++) {
            ans[j][B[i].second]=D[j][i];
        }
    }
    for(int i=1;i<=t;i++) {
        for(int j=1;j<=n-l+1;j++) {
            cout<<ans[j][i]<<" ";
        }
        cout<<endl;
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 2 ms 640 KB Output is correct
12 Correct 2 ms 640 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 2 ms 640 KB Output is correct
12 Correct 2 ms 640 KB Output is correct
13 Correct 33 ms 2044 KB Output is correct
14 Correct 22 ms 2048 KB Output is correct
15 Correct 21 ms 2048 KB Output is correct
16 Correct 32 ms 2040 KB Output is correct
17 Correct 29 ms 2048 KB Output is correct
18 Correct 28 ms 2040 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1008 ms 8444 KB Output is correct
2 Correct 999 ms 8568 KB Output is correct
3 Correct 792 ms 8440 KB Output is correct
4 Correct 723 ms 8568 KB Output is correct
5 Correct 311 ms 8568 KB Output is correct
6 Correct 672 ms 8440 KB Output is correct
7 Correct 315 ms 8440 KB Output is correct
8 Correct 479 ms 8404 KB Output is correct
9 Correct 717 ms 8568 KB Output is correct
10 Correct 729 ms 8496 KB Output is correct
11 Correct 44 ms 2808 KB Output is correct
12 Correct 442 ms 7620 KB Output is correct
13 Correct 377 ms 8440 KB Output is correct
14 Correct 386 ms 8440 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1008 ms 8444 KB Output is correct
2 Correct 999 ms 8568 KB Output is correct
3 Correct 792 ms 8440 KB Output is correct
4 Correct 723 ms 8568 KB Output is correct
5 Correct 311 ms 8568 KB Output is correct
6 Correct 672 ms 8440 KB Output is correct
7 Correct 315 ms 8440 KB Output is correct
8 Correct 479 ms 8404 KB Output is correct
9 Correct 717 ms 8568 KB Output is correct
10 Correct 729 ms 8496 KB Output is correct
11 Correct 44 ms 2808 KB Output is correct
12 Correct 442 ms 7620 KB Output is correct
13 Correct 377 ms 8440 KB Output is correct
14 Correct 386 ms 8440 KB Output is correct
15 Correct 772 ms 8440 KB Output is correct
16 Correct 641 ms 8440 KB Output is correct
17 Correct 756 ms 8568 KB Output is correct
18 Correct 739 ms 8440 KB Output is correct
19 Correct 739 ms 8444 KB Output is correct
20 Correct 748 ms 8440 KB Output is correct
21 Correct 747 ms 8404 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 2 ms 640 KB Output is correct
11 Correct 2 ms 640 KB Output is correct
12 Correct 2 ms 640 KB Output is correct
13 Correct 33 ms 2044 KB Output is correct
14 Correct 22 ms 2048 KB Output is correct
15 Correct 21 ms 2048 KB Output is correct
16 Correct 32 ms 2040 KB Output is correct
17 Correct 29 ms 2048 KB Output is correct
18 Correct 28 ms 2040 KB Output is correct
19 Correct 1008 ms 8444 KB Output is correct
20 Correct 999 ms 8568 KB Output is correct
21 Correct 792 ms 8440 KB Output is correct
22 Correct 723 ms 8568 KB Output is correct
23 Correct 311 ms 8568 KB Output is correct
24 Correct 672 ms 8440 KB Output is correct
25 Correct 315 ms 8440 KB Output is correct
26 Correct 479 ms 8404 KB Output is correct
27 Correct 717 ms 8568 KB Output is correct
28 Correct 729 ms 8496 KB Output is correct
29 Correct 44 ms 2808 KB Output is correct
30 Correct 442 ms 7620 KB Output is correct
31 Correct 377 ms 8440 KB Output is correct
32 Correct 386 ms 8440 KB Output is correct
33 Correct 772 ms 8440 KB Output is correct
34 Correct 641 ms 8440 KB Output is correct
35 Correct 756 ms 8568 KB Output is correct
36 Correct 739 ms 8440 KB Output is correct
37 Correct 739 ms 8444 KB Output is correct
38 Correct 748 ms 8440 KB Output is correct
39 Correct 747 ms 8404 KB Output is correct
40 Correct 1035 ms 9304 KB Output is correct
41 Correct 60 ms 8440 KB Output is correct
42 Correct 762 ms 9172 KB Output is correct
43 Correct 723 ms 8952 KB Output is correct
44 Correct 720 ms 8952 KB Output is correct
45 Correct 1167 ms 12280 KB Output is correct
46 Correct 76 ms 8696 KB Output is correct
47 Correct 838 ms 12408 KB Output is correct
48 Correct 797 ms 10488 KB Output is correct
49 Correct 795 ms 11256 KB Output is correct