oj.uz

Submission #897376

# Submission time Handle Problem Language Result Execution time Memory
897376 2024-01-03T02:46:35 Z 8pete8 Lottery (CEOI18_lot) C++17
25 / 100
 226 ms 65536 KB 
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<float.h>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-loops")
using namespace std;
//#define int long long
#define double long double
const int mod=998244353,mxn=1e4,lg=22;//inf=1e18,minf=-1e18,Mxn=100000;
int n,k,q;
int v[mxn+10],ans[mxn+1][mxn+1];
bitset<mxn+10>qry;
vector<int>mp[mxn+10];
map<int,int>pos;
int c=0;
int32_t main(){
    fastio
	cin>>n>>k;
	vector<int>com;
	for(int i=0;i<n;i++)cin>>v[i],com.pb(v[i]);
	sort(all(com));
	unique(all(com));
	for(auto i:com)pos[i]=++c;
	for(int i=0;i<n;i++)v[i]=pos[v[i]];
	int cur=0;
	cin>>q;
	vector<int>qry(q);
	for(int i=0;i<q;i++)cin>>qry[i];
	vector<int>cnt(2*n+1,0);
	for(int i=0;i<n;i++)mp[v[i]].pb(i);
	for(int i=0;i<k;i++)for(auto j:mp[v[i]])cnt[j-i+n]++;
	for(int i=n+1;i<2*n-k+1;i++)ans[cnt[i]][0]++;
	int l=0,r=k-1;
	while(r<n-1){
		for(auto j:mp[v[l]])cnt[j+n]--;
		l++;
		for(int j=2*n;j>=1;j--)cnt[j]=cnt[j-1];
		r++;
		for(auto j:mp[v[r]])cnt[j-(k-1)+n]++;
		for(int i=n;i<2*n-k+1;i++)if(i-n!=l)ans[cnt[i]][l]++;
	}
	for(int i=n;i>=0;i--)for(int j=0;j<n;j++)ans[i][j]+=ans[i+1][j];
	for(auto i:qry){
		for(int j=0;j<n-k+1;j++)cout<<ans[k-i][j]<<" ";
		cout<<'\n';
	}
	return 0;
}

Compilation message

lot.cpp: In function 'int32_t main()':
lot.cpp:53:6: warning: unused variable 'cur' [-Wunused-variable]
   53 |  int cur=0;
      |      ^~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2904 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 1 ms 2908 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 1 ms 2920 KB Output is correct
8 Correct 1 ms 3932 KB Output is correct
9 Correct 1 ms 5724 KB Output is correct
10 Correct 2 ms 3932 KB Output is correct
11 Correct 2 ms 3932 KB Output is correct
12 Correct 2 ms 3932 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2904 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 1 ms 2908 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 1 ms 2920 KB Output is correct
8 Correct 1 ms 3932 KB Output is correct
9 Correct 1 ms 5724 KB Output is correct
10 Correct 2 ms 3932 KB Output is correct
11 Correct 2 ms 3932 KB Output is correct
12 Correct 2 ms 3932 KB Output is correct
13 Correct 18 ms 25948 KB Output is correct
14 Correct 17 ms 25956 KB Output is correct
15 Correct 15 ms 27192 KB Output is correct
16 Correct 22 ms 31700 KB Output is correct
17 Runtime error 19 ms 34592 KB Memory limit exceeded
18 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 226 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 226 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2904 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 1 ms 2908 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 1 ms 2920 KB Output is correct
8 Correct 1 ms 3932 KB Output is correct
9 Correct 1 ms 5724 KB Output is correct
10 Correct 2 ms 3932 KB Output is correct
11 Correct 2 ms 3932 KB Output is correct
12 Correct 2 ms 3932 KB Output is correct
13 Correct 18 ms 25948 KB Output is correct
14 Correct 17 ms 25956 KB Output is correct
15 Correct 15 ms 27192 KB Output is correct
16 Correct 22 ms 31700 KB Output is correct
17 Runtime error 19 ms 34592 KB Memory limit exceeded
18 Halted 0 ms 0 KB -