oj.uz

답안 #254390

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
254390 2020-07-29T23:30:18 Z MarcoMeijer Lottery (CEOI18_lot) C++14
80 / 100
 3000 ms 4752 KB 
#include <bits/stdc++.h>
using namespace std;

// macros
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define FOR(a,b) for(auto& a : b)
#define all(a) a.begin(), a.end()
#define INF 1e9
#define EPS 1e-9
#define pb push_back
#define popb pop_back
#define fi first
#define se second
#define sz size()

// input
template<class T> void IN(T& x) {cin >> x;}
template<class H, class... T> void IN(H& h, T&... t) {IN(h); IN(t...); }

// output
template<class T1, class T2> void OUT(const pair<T1,T2>& x);
template<class T> void OUT(const T& x) {cout << x;}
template<class H, class... T> void OUT(const H& h, const T&... t) {OUT(h); OUT(t...); }
template<class T1, class T2> void OUT(const pair<T1,T2>& x) {OUT(x.fi," ",x.se);}
template<class... T> void OUTL(const T&... t) {OUT(t..., "\n"); }

//===================//
//  Added libraries  //
//===================//

//===================//
//end added libraries//
//===================//

void program();
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    program();
}


//===================//
//   begin program   //
//===================//

const int MX = 10002;
int n, m, l, q;
int a[MX], b[MX], k[MX];
int SK[MX], K[MX], RSK[MX];
vi f[MX];
int dist[MX], sdist[MX];
int ans[101][MX];

int getDif(int x, int y) {
    int ans=0;
    RE(i,l) if(a[x+i] != a[y+i]) ans++;
    return ans;
}
void addDist(int v, int i, int del) {
    FOR(u,f[v]) {
        int v=u-i;
        if(v<0) continue;
        if(v>n-l+1) break;
        dist[v] += del;
    }
}
void getDif(int x) {
    // fill dist table
    if(x == 0) {
        RE(i,n) dist[i] = l;
        RE(i,l) {
            addDist(a[x+i],i,-1);
        }
    } else {
        addDist(a[x-1],0,1);
        REV(i,0,n-l+1) dist[i+1] = dist[i];
        addDist(a[x+l-1],l-1,-1);
        dist[0] = getDif(0,x);
    }

    // answer queries
    RE(i,q) ans[i][x] = 0;
    ans[0][x] = -1;
    RE(j,n-l+1) {
        ans[lower_bound(K,K+q,dist[j])-K][x]++;
    }
    REP(i,1,q) ans[i][x] += ans[i-1][x];
}

void program() {
    IN(n, l);
    RE(i,n) IN(a[i]);
    IN(q);
    RE(i,q) IN(k[i]);
    RE(i,q) SK[i]=i;
    sort(SK,SK+q,[](int i, int j) {
        return k[i]<k[j];
    });
    RE(i,q) K[i] = k[i];
    sort(K,K+q);
    RE(i,q) RSK[SK[i]] = i;

    RE(i,n) b[i]=a[i];
    sort(b,b+n);
    m = unique(b,b+n)-b;
    RE(i,n) a[i] = lower_bound(b,b+m,a[i])-b;
    RE(i,n) f[a[i]].pb(i);

    RE(i,n-l+1) getDif(i);
    OUTL();

    RE(i,q) {
        RE(j,n-l+1) OUT(j==0?"":" ",ans[RSK[i]][j]);
        OUTL();
    }
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 640 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 2 ms 768 KB Output is correct
11 Correct 2 ms 768 KB Output is correct
12 Correct 2 ms 768 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 640 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 2 ms 768 KB Output is correct
11 Correct 2 ms 768 KB Output is correct
12 Correct 2 ms 768 KB Output is correct
13 Correct 44 ms 760 KB Output is correct
14 Correct 20 ms 896 KB Output is correct
15 Correct 15 ms 896 KB Output is correct
16 Correct 37 ms 1016 KB Output is correct
17 Correct 29 ms 896 KB Output is correct
18 Correct 30 ms 896 KB Output is correct

Subtask #3
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 827 ms 1244 KB Output is correct
2 Correct 693 ms 1012 KB Output is correct
3 Correct 434 ms 888 KB Output is correct
4 Correct 360 ms 1144 KB Output is correct
5 Correct 253 ms 892 KB Output is correct
6 Correct 330 ms 888 KB Output is correct
7 Correct 382 ms 904 KB Output is correct
8 Correct 604 ms 1016 KB Output is correct
9 Correct 409 ms 888 KB Output is correct
10 Correct 405 ms 1016 KB Output is correct
11 Correct 32 ms 640 KB Output is correct
12 Correct 269 ms 1016 KB Output is correct
13 Correct 203 ms 872 KB Output is correct
14 Correct 237 ms 888 KB Output is correct

Subtask #4
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 827 ms 1244 KB Output is correct
2 Correct 693 ms 1012 KB Output is correct
3 Correct 434 ms 888 KB Output is correct
4 Correct 360 ms 1144 KB Output is correct
5 Correct 253 ms 892 KB Output is correct
6 Correct 330 ms 888 KB Output is correct
7 Correct 382 ms 904 KB Output is correct
8 Correct 604 ms 1016 KB Output is correct
9 Correct 409 ms 888 KB Output is correct
10 Correct 405 ms 1016 KB Output is correct
11 Correct 32 ms 640 KB Output is correct
12 Correct 269 ms 1016 KB Output is correct
13 Correct 203 ms 872 KB Output is correct
14 Correct 237 ms 888 KB Output is correct
15 Correct 864 ms 1096 KB Output is correct
16 Correct 315 ms 1016 KB Output is correct
17 Correct 415 ms 888 KB Output is correct
18 Correct 348 ms 876 KB Output is correct
19 Correct 366 ms 888 KB Output is correct
20 Correct 362 ms 1144 KB Output is correct
21 Correct 343 ms 888 KB Output is correct

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 640 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 640 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 1 ms 768 KB Output is correct
9 Correct 1 ms 768 KB Output is correct
10 Correct 2 ms 768 KB Output is correct
11 Correct 2 ms 768 KB Output is correct
12 Correct 2 ms 768 KB Output is correct
13 Correct 44 ms 760 KB Output is correct
14 Correct 20 ms 896 KB Output is correct
15 Correct 15 ms 896 KB Output is correct
16 Correct 37 ms 1016 KB Output is correct
17 Correct 29 ms 896 KB Output is correct
18 Correct 30 ms 896 KB Output is correct
19 Correct 827 ms 1244 KB Output is correct
20 Correct 693 ms 1012 KB Output is correct
21 Correct 434 ms 888 KB Output is correct
22 Correct 360 ms 1144 KB Output is correct
23 Correct 253 ms 892 KB Output is correct
24 Correct 330 ms 888 KB Output is correct
25 Correct 382 ms 904 KB Output is correct
26 Correct 604 ms 1016 KB Output is correct
27 Correct 409 ms 888 KB Output is correct
28 Correct 405 ms 1016 KB Output is correct
29 Correct 32 ms 640 KB Output is correct
30 Correct 269 ms 1016 KB Output is correct
31 Correct 203 ms 872 KB Output is correct
32 Correct 237 ms 888 KB Output is correct
33 Correct 864 ms 1096 KB Output is correct
34 Correct 315 ms 1016 KB Output is correct
35 Correct 415 ms 888 KB Output is correct
36 Correct 348 ms 876 KB Output is correct
37 Correct 366 ms 888 KB Output is correct
38 Correct 362 ms 1144 KB Output is correct
39 Correct 343 ms 888 KB Output is correct
40 Correct 1911 ms 2568 KB Output is correct
41 Correct 29 ms 1144 KB Output is correct
42 Correct 1008 ms 2484 KB Output is correct
43 Correct 858 ms 2216 KB Output is correct
44 Correct 882 ms 2524 KB Output is correct
45 Execution timed out 3057 ms 4752 KB Time limit exceeded
46 Halted 0 ms 0 KB -