oj.uz

Submission #134739

# Submission time Handle Problem Language Result Execution time Memory
134739 2019-07-23T08:16:35 Z miguel Lottery (CEOI18_lot) C++14
0 / 100
 1012 ms 552 KB 
#include<bits/stdc++.h>
using namespace std;
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define sz size()
#define x first
#define y second
#define pi pair <int, int>
#define pii pair <int, pi>
#define vi vector <int>
const ll mod = 998244353;
int n, a[10001], q, l, idx[10001], ans[101][10002], miss[10003];
pi qry[1001];

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin>>n>>l;
    for(int i=1; i<=n; i++) cin>>a[i];
    cin>>q;
    for(int i=1; i<=q; i++){
        cin>>qry[i].x;
        qry[i].y=i;
    }
    sort(qry+1, qry+q+1);
    for(int xd=0; xd<=n+1; xd++){
        for(int i=1; i<=q; i++){
            if(qry[i].x<=xd) idx[xd]=i;
        }
    }
    for(int sh=1; sh<=n-l; sh++){
        fill(miss, miss+n+1, 0);
        //for(int i=1; i<=n; i++) cout<<miss[i];
        for(int i=1; i+sh<=n; i++){
            if(a[i]!=a[i+sh]){
                miss[i]++;
                miss[(min(n+2, i+l))]--;
            }
        }
        for(int i=1; i<=n; i++){
            miss[i]+=miss[i-1];
        }
        //if(sh==1){for(int i=1; i<=n; i++) cout<<miss[i]<<" "; cout<<endl;}
        for(int i=l; i<=n-sh; i++){
            ans[idx[miss[i]]][i-l+1]++;
            ans[idx[miss[i]]][i-l+1+sh]++;
        }
    }
    for(int i=1; i<=q; i++){
        for(int id=1; id<=n; id++) ans[i][id]+=ans[i-1][id];
    }
    for(int i=1; i<=q; i++){
        for(int id=1; id<=q; id++){
            if(qry[id].y==i){
                for(int xd=1; xd<=n-l+1; xd++) cout<<ans[id][xd]<<" ";
                cout<<"\n";
            }
        }
    }
}

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 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 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

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

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1012 ms 552 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 376 KB Output isn't correct
3 Halted 0 ms 0 KB -