Submission #1310204

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310204		thuhienne	Misspelling (JOI22_misspelling)	C++20	100 / 100	622 ms	82580 KiB

misspelling

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

using ll = long long;

#define re exit(0);

const int mod = 1e9 + 7;

const int maxn = 500009;

int n,m;
pair <int,int> mark[maxn];

vector <pair <int,int>> event[maxn];

struct ev {
	int val[26];
	ev operator + (const ev & other) {
		ev ret;
		for (int i = 0;i < 26;i++) ret.val[i] = (val[i] + other.val[i]) % mod;
		return ret;
	}
	ev opposite() {
		ev ret;
		for (int i = 0;i < 26;i++) ret.val[i] = (mod - val[i]) % mod;
		return ret;
	}
};

ev total,sum0,sum1;

ev temp;

ev dp[maxn];

priority_queue <int,vector <int>,greater <int>> nothing,type0,type1;

int main() {
//  ios_base::sync_with_stdio(0);cin.tie(nullptr);

	cin >> n >> m;
	for (int i = 1;i <= m;i++) {
		cin >> mark[i].first >> mark[i].second;
		int l = min(mark[i].first,mark[i].second),r = max(mark[i].first,mark[i].second);
		event[l].push_back({r,mark[i].first < mark[i].second});
	}
	
	for (int tt = n;tt >= 1;tt--) {
		
		ev & TMP = dp[tt];
		
		for (int j = 0;j < 26;j++) TMP.val[j] = 1;
		
		for (pair <int,int> e : event[tt]) {
			
			if (e.second == 0) {
				while (nothing.size() && nothing.top() <= e.first) {
					int pos = nothing.top();
					
					total = total + dp[pos].opposite();
					sum0 = sum0 + dp[pos];
					
					nothing.pop();
					type0.push(pos);
				}
				
				while (type1.size() && type1.top() <= e.first) {
					int pos = type1.top();
					
					sum1 = sum1 + dp[pos].opposite();
					
					type1.pop();
				}
			} else {
				while (nothing.size() && nothing.top() <= e.first) {
					int pos = nothing.top();
					
					total = total + dp[pos].opposite();
					sum1 = sum1 + dp[pos];
					
					nothing.pop();
					type1.push(pos);
				}
				
				while (type0.size() && type0.top() <= e.first) {
					int pos = type0.top();
					
					sum0 = sum0 + dp[pos].opposite();
					
					type0.pop();
				}
			}
			
		}
		
		int sum = 0;
		for (int i = 0;i < 26;i++) sum = (sum + total.val[i]) % mod;
		for (int i = 0;i < 26;i++) {
			TMP.val[i] = ((TMP.val[i] + sum - total.val[i]) % mod + mod) % mod;
		}
		
		sum = 0;
		for (int i = 0;i < 26;i++) {
			TMP.val[i] = (TMP.val[i] + sum) % mod;
			sum = (sum + sum0.val[i]) % mod;
		}
		
		sum = 0;
		for (int i = 25;i >= 0;i--) {
			TMP.val[i] = (TMP.val[i] + sum) % mod;
			sum = (sum + sum1.val[i]) % mod;
		}
		
		nothing.push(tt);
		total = total + TMP;
		
		
//		for (int i = 0;i < 26;i++) cout << TMP.val[i] << " ";
//		cout << '\n';
		
	}
	
	int ret = 0;
	for (int i = 0;i < 26;i++) ret = (ret + dp[1].val[i]) % mod;
	
	cout << ret;

}

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