Submission #292914

#	Time	Username	Problem	Language	Result	Execution time	Memory
292914		arnold518	Monochrome Points (JOI20_monochrome)	C++14	35 / 100	2079 ms	12160 KiB

monochrome

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2e5;

int N;
char S[MAXN*2+10];
int A[MAXN+10], B[MAXN+10], L[MAXN*2+10], R[MAXN*2+10];

ll P[MAXN+10], ans, off;

ll tree[MAXN+10];
void init() { memset(tree, 0, sizeof(tree)); }
void update(int i, int k) { for(; i<=N; i+=(i&-i)) tree[i]+=k; }
ll query(int i) { ll ret=0; for(i=R[i]+1; i>0; i-=(i&-i)) ret+=tree[i]; return ret; }
void update2(int l, int r, int k)
{
	//printf("%d %d -> %d %d\n", l, r, R[l]+1, L[r]+1);
	l=R[l]+1; r=L[r]+1;
	if(l<=r) update(l, k), update(r+1, -k);
	else update(l, k), update(r+1, -k), update(1, k);
}

int maxcnt;

struct dequeue
{
	int pt=0;
	vector<pii> V;
	void push_back(pii x) { V.push_back(x); }
	void pop_back() { V.pop_back(); }
	void pop_front() { pt++; }
	pii front() { return V[pt]; }
	bool empty() { return pt==V.size(); }
};

ll f(int j)
{
	j=(j+off)%N;
	if(P[j]!=-1) return P[j];

	int p=0, q=0;
	dequeue DQ;
	ll now=0;
	init();

	for(int i=0; i<N; i++)
	{
		int u=A[i], v=B[(i+j)%N];
		while(!DQ.empty() && DQ.front().second<u)
		{
			update2(DQ.front().second, DQ.front().first, -1);
			update2(DQ.front().first, DQ.front().second, 1);
			DQ.pop_front();
		}
		now+=query(v);
		update2(v, u, 1);
		if(u<v) DQ.push_back({u, v});
	}
	ans=max(ans, now);
	return P[j]=now;
}

int main()
{
	memset(P, -1, sizeof(P));
	scanf("%d", &N);
	scanf(" %s", S+1);

	memset(L, -1, sizeof(L));
	memset(R, -1, sizeof(R));
	int ca=0, cb=0;
	for(int i=1; i<=2*N; i++)
	{
		if(S[i]=='B') A[ca++]=i;
		else B[cb]=i, L[i]=R[i]=cb++;
	}

	R[2*N+1]=0;
	for(int i=2*N; i>=1; i--) if(R[i]==-1) R[i]=R[i+1];

	L[0]=N-1;
	for(int i=1; i<=2*N; i++) if(L[i]==-1) L[i]=L[i-1];

	//for(int i=1; i<=2*N; i++) printf("%d ", L[i]); printf("\n");
	//for(int i=1; i<=2*N; i++) printf("%d ", R[i]); printf("\n");

	off=N-1;
	int lo=0, hi=N-1;	
	while(lo+2<hi)
	{
		int m1=(lo*2+hi)/3, m2=(lo+hi*2)/3;
		if(f(m1)>f(m2)) hi=m2;
		else lo=m1;
	}
	for(int i=lo; i<=hi; i++) f(i);

	printf("%lld\n", ans);
}

Compilation message (stderr)

monochrome.cpp: In member function 'bool dequeue::empty()':
monochrome.cpp:38:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |  bool empty() { return pt==V.size(); }
      |                        ~~^~~~~~~~~~
monochrome.cpp: In function 'll f(int)':
monochrome.cpp:46:6: warning: unused variable 'p' [-Wunused-variable]
   46 |  int p=0, q=0;
      |      ^
monochrome.cpp:46:11: warning: unused variable 'q' [-Wunused-variable]
   46 |  int p=0, q=0;
      |           ^
monochrome.cpp: In function 'int main()':
monochrome.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   71 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
monochrome.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   72 |  scanf(" %s", S+1);
      |  ~~~~~^~~~~~~~~~~~

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