Submission #376114

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
376114	2021-03-11T00:24:54 Z	YJU	Lottery (CEOI18_lot)	C++14	100 / 100	1039 ms	12780 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;
		ll id=0;
        for(int i=0;i+l+len<=n;i++){
            while(id<SZ(query)&&query[id]<len-cnt)++id;
            while(id>0&&query[id-1]>=len-cnt)--id;
            ++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]);
	}
	query.pb(len+1);
	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	6 ms	8556 KB	Output is correct
2	Correct	5 ms	8556 KB	Output is correct
3	Correct	7 ms	8556 KB	Output is correct
4	Correct	5 ms	8556 KB	Output is correct
5	Correct	6 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	6 ms	8576 KB	Output is correct
9	Correct	5 ms	8556 KB	Output is correct
10	Correct	6 ms	8556 KB	Output is correct
11	Correct	7 ms	8576 KB	Output is correct
12	Correct	6 ms	8556 KB	Output is correct

Subtask #2
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	8556 KB	Output is correct
2	Correct	5 ms	8556 KB	Output is correct
3	Correct	7 ms	8556 KB	Output is correct
4	Correct	5 ms	8556 KB	Output is correct
5	Correct	6 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	6 ms	8576 KB	Output is correct
9	Correct	5 ms	8556 KB	Output is correct
10	Correct	6 ms	8556 KB	Output is correct
11	Correct	7 ms	8576 KB	Output is correct
12	Correct	6 ms	8556 KB	Output is correct
13	Correct	21 ms	8684 KB	Output is correct
14	Correct	13 ms	8684 KB	Output is correct
15	Correct	12 ms	8684 KB	Output is correct
16	Correct	18 ms	8736 KB	Output is correct
17	Correct	16 ms	8684 KB	Output is correct
18	Correct	18 ms	8684 KB	Output is correct

Subtask #3
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	518 ms	8684 KB	Output is correct
2	Correct	434 ms	8812 KB	Output is correct
3	Correct	424 ms	8940 KB	Output is correct
4	Correct	409 ms	8684 KB	Output is correct
5	Correct	100 ms	8684 KB	Output is correct
6	Correct	361 ms	8704 KB	Output is correct
7	Correct	129 ms	8684 KB	Output is correct
8	Correct	212 ms	8812 KB	Output is correct
9	Correct	392 ms	8684 KB	Output is correct
10	Correct	403 ms	8684 KB	Output is correct
11	Correct	17 ms	8556 KB	Output is correct
12	Correct	198 ms	8812 KB	Output is correct
13	Correct	127 ms	8812 KB	Output is correct
14	Correct	129 ms	8684 KB	Output is correct

Subtask #4
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	518 ms	8684 KB	Output is correct
2	Correct	434 ms	8812 KB	Output is correct
3	Correct	424 ms	8940 KB	Output is correct
4	Correct	409 ms	8684 KB	Output is correct
5	Correct	100 ms	8684 KB	Output is correct
6	Correct	361 ms	8704 KB	Output is correct
7	Correct	129 ms	8684 KB	Output is correct
8	Correct	212 ms	8812 KB	Output is correct
9	Correct	392 ms	8684 KB	Output is correct
10	Correct	403 ms	8684 KB	Output is correct
11	Correct	17 ms	8556 KB	Output is correct
12	Correct	198 ms	8812 KB	Output is correct
13	Correct	127 ms	8812 KB	Output is correct
14	Correct	129 ms	8684 KB	Output is correct
15	Correct	423 ms	8812 KB	Output is correct
16	Correct	365 ms	8684 KB	Output is correct
17	Correct	419 ms	8812 KB	Output is correct
18	Correct	407 ms	8684 KB	Output is correct
19	Correct	433 ms	8684 KB	Output is correct
20	Correct	403 ms	8704 KB	Output is correct
21	Correct	446 ms	8704 KB	Output is correct

Subtask #5
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	8556 KB	Output is correct
2	Correct	5 ms	8556 KB	Output is correct
3	Correct	7 ms	8556 KB	Output is correct
4	Correct	5 ms	8556 KB	Output is correct
5	Correct	6 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	6 ms	8576 KB	Output is correct
9	Correct	5 ms	8556 KB	Output is correct
10	Correct	6 ms	8556 KB	Output is correct
11	Correct	7 ms	8576 KB	Output is correct
12	Correct	6 ms	8556 KB	Output is correct
13	Correct	21 ms	8684 KB	Output is correct
14	Correct	13 ms	8684 KB	Output is correct
15	Correct	12 ms	8684 KB	Output is correct
16	Correct	18 ms	8736 KB	Output is correct
17	Correct	16 ms	8684 KB	Output is correct
18	Correct	18 ms	8684 KB	Output is correct
19	Correct	518 ms	8684 KB	Output is correct
20	Correct	434 ms	8812 KB	Output is correct
21	Correct	424 ms	8940 KB	Output is correct
22	Correct	409 ms	8684 KB	Output is correct
23	Correct	100 ms	8684 KB	Output is correct
24	Correct	361 ms	8704 KB	Output is correct
25	Correct	129 ms	8684 KB	Output is correct
26	Correct	212 ms	8812 KB	Output is correct
27	Correct	392 ms	8684 KB	Output is correct
28	Correct	403 ms	8684 KB	Output is correct
29	Correct	17 ms	8556 KB	Output is correct
30	Correct	198 ms	8812 KB	Output is correct
31	Correct	127 ms	8812 KB	Output is correct
32	Correct	129 ms	8684 KB	Output is correct
33	Correct	423 ms	8812 KB	Output is correct
34	Correct	365 ms	8684 KB	Output is correct
35	Correct	419 ms	8812 KB	Output is correct
36	Correct	407 ms	8684 KB	Output is correct
37	Correct	433 ms	8684 KB	Output is correct
38	Correct	403 ms	8704 KB	Output is correct
39	Correct	446 ms	8704 KB	Output is correct
40	Correct	628 ms	9472 KB	Output is correct
41	Correct	16 ms	8684 KB	Output is correct
42	Correct	426 ms	9452 KB	Output is correct
43	Correct	406 ms	9068 KB	Output is correct
44	Correct	447 ms	9324 KB	Output is correct
45	Correct	1039 ms	12652 KB	Output is correct
46	Correct	23 ms	8940 KB	Output is correct
47	Correct	514 ms	12780 KB	Output is correct
48	Correct	548 ms	10732 KB	Output is correct
49	Correct	473 ms	11396 KB	Output is correct

Submission #376114

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