Submission #567675

#	Time	Username	Problem	Language	Result	Execution time	Memory
567675		jamezzz	Misspelling (JOI22_misspelling)	C++17	100 / 100	1077 ms	105996 KiB

misspelling

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

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));

#define mod 1000000007

inline int add(int a,int b){
	int r=a+b;
	while(r>=mod)r-=mod;
	while(r<0)r+=mod;
	return r;
}

inline int mult(int a,int b){
	return (int)(((ll)(a*b))%mod);
}

inline int rd(){
	int x=0;
	char ch=getchar_unlocked();
	while(!(ch&16))ch=getchar();//keep reading while current character is whitespace
    while(ch&16){//this will break when ‘\n’ or ‘ ‘ is encountered
		x=(x<<3)+(x<<1)+(ch&15);
		ch=getchar_unlocked();
	}
	return x;
}

#define maxn 500005

int n,m,a,b,far_up[maxn],far_down[maxn];
int tot[maxn],dp[maxn][26];
set<int> t_up,t_down;

int main(){
	sf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)far_up[i]=far_down[i]=i;
	for(int i=0;i<m;++i){
		sf("%d%d",&a,&b);
		if(a<b)mxto(far_down[a],b);//[a,far_down[a]] cannot go up
		else mxto(far_up[b],a);//[b,far_up[b]] cannot go down
	}
	
	for(int i=1;i<=n+1;++i){
		t_up.insert(i);//possible transitions up
		t_down.insert(i);//possible transitions down
	}
	
	for(int i=0;i<26;++i)tot[i]=1;
	
	for(int i=n;i>=1;--i){
		while(*t_up.lower_bound(i+1)<=far_down[i]){//illegal transition
			int x=*t_up.lower_bound(i+1);
			t_up.erase(x);
			int pfx=0;
			for(int j=25;j>=0;--j){
				tot[j]=add(tot[j],-pfx);
				pfx=add(pfx,dp[x][j]);
			}
		}
		while(*t_down.lower_bound(i+1)<=far_up[i]){//illegal transition
			int x=*t_down.lower_bound(i+1);
			t_down.erase(x);
			int pfx=0;
			for(int j=0;j<26;++j){
				tot[j]=add(tot[j],-pfx);
				pfx=add(pfx,dp[x][j]);
			}
		}
		int sm=0;
		for(int j=0;j<26;++j){
			dp[i][j]=tot[j];
			sm=add(sm,dp[i][j]);
		}
		for(int j=0;j<26;++j){
			tot[j]=add(tot[j],add(sm,-dp[i][j]));
		}
	}
	
	int ans=0;
	for(int j=0;j<26;++j){
		ans=add(ans,dp[1][j]);
	}
	pf("%d\n",ans);
}

Compilation message (stderr)

misspelling.cpp: In function 'int main()':
misspelling.cpp:64:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |  sf("%d%d",&n,&m);
      |    ^
misspelling.cpp:67:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |   sf("%d%d",&a,&b);
      |     ^

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