Submission #695303

#	Time	Username	Problem	Language	Result	Execution time	Memory
695303		GusterGoose27	Misspelling (JOI22_misspelling)	C++11	100 / 100	1157 ms	398492 KiB

misspelling

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5e5;
const int MOD = 1e9+7;
int n, m;
int add[2][MAXN]; // each interval is either nonintersecting on the right, inter
vector<int> del[2][MAXN]; // each interval is either nonintersecting on the right, inter
int dp[MAXN][26];
int cur_sum[MAXN][26][2]; // node, letter, 0 is sum of smaller things, 1 is sum of bigger things
int presum[MAXN][26][2];
int cur_allow[26];

class stree {
public:
	int lp, rp;
	stree *l = nullptr;
	stree *r = nullptr;
	int c = 0; // c = min(lc, rc)
	int lz = 0;
	stree(int lv, int rv) {
		lp = lv;
		rp = rv;
		if (lp < rp) {
			int mid = (lp+rp)/2;
			l = new stree(lp, mid);
			r = new stree(mid+1, rp);
		}
	}
	void add_to(int v) {
		c += v;
		lz += v;
	}
	void prop() {
		l->add_to(lz);
		r->add_to(lz);
		lz = 0;
	}
	int leftmost() { // leftmost thing which is 0
		if (c) return n;
		if (lp == rp) return lp;
		prop();
		int ql = l->leftmost();
		if (ql < n) return ql;
		return r->leftmost();
	}
	void upd(int lv, int rv, int v = 1) {
		if (lp > rv || rp < lv) return;
		if (lp >= lv && rp <= rv) {
			add_to(v);
			return;
		}
		prop();
		l->upd(lv, rv, v);
		r->upd(lv, rv, v);
	}
};

void make_sums(int i) {
	for (int j = 1; j < 26; j++) {
		cur_sum[i][j][0] = (cur_sum[i][j-1][0]+dp[i][j-1])%MOD;
		presum[i][j][0] = cur_sum[i][j][0];
		if (i) presum[i][j][0] = (presum[i][j][0]+presum[i-1][j][0])%MOD;
		cur_allow[j] = (cur_allow[j]+cur_sum[i][j][0])%MOD;
	}
	for (int j = 24; j >= 0; j--) {
		cur_sum[i][j][1] = (cur_sum[i][j+1][1]+dp[i][j+1])%MOD;
		presum[i][j][1] = cur_sum[i][j][1];
		if (i) presum[i][j][1] = (presum[i][j][1]+presum[i-1][j][1])%MOD;
		cur_allow[j] = (cur_allow[j]+cur_sum[i][j][1])%MOD;
	}
}

stree *trees[2];

void ins(int l, int r, int j) {
	for (int i = 0; i < 26; i++) {
		int amt = presum[r][i][j]-((l == 0) ? 0 : presum[l-1][i][j]);
		amt = (MOD+amt)%MOD;
		cur_allow[i] += amt;
		cur_allow[i] %= MOD;
	}
}

void rem(int l, int r, int j) {
	for (int i = 0; i < 26; i++) {
		int amt = -presum[r][i][j]+((l == 0) ? 0 : presum[l-1][i][j]);
		amt = (MOD+amt)%MOD;
		cur_allow[i] += amt;
		cur_allow[i] %= MOD;
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m;
	fill(add[0], add[0]+n, -1);
	fill(add[1], add[1]+n, -1);
	for (int i = 0; i < m; i++) {
		int x, y; cin >> x >> y;
		x--; y--;
		if (x < y) add[0][x] = max(add[0][x], y);
		else add[1][y] = max(add[1][y], x);
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 2; j++) {
			if (add[j][i] != -1) {
				del[j][add[j][i]].push_back(i);
			}
		}
	}
	int ans = 0;
	trees[0] = new stree(0, n-1);
	trees[1] = new stree(0, n-1);
	for (int i = 0; i < n; i++) {
		if (i == 0) {
			for (int j = 0; j < 26; j++) dp[i][j] = 1;
			ans += 26;
		}
		else {
			for (int j = 0; j < 26; j++) {
				dp[i][j] = cur_allow[j];
				ans += cur_allow[j];
				ans %= MOD;
			}
		}
		make_sums(i);
		for (int j = 0; j < 2; j++) {
			if (add[j][i] >= 0) {
				int l = trees[j]->leftmost();
				if (l <= i) {
					rem(l, i, j);
				}
				trees[j]->upd(0, i);
			}
			for (int v: del[j][i]) {
				trees[j]->upd(0, v, -1);
				int l = trees[j]->leftmost();
				if (l <= v) ins(l, v, j);
			}
		}
	}
	cout << ans << "\n";
}

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