Submission #684345

#	Time	Username	Problem	Language	Result	Execution time	Memory
684345		arnold518	Misspelling (JOI22_misspelling)	C++17	100 / 100	652 ms	249812 KiB

misspelling

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

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

const int MAXN = 5e5;
const ll MOD = 1e9+7;

int N, M;
vector<pii> A, B;
int PA[MAXN+10], PB[MAXN+10];

struct priority_set
{
	priority_queue<int> PQ1, PQ2;
	void push(int x) { PQ1.push(x); }
	void pop(int x) { PQ2.push(x); }
	bool empty()
	{
		while(!PQ1.empty() && !PQ2.empty() && PQ1.top()==PQ2.top()) PQ1.pop(), PQ2.pop();
		return PQ1.empty();
	}
	int top()
	{
		if(empty()) return 0;
		return PQ1.top();
	}
};

ll dp[30];
ll dp1[MAXN+10][30], dp2[MAXN+10][30];

int main()
{
	scanf("%d%d", &N, &M);
	for(int i=1; i<=M; i++)
	{
		int p, q;
		scanf("%d%d", &p, &q);
		if(p<q) A.push_back({p, q-1});
		else B.push_back({q, p-1});
	}

	{
		priority_set PS;
		vector<pii> V;
		for(int i=0; i<A.size(); i++)
		{
			V.push_back({A[i].first, i+1});
			V.push_back({A[i].second+1, -i-1});
		}
		sort(V.begin(), V.end());

		for(int i=1, j=0; i<N; i++)
		{
			for(; j<V.size() && V[j].first==i; j++)
			{
				if(V[j].second>0) PS.push(A[V[j].second-1].first);
				else PS.pop(A[-V[j].second-1].first); 
			}
			PA[i]=PS.top();
		}
	}
	{
		priority_set PS;
		vector<pii> V;
		for(int i=0; i<B.size(); i++)
		{
			V.push_back({B[i].first, i+1});
			V.push_back({B[i].second+1, -i-1});
		}
		sort(V.begin(), V.end());

		for(int i=1, j=0; i<N; i++)
		{
			for(; j<V.size() && V[j].first==i; j++)
			{
				if(V[j].second>0) PS.push(B[V[j].second-1].first);
				else PS.pop(B[-V[j].second-1].first); 
			}
			PB[i]=PS.top();
		}
	}

	for(int j=1; j<=26; j++)
	{
		dp1[0][j]=j;
		dp2[0][26-j+1]=j;
	}
	for(int i=1; i<N; i++)
	{
		for(int j=1; j<=26; j++)
		{
			dp[j]=0;
			if(PA[i]<PB[i])
			{
				int l, r;
				l=PB[i], r=i-1;
				if(l<=r)
				{
					if(l>=1) dp[j]+=(dp1[r][j-1]-dp1[l-1][j-1])+(dp2[r][j+1]-dp2[l-1][j+1]);
					else dp[j]+=dp1[r][j-1]+dp2[r][j+1];
					dp[j]%=MOD;
					if(dp[j]<0) dp[j]+=MOD;
				}
				l=PA[i], r=PB[i]-1;
				if(l<=r)
				{
					if(l>=1) dp[j]+=(dp1[r][j-1]-dp1[l-1][j-1]);
					else dp[j]+=dp1[r][j-1];
					dp[j]%=MOD;
					if(dp[j]<0) dp[j]+=MOD;
				}
			}
			else
			{
				int l, r;
				l=PA[i], r=i-1;
				if(l<=r)
				{
					if(l>=1) dp[j]+=(dp1[r][j-1]-dp1[l-1][j-1])+(dp2[r][j+1]-dp2[l-1][j+1]);
					else dp[j]+=dp1[r][j-1]+dp2[r][j+1];
					dp[j]%=MOD;
					if(dp[j]<0) dp[j]+=MOD;
				}
				l=PB[i], r=PA[i]-1;
				if(l<=r)
				{
					if(l>=1) dp[j]+=(dp2[r][j+1]-dp2[l-1][j+1]);
					else dp[j]+=dp2[r][j+1];
					dp[j]%=MOD;
					if(dp[j]<0) dp[j]+=MOD;
				}
			}
		}

		for(int j=1; j<=26; j++) dp1[i][j]=(dp1[i][j-1]+dp[j])%MOD;
		for(int j=26; j>=1; j--) dp2[i][j]=(dp2[i][j+1]+dp[j])%MOD;
		for(int j=1; j<=26; j++)
		{
			dp1[i][j]=(dp1[i-1][j]+dp1[i][j])%MOD;
			dp2[i][j]=(dp2[i-1][j]+dp2[i][j])%MOD;
		}
	}
	printf("%lld\n", dp1[N-1][26]);
}

Compilation message (stderr)

misspelling.cpp: In function 'int main()':
misspelling.cpp:49:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |   for(int i=0; i<A.size(); i++)
      |                ~^~~~~~~~~
misspelling.cpp:58:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |    for(; j<V.size() && V[j].first==i; j++)
      |          ~^~~~~~~~~
misspelling.cpp:69:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |   for(int i=0; i<B.size(); i++)
      |                ~^~~~~~~~~
misspelling.cpp:78:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |    for(; j<V.size() && V[j].first==i; j++)
      |          ~^~~~~~~~~
misspelling.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
misspelling.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |   scanf("%d%d", &p, &q);
      |   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 20 / 20
• Subtask 3: 29 / 29
• Subtask 4: 32 / 32
• Subtask 5: 11 / 11