Submission #586855

#	Time	Username	Problem	Language	Result	Execution time	Memory
586855		penguinhacker	Misspelling (JOI22_misspelling)	C++17	100 / 100	1713 ms	222960 KiB

misspelling

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

#define ll long long
#define ar array

const int mxN=5e5, M=1e9+7, INF=69696969;
int n, m, first[mxN][2], dp[mxN][2][26], pbad[mxN+1][2], base[mxN][26];
vector<int> bad[mxN][2];

struct ST {
	int st[1<<20], lz[1<<20];
	void psh(int u, int l, int r) {
		if (lz[u]) {
			st[u]+=lz[u];
			if (l!=r)
				lz[2*u]+=lz[u], lz[2*u+1]+=lz[u];
			lz[u]=0;
		}
	}
	void upd(int ql, int qr, int x, int u=1, int l=0, int r=n-1) {
		psh(u, l, r);
		if (l>qr||r<ql)
			return;
		if (ql<=l&&r<=qr) {
			lz[u]=x;
			psh(u, l, r);
			return;
		}
		int mid=(l+r)/2;
		upd(ql, qr, x, 2*u, l, mid);
		upd(ql, qr, x, 2*u+1, mid+1, r);
		st[u]=min(st[2*u], st[2*u+1]);
	}
	int qry(int u=1, int l=0, int r=n-1) {
		psh(u, l, r);
		if (st[u]>0)
			return -1;
		if (l==r)
			return l;
		int mid=(l+r)/2;
		int ls=qry(2*u, l, mid);
		return ls!=-1?ls:qry(2*u+1, mid+1, r);
	}
} st[2];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	for (int i=0; i<m; ++i) {
		int a, b;
		cin >> a >> b, --a, --b;
		if (a<b) {
			++a;
			bad[a][0].push_back(b);
			st[0].upd(a, b, 1);
			++pbad[a][0], --pbad[b+1][0];
		} else {
			swap(a, b);
			++a;
			bad[a][1].push_back(b);
			st[1].upd(a, b, 1);
			++pbad[a][1], --pbad[b+1][1];
		}
	}
	for (int i=1; i<n; ++i) {
		for (int j : {0, 1})
			pbad[i][j]+=pbad[i-1][j];
		for (int j=0; j<26; ++j)
			base[i][j]=(!pbad[i][0]?j:0)+(!pbad[i][1]?25-j:0);
	}
	memset(first, -1, sizeof(first));
	ll ans=26;
	for (int i=0; i<n; ++i) {
		//ar<ll, 26> cur;
		//cur.fill(1);
		ar<ll, 26> cur;
		for (int j=0; j<26; ++j)
			cur[j]=base[i][j];
		for (int j : {0, 1})
			if (first[i][j]!=-1)
				for (int k=0; k<26; ++k)
					cur[k]=(cur[k]+dp[i][j][k]-dp[first[i][j]][j][k]+M)%M;
		for (int j : {0, 1}) {
			for (int k : bad[i][j])
				st[j].upd(i, k, -1);
			for (int pos=st[j].qry(); pos!=-1; pos=st[j].qry()) {
				st[j].upd(pos, pos, INF);
				first[pos][j]=i;
			}
		}
		//if (i==n-1)
			for (int j=0; j<26; ++j)
				ans=(ans+cur[j])%M;
		int ic=0;
		for (int j=0; j<26; ++j) {
			dp[i+1][0][j]=(dp[i][0][j]+ic)%M;
			ic=(ic+cur[j])%M;
		}
		int dc=0;
		for (int j=25; ~j; --j) {
			dp[i+1][1][j]=(dp[i][1][j]+dc)%M;
			dc=(dc+cur[j])%M;
		}
	}
	cout << ans;
	return 0;
}

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