Submission #1053531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1053531		anton	Lottery (CEOI18_lot)	C++17	100 / 100	1651 ms	12924 KiB

lot

#include<bits/stdc++.h>

using namespace std;
#define pii pair<int, int>
int L, N;
int M;

int get_pos(vector<int>& v, int i){
    int res =0;
    for(int step =(1<<20); step>=1; step/=2){
        if(res + step < v.size() && v[res+step]<=i){
            res += step;
        }
    }
    return res;
}
int get_pos(vector<pii>& v, int i){
    int res =0;
    for(int step =(1<<20); step>=1; step/=2){
        if(res + step < v.size() && v[res+step].first<i){
            res += step;
        }
    }
    return res;
}

struct Summer{
    vector<int> ev;

    Summer(int n){
        ev.resize(n+1);
    }


    void add_inc(int l, int r){
        ev[l]++;
        ev[r+1]--;
    }

    vector<int> calc(){
        vector<int> res;
        int cur_s = 0;
        for(int i = 0; i<ev.size()-1; i++){
            
            cur_s += ev[i];
            
            res.push_back(cur_s);
        }
        return res;
    }
};

signed main(){
    cin>>N>>L;
    M = N-L+1;
    vector<int> a(N);
    vector<int> vals;

    for(int i= 0; i<N; i++){
        cin>>a[i];
        vals.push_back(a[i]);
    }

    sort(vals.begin(), vals.end());

    for(int i = 0; i<N; i++){
        a[i] = get_pos(vals, a[i]);
    }

    int Q;
    cin>>Q;

    vector<pii> lims(Q);
    for(int i = 0; i<Q; i++){
        cin>>lims[i].first;
        lims[i].second = i;
    }

    lims.push_back({-1, -1});
    sort(lims.begin(), lims.end());
    lims.push_back({1e9, -1});


    vector<vector<int>> score_d(M, vector<int>(Q+2, 0));

    for(int len = 1; len<N; len++){

        Summer sum(N+1);
        for(int i = N-1; i>=0; i--){
            int cur_a = a[i];
            if(i+len <N && a[i+len]==a[i]){
                sum.add_inc(max(0, i-L+1),i);
            }
        }

        vector<int> dists = sum.calc();
        sum.ev.clear();
        for(int i = 0; i+len<M; i++){
            int q_pos =get_pos(lims, L-dists[i]);
            score_d[i][q_pos]++;
            score_d[i+len][q_pos]++;
        }
    }


    vector<vector<int>> ans(M, vector<int>(Q));
    
    for(int i = 0; i<M; i++){
        int r= 0;
        for(int q = 0; q<lims.size(); q++){
            if(lims[q].second!=-1){
            ans[i][lims[q].second] = r;
           }
           r += score_d[i][q];
           
        }
    }

    for(int i = 0; i<Q; i++){
        for(int j = 0; j<M; j++){
            cout<<ans[j][i]<<" ";
        }
        cout<<endl;
    }


}

Compilation message (stderr)

lot.cpp: In function 'int get_pos(std::vector<int>&, int)':
lot.cpp:11:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   11 |         if(res + step < v.size() && v[res+step]<=i){
      |            ~~~~~~~~~~~^~~~~~~~~~
lot.cpp: In function 'int get_pos(std::vector<std::pair<int, int> >&, int)':
lot.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         if(res + step < v.size() && v[res+step].first<i){
      |            ~~~~~~~~~~~^~~~~~~~~~
lot.cpp: In member function 'std::vector<int> Summer::calc()':
lot.cpp:43:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for(int i = 0; i<ev.size()-1; i++){
      |                        ~^~~~~~~~~~~~
lot.cpp: In function 'int main()':
lot.cpp:90:17: warning: unused variable 'cur_a' [-Wunused-variable]
   90 |             int cur_a = a[i];
      |                 ^~~~~
lot.cpp:110:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |         for(int q = 0; q<lims.size(); q++){
      |                        ~^~~~~~~~~~~~

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