Submission #292580

#	Time	Username	Problem	Language	Result	Execution time	Memory
292580		model_code	Monochrome Points (JOI20_monochrome)	C++17	100 / 100	42 ms	4840 KiB

monochrome

#include <bits/stdc++.h>
#define SIZE 400005
using namespace std;
typedef pair <int,int> P;
typedef long long int ll;

char str[SIZE];
ll rt[SIZE];
int n;

void add(int l,int r,int k)
{
	if(l>r) return;
	while(l<0) l+=n,r+=n;
	while(1)
	{
		if(l/n!=r/n)
		{
			rt[l%n]+=k;
			rt[n]-=k;
			l=(l/n+1)*n;
		}
		else
		{
			rt[l%n]+=k;
			rt[r%n+1]-=k;
			break;
		}
	}
}
int main()
{
	scanf("%d",&n);
	scanf("%s",&str);
	vector <int> vb,vw;
	for(int i=0;i<2*n;i++)
	{
		if(str[i]=='B') vb.push_back(i);
		else vw.push_back(i);
	}
	for(int i=0;i<n;i++) vw.push_back(vw[i]+2*n);
	int s=0,t=0;
	for(int i=0;i<n;i++)
	{
		while(t<vw.size()&&vw[t]<=vb[i]+n) t++;
		while(s<vw.size()&&vw[s]<vb[i]) s++;
		add(s-i,t-i-1,-vb[i]-1);
		add(t-i,s+n-i-1,2*n+vb[i]-1);
	}
	s=t=0;
	int r=0;
	for(int i=0;i<2*n;i++)
	{
		while(t<vb.size()&&vb[t]<vw[i]) t++;
		while(s<vb.size()&&vb[s]<vw[i]-n) s++;
		while(r<vb.size()&&vb[r]<vw[i]-2*n) r++;
		add(i-t+1,i-s,vw[i]);
		add(i-s+1,i-r,-vw[i]);
	}
	for(int i=1;i<n;i++) rt[i]+=rt[i-1];
	ll ret=0;
	for(int i=0;i<n;i++) ret=max(ret,rt[i]);
	printf("%lld\n",ret/2);
}

Compilation message (stderr)

monochrome.cpp: In function 'int main()':
monochrome.cpp:34:10: warning: format '%s' expects argument of type 'char*', but argument 2 has type 'char (*)[400005]' [-Wformat=]
   34 |  scanf("%s",&str);
      |         ~^  ~~~~
      |          |  |
      |          |  char (*)[400005]
      |          char*
monochrome.cpp:45:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |   while(t<vw.size()&&vw[t]<=vb[i]+n) t++;
      |         ~^~~~~~~~~~
monochrome.cpp:46:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |   while(s<vw.size()&&vw[s]<vb[i]) s++;
      |         ~^~~~~~~~~~
monochrome.cpp:54:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |   while(t<vb.size()&&vb[t]<vw[i]) t++;
      |         ~^~~~~~~~~~
monochrome.cpp:55:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |   while(s<vb.size()&&vb[s]<vw[i]-n) s++;
      |         ~^~~~~~~~~~
monochrome.cpp:56:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   while(r<vb.size()&&vb[r]<vw[i]-2*n) r++;
      |         ~^~~~~~~~~~
monochrome.cpp:33:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   33 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
monochrome.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |  scanf("%s",&str);
      |  ~~~~~^~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 21 / 21
• Subtask 3: 10 / 10
• Subtask 4: 65 / 65