Submission #598293

#	Time	Username	Problem	Language	Result	Execution time	Memory
598293		1bin	Lottery (CEOI18_lot)	C++14	100 / 100	1253 ms	8368 KiB

lot

    #include <bits/stdc++.h>
    
    using namespace std;
    
    #define all(v) v.begin(), v.end()
    typedef long long ll;
    const int NMAX = 1e4 + 5;
    int n, l, d, a[NMAX], q, x, qry[105], p[NMAX][105], ix;
    vector<int> tmp;
    
    void add(int i, int v){
        while(v > tmp[ix]) ix++;
        while(ix && tmp[ix - 1] >= v) ix--;
        p[i][ix]++;
        return;
    }
    
    int main(void){
        ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
        
        cin >> n >> l;
        for(int i = 0; i < n; i++) cin >> a[i];
        cin >> q;
        for(int i = 0; i < q; i++){
            cin >> qry[i]; tmp.emplace_back(qry[i]);
        }
        tmp.emplace_back(1e9);
        sort(all(tmp));
        tmp.erase(unique(all(tmp)), tmp.end());
        
        for(int d = 1; d + l - 1 < n; d++){
            int v = 0;
            for(int i = 0; i < l; i++)
                if(a[i] != a[i + d]) v++;
            add(0, v); add(d, v);
            for(int i = 1; i + l - 1 + d < n; i++){
                if(a[i - 1] != a[i - 1 + d]) v--;
                if(a[i + l - 1] != a[i + l - 1 + d]) v++;
                add(i,v); add(i + d, v);
            }
        }
        
        for(int i = 0; i + l - 1 < n; i++)
            for(int j = 1; j < tmp.size(); j++) p[i][j] += p[i][j - 1];
        for(int j = 0; j < q; j++){
            for(int i = 0; i + l - 1 < n; i++) cout << p[i][lower_bound(all(tmp), qry[j]) - tmp.begin()] << ' ';
            cout << '\n';
        }
        return 0;
    }

Compilation message (stderr)

lot.cpp: In function 'int main()':
lot.cpp:44:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |             for(int j = 1; j < tmp.size(); j++) p[i][j] += p[i][j - 1];
      |                            ~~^~~~~~~~~~~~

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