Submission #309688

#	Time	Username	Problem	Language	Result	Execution time	Memory
309688		lukameladze	Lottery (CEOI18_lot)	C++14	100 / 100	982 ms	20856 KiB

lot

# include <bits/stdc++.h>
using namespace std;
long long n,l,k,a[300005],ans1[300005][105],cnt[300005],pr[300005],ans[300005][105],q,j,a1[300005],xx;
pair <int, int> b[300005];
int main()
{
     cin>>n>>l;
     for (int i=1; i<=n; i++)
     {
          cin>>a[i];
     }
     cin>>q;
     for (int i=1; i<=q; i++)
     {
     	cin>>b[i].first;
     	b[i].first=l-b[i].first;
     	b[i].second=i;
	}
	sort(b+1, b+q+1);
	j=1;
	for (int i=0; i<=l; i++)
	{
	     //if (i==0) cout<<j<<endl;
		while (b[j].first<=i && j<=q)
		{
			j++;
		}
		a1[i]=j-1; 
	}
//	cout<<a1[0]<<" "<<a1[1]<<" "<<a1[2]<<endl;
     for (int d=1; d<=n-1; d++)
     {
          for (int j=1; j<=n-d; j++)
          {
               if(a[j]==a[j+d]) cnt[j]++;
          }
          for (int j=1; j<=n-d; j++)
          {
               pr[j]=pr[j-1]+cnt[j];
               cnt[j]=0;
          }
          for (int j=l; j<=n-d; j++)
          {
               
               xx=pr[j]-pr[j-l];
        
    //   cout<<d<<" "<<j<<" "<<j-l<<" "<<xx<<" "<<a1[xx]<<endl;
      // cout<<j-l+1<<" "<<j-l+1+d<<" "<<a1[xx]<<endl;
               ans[j-l+1][a1[xx]]++; 
               ans[j-l+1+d][a1[xx]]++;
          }
     }
     // 0,1
  /*   for (int i=1; i<=q; i++)
     {
          for (int j=1; j<=n-l+1; j++)
          {
               cout<<ans[j][i]<<" ";
          }
          cout<<endl;
     }*/
     for (int i=q; i>=1; i--)
     {
          for (int j=1; j<=n-l+1; j++)
          {
               if(i==1)
               {
//      //              cout<<j<<" "<<b[i].second<<" "<<ans[j][b[i].second]<<" "<<ans[j][b[i+1].second]<<endl;
               }
               ans1[j][b[i].second]=ans1[j][b[i+1].second]+ans[j][i];
          }
     }
     for (int i=1; i<=q; i++)
     {
          for (int j=1; j<=n-l+1; j++)
          {
               cout<<ans1[j][i]<<" ";
          }
          cout<<endl;
     }
     cout<<endl;
 }

• Subtask 1: 25 / 25
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20