Submission #815086

#	Time	Username	Problem	Language	Result	Execution time	Memory
815086		waldi	Misspelling (JOI22_misspelling)	C++17	100 / 100	2824 ms	91596 KiB

misspelling

#include<bits/stdc++.h>
#define FOR(i,p,k) for(int i=(p);i<=(k);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define pii pair<int, int>
#define fi first
#define se second
#define mod 1000000007
#define A 26
typedef long long ll;
using namespace std;

struct modular{
	int a;
	modular(int x = 0){a = x;}
	modular operator+(modular t){return {(a+t.a)%mod};}
	modular operator-(modular t){return {(a-t.a+mod)%mod};}
	void operator+=(modular t){a = (a+t.a)%mod;}
};

int main(){
	int n, m;
	scanf("%d%d", &n, &m);
	vector<set<pii>> s(2);
	while(m--){
		int a, b;
		scanf("%d%d", &a, &b);
		if(a < b) s[0].emplace(a, b);
		else s[1].emplace(b, a);
	}
	
	vector<vector<modular>> dp(n+1, vector<modular>(A, 0));
	REP(lit, A) dp[1][lit] = 1;
	FOR(pref, 1, n-1) REP(lit, A){
		modular t = dp[pref][lit];
		
		auto f = [&](int x){
			while(s[x].size()){
				auto it = s[x].lower_bound({pref+1, 0});
				if(it == s[x].begin()) return 0;
				it = prev(it);
				if(it->se > pref) return it->fi;
				s[x].erase(it);
			}
			return 0;
		};
		int dol = f(1);
		int gora = f(0);
		
		REP(nowa, A){
			int ogr = 0;
			if(nowa < lit) ogr = dol;
			if(nowa > lit) ogr = gora;
			dp[pref+1][nowa] += t-dp[ogr][lit];
		}
	}
	modular wyn = 0;
	REP(lit, A) wyn += dp[n][lit];
	printf("%d", wyn.a);
}

Compilation message (stderr)

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

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