oj.uz

Submission #946740

# Submission time Handle Problem Language Result Execution time Memory
946740 2024-03-15T01:26:07 Z guagua0407 Lottery (CEOI18_lot) C++17
25 / 100
 116 ms 65536 KB 
//#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;
    vector<vector<int>> st(n),en(n);
    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});
            st[L].push_back(j-i);
            if(R<n-1) en[R+1].push_back(j-i);
        }
    }
    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(j+n>=0 and j+n<3*n);
            //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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 1116 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 2 ms 1628 KB Output is correct
11 Correct 2 ms 1628 KB Output is correct
12 Correct 2 ms 1628 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 1116 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 2 ms 1628 KB Output is correct
11 Correct 2 ms 1628 KB Output is correct
12 Correct 2 ms 1628 KB Output is correct
13 Correct 46 ms 32592 KB Output is correct
14 Correct 47 ms 30904 KB Output is correct
15 Correct 44 ms 30904 KB Output is correct
16 Runtime error 56 ms 32824 KB Memory limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 116 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 116 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 2 ms 1116 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 2 ms 1628 KB Output is correct
11 Correct 2 ms 1628 KB Output is correct
12 Correct 2 ms 1628 KB Output is correct
13 Correct 46 ms 32592 KB Output is correct
14 Correct 47 ms 30904 KB Output is correct
15 Correct 44 ms 30904 KB Output is correct
16 Runtime error 56 ms 32824 KB Memory limit exceeded
17 Halted 0 ms 0 KB -