Submission #549402

#	Time	Username	Problem	Language	Result	Execution time	Memory
549402		keta_tsimakuridze	Misspelling (JOI22_misspelling)	C++14	100 / 100	1223 ms	107200 KiB

misspelling

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define f first
#define s second
#define endl "\n"
const int N = 5e5 + 5, mod = 1e9 + 7; //!
int t, n, dp[N][26];	
multiset<int> s[2];
vector<pii> st[N], en[N];
void add(int &a, int b) {
	if(b < 0) b += mod;
	a += b;
	if(a >= mod) a -= mod;
}
void upd(int i) {
	for(int j = 0; j < st[i].size(); j++) {
		s[st[i][j].f].insert(st[i][j].s);
	}
	for(int j = 0; j < en[i].size(); j++) {
		s[en[i][j].f].erase(s[en[i][j].f].find(en[i][j].s));
	}	
}
main() {
//	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int n, m;
	cin >> n >> m;
	#define pb push_back
	for(int i = 1; i <= m; i++) {
		int l, r;
		cin >> l >> r;
		if(l > r) {
			st[r].pb({0, r});
			en[l].pb({0, r});
		} else {
			st[l].pb({1, l});
			en[r].pb({1, l});			
		}
	}
	for(int j = 0; j < 26; j++) dp[1][j] = 1;

	upd(1);
	for(int i = 2; i <= n; i++) {
		int b = 0, c = 0;
		if(s[0].size()) {
			b = *--s[0].end();
		}	
		if(s[1].size())	{
			c = *--s[1].end();
		}
		vector<int> p(26), sf(26);			
		for(int k = 0; k < 26; k++) {
			if(k) p[k] = p[k - 1];
			add(p[k] , dp[i - 1][k] - dp[b][k]);
		}
		for(int k = 26 - 1; k >= 0; k--) {
			if(k != 25) sf[k] = sf[k + 1];
			add(sf[k], dp[i - 1][k] - dp[c][k]);
		}
		for(int j = 0; j < 26; j++) {
			dp[i][j] = dp[i - 1][j];
			if(j) add(dp[i][j], p[j - 1]);
			if(j != 25) add(dp[i][j], sf[j + 1]);
		}
		upd(i);
	}
	int ans = 0;
	for(int i = 0; i < 26; i++) add(ans , dp[n][i]);
	cout << ans;
}

Compilation message (stderr)

misspelling.cpp: In function 'void upd(int)':
misspelling.cpp:17:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |  for(int j = 0; j < st[i].size(); j++) {
      |                 ~~^~~~~~~~~~~~~~
misspelling.cpp:20:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  for(int j = 0; j < en[i].size(); j++) {
      |                 ~~^~~~~~~~~~~~~~
misspelling.cpp: At global scope:
misspelling.cpp:24:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   24 | main() {
      | ^~~~

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