Submission #946731

#	Time	Username	Problem	Language	Result	Execution time	Memory
946731		guagua0407	Lottery (CEOI18_lot)	C++17	25 / 100	76 ms	65536 KiB

lot

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

int main() {_
    int n,l;
    cin>>n>>l;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    vector<pair<pair<int,int>,int>> vec;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            if(a[i]==a[j]) continue;
            int L=max(0,i-(l-max({0,l-(i+1),l-(j+1)}))+1);
            int R=i-max({0,l-(n-i),l-(n-j)});
            if(R<L) continue;
            //cout<<L<<' '<<R<<'\n';
            vec.push_back({{L,R},j-i});
        }
    }
    //return 0;
    vector<vector<int>> st(n),en(n);
    for(auto v:vec){
        st[v.f.f].push_back(v.s);
        if(v.f.s<n-1) en[v.f.s+1].push_back(v.s);
    }
    int q;
    cin>>q;
    vector<pair<int,int>> qs;
    for(int i=0;i<q;i++){
        int x;
        cin>>x;
        qs.push_back({x,i});
    }
    sort(all(qs));
    sort(all(vec));
    vector<int> cnt(3*n);
    vector<int> id(l+1);
    for(int i=0;i<=l;i++){
        int pos=lower_bound(all(qs),make_pair(i,-1))-qs.begin();
        id[i]=((pos==q)?-1:pos);
    }
    //return 0;
    vector<vector<int>> ans(n,vector<int>(q));
    for(int i=0;i<n-l+1;i++){
        for(auto v:st[i]){
            assert(v+n>=0 and v+n<3*n);
            cnt[v+n]++;
        }
        for(auto v:en[i]){
            assert(v+n>=0 and v+n<3*n);
            cnt[v+n]--;
        }
        for(int j=-i;j<n-i-l+1;j++){
            if(j==0) continue;
            //cout<<cnt[n+j]<<' ';
            //assert(cnt[n+j]>=0 and cnt[n+j]<=l);
            if(id[cnt[n+j]]!=-1){
                ans[i][id[cnt[n+j]]]++;
            }
        }
        for(int j=1;j<q;j++){
            ans[i][j]+=ans[i][j-1];
        }
        //cout<<'\n';
    }
    //return 0;
    vector<int> tmp(q);
    for(int i=0;i<q;i++){
        assert(qs[i].s>=0 and qs[i].s<q);
        tmp[qs[i].s]=i;
    }
    for(int j=0;j<q;j++){
        for(int i=0;i<n-l+1;i++){
            assert(tmp[j]>=0 and tmp[j]<q);
            cout<<ans[i][tmp[j]]<<' ';
        }
        cout<<'\n';
    }
    return 0;
}
//maybe its multiset not set
//yeeorz
//laborz

Compilation message (stderr)

lot.cpp: In function 'void setIO(std::string)':
lot.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
lot.cpp:16:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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