Submission #126089

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
126089	2019-07-07T03:06:39 Z	briansu	Lottery (CEOI18_lot)	C++14	100 / 100	2695 ms	8564 KB

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
#define REP(i, n) for(int i = 0;i < n;i ++)
#define REP1(i, n) for(int i = 1;i <= n;i ++)
#define FILL(i, n) memset(i, n, sizeof(i))
#define X first
#define Y second
#define pb push_back
#define SZ(_a) ((int)(_a).size())
#define ALL(_a) (_a).begin(), (_a).end()
#ifdef brian
#define IOS()
template<typename T>void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...t> void _do(T &&x, t &&...X){cerr<<x<<", ";_do(X...);}
#define debug(...) {\
	fprintf(stderr, "%s - %d (%s) = ", __PRETTY_FUNCTION__, __LINE__, #__VA_ARGS__);\
	_do(__VA_ARGS__);\
}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define debug(...)
#define endl '\n'
#endif

const ll MAXn = 1e4 + 5;
const ll INF = ll(1e17);
const ll MOD = 1000000007;
const ll bs = 880301;

int dt[MAXn];
int qr[MAXn];

int d[MAXn], a[105][MAXn];

vector<ll> qdt;

int main(){
	IOS();
	ll n, l;
	cin>>n>>l;
	REP1(i, n)cin>>d[i];
	ll q;
	cin>>q;
	REP1(i, q)cin>>qr[i], qdt.pb(i);
	sort(ALL(qdt), [](int a,int b){return qr[a] < qr[b];});

	REP1(dif, n - l)
	{
		REP1(j, n - dif)dt[j] = (d[j] != d[j + dif]) + dt[j-1];
		vector<ll> v;
		REP1(i, n - l + 1 - dif)v.pb(i);
		sort(ALL(v), [&](int a,int b){return dt[a + l - 1] - dt[a - 1] < dt[b + l - 1] - dt[b - 1];});
		ll it = 0;
		for(auto t:qdt)while(it < SZ(v) && qr[t] >= dt[v[it] + l - 1] - dt[v[it] - 1])a[t][v[it]]++, a[t][v[it] + dif]++, it++;
	}
	REP1(x, q - 1)REP1(i, n - l + 1)a[qdt[x]][i] += a[qdt[x - 1]][i];
	REP1(t, q)REP1(i, n - l + 1)cout<<a[t][i]<<" \n"[i == n - l + 1];
}

Subtask #1
25.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	508 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	380 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	504 KB	Output is correct
9	Correct	3 ms	504 KB	Output is correct
10	Correct	4 ms	504 KB	Output is correct
11	Correct	4 ms	504 KB	Output is correct
12	Correct	4 ms	504 KB	Output is correct

Subtask #2
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	508 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	380 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	504 KB	Output is correct
9	Correct	3 ms	504 KB	Output is correct
10	Correct	4 ms	504 KB	Output is correct
11	Correct	4 ms	504 KB	Output is correct
12	Correct	4 ms	504 KB	Output is correct
13	Correct	76 ms	516 KB	Output is correct
14	Correct	34 ms	588 KB	Output is correct
15	Correct	30 ms	504 KB	Output is correct
16	Correct	51 ms	760 KB	Output is correct
17	Correct	43 ms	632 KB	Output is correct
18	Correct	43 ms	604 KB	Output is correct

Subtask #3
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2277 ms	964 KB	Output is correct
2	Correct	2276 ms	896 KB	Output is correct
3	Correct	1881 ms	836 KB	Output is correct
4	Correct	1582 ms	952 KB	Output is correct
5	Correct	441 ms	576 KB	Output is correct
6	Correct	1407 ms	816 KB	Output is correct
7	Correct	495 ms	760 KB	Output is correct
8	Correct	909 ms	632 KB	Output is correct
9	Correct	1574 ms	984 KB	Output is correct
10	Correct	1603 ms	848 KB	Output is correct
11	Correct	87 ms	376 KB	Output is correct
12	Correct	1032 ms	760 KB	Output is correct
13	Correct	628 ms	504 KB	Output is correct
14	Correct	666 ms	632 KB	Output is correct

Subtask #4
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2277 ms	964 KB	Output is correct
2	Correct	2276 ms	896 KB	Output is correct
3	Correct	1881 ms	836 KB	Output is correct
4	Correct	1582 ms	952 KB	Output is correct
5	Correct	441 ms	576 KB	Output is correct
6	Correct	1407 ms	816 KB	Output is correct
7	Correct	495 ms	760 KB	Output is correct
8	Correct	909 ms	632 KB	Output is correct
9	Correct	1574 ms	984 KB	Output is correct
10	Correct	1603 ms	848 KB	Output is correct
11	Correct	87 ms	376 KB	Output is correct
12	Correct	1032 ms	760 KB	Output is correct
13	Correct	628 ms	504 KB	Output is correct
14	Correct	666 ms	632 KB	Output is correct
15	Correct	2025 ms	788 KB	Output is correct
16	Correct	1305 ms	764 KB	Output is correct
17	Correct	1710 ms	848 KB	Output is correct
18	Correct	1615 ms	904 KB	Output is correct
19	Correct	1614 ms	860 KB	Output is correct
20	Correct	1633 ms	908 KB	Output is correct
21	Correct	1628 ms	820 KB	Output is correct

Subtask #5
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	508 KB	Output is correct
3	Correct	2 ms	504 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	380 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	504 KB	Output is correct
9	Correct	3 ms	504 KB	Output is correct
10	Correct	4 ms	504 KB	Output is correct
11	Correct	4 ms	504 KB	Output is correct
12	Correct	4 ms	504 KB	Output is correct
13	Correct	76 ms	516 KB	Output is correct
14	Correct	34 ms	588 KB	Output is correct
15	Correct	30 ms	504 KB	Output is correct
16	Correct	51 ms	760 KB	Output is correct
17	Correct	43 ms	632 KB	Output is correct
18	Correct	43 ms	604 KB	Output is correct
19	Correct	2277 ms	964 KB	Output is correct
20	Correct	2276 ms	896 KB	Output is correct
21	Correct	1881 ms	836 KB	Output is correct
22	Correct	1582 ms	952 KB	Output is correct
23	Correct	441 ms	576 KB	Output is correct
24	Correct	1407 ms	816 KB	Output is correct
25	Correct	495 ms	760 KB	Output is correct
26	Correct	909 ms	632 KB	Output is correct
27	Correct	1574 ms	984 KB	Output is correct
28	Correct	1603 ms	848 KB	Output is correct
29	Correct	87 ms	376 KB	Output is correct
30	Correct	1032 ms	760 KB	Output is correct
31	Correct	628 ms	504 KB	Output is correct
32	Correct	666 ms	632 KB	Output is correct
33	Correct	2025 ms	788 KB	Output is correct
34	Correct	1305 ms	764 KB	Output is correct
35	Correct	1710 ms	848 KB	Output is correct
36	Correct	1615 ms	904 KB	Output is correct
37	Correct	1614 ms	860 KB	Output is correct
38	Correct	1633 ms	908 KB	Output is correct
39	Correct	1628 ms	820 KB	Output is correct
40	Correct	2614 ms	2360 KB	Output is correct
41	Correct	45 ms	632 KB	Output is correct
42	Correct	1766 ms	2344 KB	Output is correct
43	Correct	1512 ms	2076 KB	Output is correct
44	Correct	1514 ms	1916 KB	Output is correct
45	Correct	2695 ms	8504 KB	Output is correct
46	Correct	52 ms	1656 KB	Output is correct
47	Correct	1937 ms	8564 KB	Output is correct
48	Correct	1576 ms	6928 KB	Output is correct
49	Correct	1578 ms	7440 KB	Output is correct

Submission #126089

Compilation message

Subtask #1 25.0 / 25.0

Subtask #2 20.0 / 20.0

Subtask #3 20.0 / 20.0

Subtask #4 15.0 / 15.0

Subtask #5 20.0 / 20.0

Subtask #1
25.0 / 25.0

Subtask #2
20.0 / 20.0

Subtask #3
20.0 / 20.0

Subtask #4
15.0 / 15.0

Subtask #5
20.0 / 20.0