Submission #826306

#	Time	Username	Problem	Language	Result	Execution time	Memory
826306		gagik_2007	Lottery (CEOI18_lot)	C++17	100 / 100	247 ms	8616 KiB

lot

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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define ff first
#define ss second

ll ttt;
const ll INF=1e18;
const ll MOD=1e9+7;
const ll N=2007;
const ll M=10007;
const ll Q=107;
ll n,m,k;
ll a[M];
ll dp[2][M];
vector<pair<int,int>>qs;
vector<int>q;
int lb[M];
int res[M][Q];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    cin>>m;
    for(int i=0;i<m;i++){
        int x;
        cin>>x;
        q.push_back(x);
        qs.push_back({x,i});
    }
    qs.push_back({n+1,m});
    sort(qs.begin(),qs.end());
    int cur=0;
    vector<int>revq(m+1);
    for(int i=0;i<qs.size();i++){
        revq[qs[i].ss]=i;
        while(cur<=qs[i].ff){
            lb[cur]=i;
            cur++;
        }
    }
    for(int i=1;i+k-1<n;i++){
        for(int j=i;j-i<k;j++){
            dp[0][i]+=(a[j-i]!=a[j]);
        }
        res[0][lb[dp[0][i]]]++;
        res[i][lb[dp[0][i]]]++;
    }
    for(int i=1;i+k-1<n;i++){
        for(int j=i+1;j+k-1<n;j++){
            dp[1][j]=dp[0][j-1];
            dp[1][j]-=(a[i-1]!=a[j-1]);
            dp[1][j]+=(a[i+k-1]!=a[j+k-1]);
            res[i][lb[dp[1][j]]]++;
            res[j][lb[dp[1][j]]]++;
        }
        for(int j=0;j<=n;j++){
            dp[0][j]=dp[1][j];
        }
    }
    for(int i=0;i+k-1<n;i++){
        for(int j=1;j<=m;j++){
            res[i][j]+=res[i][j-1];
        }
    }
    for(int i=0;i<m;i++){
        for(int j=0;j+k-1<n;j++){
            cout<<res[j][revq[i]]<<" ";
        }
        cout<<endl;
    }
}

Compilation message (stderr)

lot.cpp: In function 'int main()':
lot.cpp:47:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for(int i=0;i<qs.size();i++){
      |                 ~^~~~~~~~~~

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