제출 #1053500

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1053500		anton	Lottery (CEOI18_lot)	C++17	80 / 100	3058 ms	5180 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;
}

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<int> lims(Q);
    for(int i = 0; i<Q; i++){
        cin>>lims[i];
    }

        vector<vector<int>> score(M, vector<int>(Q, 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++){
            for(int q=  0; q<Q; q++){
                if(dists[i]>=L-lims[q]){
                    score[i][q]++;
                    score[i+len][q]++;
                }
            }
        }
    }

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

}

컴파일 시 표준 에러 (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 member function 'std::vector<int> Summer::calc()':
lot.cpp:34:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         for(int i = 0; i<ev.size()-1; i++){
      |                        ~^~~~~~~~~~~~
lot.cpp: In function 'int main()':
lot.cpp:75:17: warning: unused variable 'cur_a' [-Wunused-variable]
   75 |             int cur_a = a[i];
      |                 ^~~~~

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