Submission #376113

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
376113	2021-03-11T00:18:37 Z	YJU	Lottery (CEOI18_lot)	C++14	100 / 100	1413 ms	12652 KB

#include<bits/stdc++.h>
#pragma GCC optimize("unroll-loops,no-stack-protector,Ofast")
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;
const ll N=1e4+5;
const ll MOD=1e9+7;
const ll INF=(1LL<<61);
const ld pi=acos(-1);
#define REP(i,n) for(int i=0;i<n;++i)
#define REP1(i,n) for(int i=1;i<=n;++i)
#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define lwb lower_bound
#define SZ(_a) (ll)_a.size()

ll n,len,q,x;
ll u[N],ans[N][105],e[N];
vector<ll> query;

void solve(){
	memset(ans,0,sizeof(ans));
    for(int l=1;l+len<=n;l++){
		//matching i with i+l
		ll cnt=0;
		for(int i=0;i<len;i++)if(u[i]==u[i+l])++cnt;
        for(int i=0;i+l+len<=n;i++){
			//k>=len-cnt;
            ll id=lwb(query.begin(),query.end(),len-cnt)-query.begin();
            ++ans[i][id];
            ++ans[i+l][id];
            cnt-=(u[i]==u[i+l]);
            cnt+=(u[i+len]==u[i+l+len]);
        }
    }
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>n>>len;
	REP(i,n)cin>>u[i];
	cin>>q;
	REP(i,q){
		cin>>e[i];
		query.pb(e[i]);
	}
	sort(query.begin(),query.end());
	query.erase(unique(query.begin(),query.end()),query.end());
	solve();
	REP(i,n)REP1(j,q)ans[i][j]+=ans[i][j-1];
    REP(i,q){
        ll id=lwb(query.begin(),query.end(),e[i])-query.begin();
        REP(j,n-len+1)cout<<ans[j][id]<<" \n"[j==n-len];
    }
	return 0;
}
/*
7 1
5 0
5 0
7 0
3 0
4 0
4 3 0
2 1 0


*/

Subtask #1
25.0 / 25.0

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

Subtask #2
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	8556 KB	Output is correct
2	Correct	5 ms	8556 KB	Output is correct
3	Correct	5 ms	8556 KB	Output is correct
4	Correct	5 ms	8556 KB	Output is correct
5	Correct	5 ms	8556 KB	Output is correct
6	Correct	5 ms	8556 KB	Output is correct
7	Correct	5 ms	8556 KB	Output is correct
8	Correct	5 ms	8556 KB	Output is correct
9	Correct	5 ms	8556 KB	Output is correct
10	Correct	7 ms	8556 KB	Output is correct
11	Correct	6 ms	8556 KB	Output is correct
12	Correct	7 ms	8556 KB	Output is correct
13	Correct	27 ms	8684 KB	Output is correct
14	Correct	18 ms	8684 KB	Output is correct
15	Correct	16 ms	8684 KB	Output is correct
16	Correct	26 ms	8684 KB	Output is correct
17	Correct	24 ms	8684 KB	Output is correct
18	Correct	24 ms	8684 KB	Output is correct

Subtask #3
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	546 ms	8684 KB	Output is correct
2	Correct	453 ms	8684 KB	Output is correct
3	Correct	450 ms	8728 KB	Output is correct
4	Correct	422 ms	8812 KB	Output is correct
5	Correct	115 ms	8812 KB	Output is correct
6	Correct	382 ms	8848 KB	Output is correct
7	Correct	97 ms	8812 KB	Output is correct
8	Correct	211 ms	8812 KB	Output is correct
9	Correct	419 ms	8812 KB	Output is correct
10	Correct	425 ms	8940 KB	Output is correct
11	Correct	21 ms	8556 KB	Output is correct
12	Correct	216 ms	8812 KB	Output is correct
13	Correct	158 ms	8812 KB	Output is correct
14	Correct	155 ms	8812 KB	Output is correct

Subtask #4
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	546 ms	8684 KB	Output is correct
2	Correct	453 ms	8684 KB	Output is correct
3	Correct	450 ms	8728 KB	Output is correct
4	Correct	422 ms	8812 KB	Output is correct
5	Correct	115 ms	8812 KB	Output is correct
6	Correct	382 ms	8848 KB	Output is correct
7	Correct	97 ms	8812 KB	Output is correct
8	Correct	211 ms	8812 KB	Output is correct
9	Correct	419 ms	8812 KB	Output is correct
10	Correct	425 ms	8940 KB	Output is correct
11	Correct	21 ms	8556 KB	Output is correct
12	Correct	216 ms	8812 KB	Output is correct
13	Correct	158 ms	8812 KB	Output is correct
14	Correct	155 ms	8812 KB	Output is correct
15	Correct	424 ms	8684 KB	Output is correct
16	Correct	361 ms	8812 KB	Output is correct
17	Correct	444 ms	8812 KB	Output is correct
18	Correct	447 ms	8812 KB	Output is correct
19	Correct	445 ms	8812 KB	Output is correct
20	Correct	444 ms	8812 KB	Output is correct
21	Correct	454 ms	8812 KB	Output is correct

Subtask #5
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	8556 KB	Output is correct
2	Correct	5 ms	8556 KB	Output is correct
3	Correct	5 ms	8556 KB	Output is correct
4	Correct	5 ms	8556 KB	Output is correct
5	Correct	5 ms	8556 KB	Output is correct
6	Correct	5 ms	8556 KB	Output is correct
7	Correct	5 ms	8556 KB	Output is correct
8	Correct	5 ms	8556 KB	Output is correct
9	Correct	5 ms	8556 KB	Output is correct
10	Correct	7 ms	8556 KB	Output is correct
11	Correct	6 ms	8556 KB	Output is correct
12	Correct	7 ms	8556 KB	Output is correct
13	Correct	27 ms	8684 KB	Output is correct
14	Correct	18 ms	8684 KB	Output is correct
15	Correct	16 ms	8684 KB	Output is correct
16	Correct	26 ms	8684 KB	Output is correct
17	Correct	24 ms	8684 KB	Output is correct
18	Correct	24 ms	8684 KB	Output is correct
19	Correct	546 ms	8684 KB	Output is correct
20	Correct	453 ms	8684 KB	Output is correct
21	Correct	450 ms	8728 KB	Output is correct
22	Correct	422 ms	8812 KB	Output is correct
23	Correct	115 ms	8812 KB	Output is correct
24	Correct	382 ms	8848 KB	Output is correct
25	Correct	97 ms	8812 KB	Output is correct
26	Correct	211 ms	8812 KB	Output is correct
27	Correct	419 ms	8812 KB	Output is correct
28	Correct	425 ms	8940 KB	Output is correct
29	Correct	21 ms	8556 KB	Output is correct
30	Correct	216 ms	8812 KB	Output is correct
31	Correct	158 ms	8812 KB	Output is correct
32	Correct	155 ms	8812 KB	Output is correct
33	Correct	424 ms	8684 KB	Output is correct
34	Correct	361 ms	8812 KB	Output is correct
35	Correct	444 ms	8812 KB	Output is correct
36	Correct	447 ms	8812 KB	Output is correct
37	Correct	445 ms	8812 KB	Output is correct
38	Correct	444 ms	8812 KB	Output is correct
39	Correct	454 ms	8812 KB	Output is correct
40	Correct	739 ms	9492 KB	Output is correct
41	Correct	19 ms	8812 KB	Output is correct
42	Correct	589 ms	9504 KB	Output is correct
43	Correct	547 ms	9196 KB	Output is correct
44	Correct	557 ms	9452 KB	Output is correct
45	Correct	1413 ms	12652 KB	Output is correct
46	Correct	28 ms	9068 KB	Output is correct
47	Correct	833 ms	12652 KB	Output is correct
48	Correct	737 ms	10860 KB	Output is correct
49	Correct	734 ms	11496 KB	Output is correct

Submission #376113

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