답안 #93396 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
93396	2019-01-08T08:13:15 Z	SpeedOfMagic	Lottery (CEOI18_lot)	C++17	65 / 100	266 ms	8184 KB

/** MIT License Copyright (c) 2018 Vasilyev Daniil **/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
#pragma GCC optimize("Ofast")
template<typename T> using v = vector<T>;
template<typename T, typename U>  using hmap = __gnu_pbds::gp_hash_table<T, U>;
//#define int long long
typedef long double ld;
typedef string str;
typedef vector<int> vint;
#define rep(a, l, r) for(int a = (l); a < (r); a++)
#define pb push_back
#define fs first
#define sc second
#define sz(a) ((int) a.size())
const long long inf = 4611686018427387903; //2^62 - 1
#if 0  //FileIO
const string fileName = "";
ifstream fin ((fileName == "" ? "input.txt"  : fileName + ".in" ));
ofstream fout((fileName == "" ? "output.txt" : fileName + ".out"));
#define get fin>>
#define put fout<<
#else
#define get cin>>
#define put cout<<
#endif
#define eol put endl
#define check(a) put #a << ": " << a << endl;
void read() {}     template<typename Arg,typename... Args> void read (Arg& arg,Args&... args){get (arg)     ;read(args...) ;}
void print(){}     template<typename Arg,typename... Args> void print(Arg  arg,Args...  args){put (arg)<<" ";print(args...);}
void debug(){eol;} template<typename Arg,typename... Args> void debug(Arg  arg,Args...  args){put (arg)<<" ";debug(args...);}
int getInt(){int a; get a; return a;}
//code goes here

void run() {
    int n, l;
    read(n, l);

    int a[n];
    rep(i, 0, n)
        get a[i];

    map<int, short> hsh;
    short p = 0;
    rep(i, 0, n) {
        if (!hsh.count(a[i]))
            hsh[a[i]] = p++;
        a[i] = hsh[a[i]];
    }

    int m = n - l + 1;

    int q;
    get q;

    if (q == 1) {
        map<int, int> buckets;
        const long long mod = 36028797018963913;
        long long hshes[m];
        rep(i, 0, m) {
            long long curHsh = 0;
            rep(j, 0, l) {
                long long t = a[i + j];
                curHsh = ((curHsh * 29ll) % mod + t) % mod;
            }
            buckets[curHsh]++;
            hshes[i] = curHsh;
        }
        rep(i, 0, m)
            print(buckets[hshes[i]] - 1);
    } else {
        short vals[m][m];
        rep(i, 0, m)
            rep(j, 0, m)
                vals[i][j] = l + (i == j);

        rep(i, 0, l) {
            v<short> buckets[p];
            rep(j, 0, m) {
                for (short k : buckets[a[i + j]]) {
                    vals[j][k]--;
                    vals[k][j]--;
                }

                buckets[a[i + j]].pb(j);
            }
        }

        rep(i, 0, m)
            sort(vals[i], vals[i] + m);

        for (; q; q--) {
            short k;
            get k;
            rep(i, 0, m)
                print((upper_bound(vals[i], vals[i] + m, k) - vals[i]));
            eol;
        }
    }
}

int32_t main() {srand(time(0)); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); put fixed; put setprecision(15); run(); return 0;}

Subtask #1
25.0 / 25.0

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

Subtask #2
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	3 ms	376 KB	Output is correct
9	Correct	3 ms	376 KB	Output is correct
10	Correct	3 ms	504 KB	Output is correct
11	Correct	3 ms	504 KB	Output is correct
12	Correct	3 ms	504 KB	Output is correct
13	Correct	68 ms	8184 KB	Output is correct
14	Correct	53 ms	4088 KB	Output is correct
15	Correct	72 ms	3960 KB	Output is correct
16	Correct	95 ms	6648 KB	Output is correct
17	Correct	55 ms	6008 KB	Output is correct
18	Correct	57 ms	6008 KB	Output is correct

Subtask #3
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	504 KB	Output is correct
2	Correct	4 ms	508 KB	Output is correct
3	Correct	5 ms	504 KB	Output is correct
4	Correct	26 ms	760 KB	Output is correct
5	Correct	266 ms	760 KB	Output is correct
6	Correct	76 ms	1016 KB	Output is correct
7	Correct	263 ms	564 KB	Output is correct
8	Correct	221 ms	632 KB	Output is correct
9	Correct	38 ms	632 KB	Output is correct
10	Correct	24 ms	632 KB	Output is correct
11	Correct	24 ms	504 KB	Output is correct
12	Correct	158 ms	1016 KB	Output is correct
13	Correct	258 ms	1108 KB	Output is correct
14	Correct	258 ms	1040 KB	Output is correct

Subtask #4
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	504 KB	Output is correct
2	Correct	4 ms	508 KB	Output is correct
3	Correct	5 ms	504 KB	Output is correct
4	Correct	26 ms	760 KB	Output is correct
5	Correct	266 ms	760 KB	Output is correct
6	Correct	76 ms	1016 KB	Output is correct
7	Correct	263 ms	564 KB	Output is correct
8	Correct	221 ms	632 KB	Output is correct
9	Correct	38 ms	632 KB	Output is correct
10	Correct	24 ms	632 KB	Output is correct
11	Correct	24 ms	504 KB	Output is correct
12	Correct	158 ms	1016 KB	Output is correct
13	Correct	258 ms	1108 KB	Output is correct
14	Correct	258 ms	1040 KB	Output is correct
15	Incorrect	41 ms	888 KB	Output isn't correct
16	Halted	0 ms	0 KB	-

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	3 ms	376 KB	Output is correct
9	Correct	3 ms	376 KB	Output is correct
10	Correct	3 ms	504 KB	Output is correct
11	Correct	3 ms	504 KB	Output is correct
12	Correct	3 ms	504 KB	Output is correct
13	Correct	68 ms	8184 KB	Output is correct
14	Correct	53 ms	4088 KB	Output is correct
15	Correct	72 ms	3960 KB	Output is correct
16	Correct	95 ms	6648 KB	Output is correct
17	Correct	55 ms	6008 KB	Output is correct
18	Correct	57 ms	6008 KB	Output is correct
19	Correct	4 ms	504 KB	Output is correct
20	Correct	4 ms	508 KB	Output is correct
21	Correct	5 ms	504 KB	Output is correct
22	Correct	26 ms	760 KB	Output is correct
23	Correct	266 ms	760 KB	Output is correct
24	Correct	76 ms	1016 KB	Output is correct
25	Correct	263 ms	564 KB	Output is correct
26	Correct	221 ms	632 KB	Output is correct
27	Correct	38 ms	632 KB	Output is correct
28	Correct	24 ms	632 KB	Output is correct
29	Correct	24 ms	504 KB	Output is correct
30	Correct	158 ms	1016 KB	Output is correct
31	Correct	258 ms	1108 KB	Output is correct
32	Correct	258 ms	1040 KB	Output is correct
33	Incorrect	41 ms	888 KB	Output isn't correct
34	Halted	0 ms	0 KB	-

답안 #93396

Compilation message

Subtask #1 25.0 / 25.0

Subtask #2 20.0 / 20.0

Subtask #3 20.0 / 20.0

Subtask #4 0 / 15.0

Subtask #5 0 / 20.0

Subtask #1
25.0 / 25.0

Subtask #2
20.0 / 20.0

Subtask #3
20.0 / 20.0

Subtask #4
0 / 15.0

Subtask #5
0 / 20.0