oj.uz

Submission #586855

# Submission time Handle Problem Language Result Execution time Memory
586855 2022-06-30T19:08:54 Z penguinhacker Misspelling (JOI22_misspelling) C++17
100 / 100
 1713 ms 222960 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27748 KB Output is correct
2 Correct 14 ms 27660 KB Output is correct
3 Correct 16 ms 27756 KB Output is correct
4 Correct 14 ms 27732 KB Output is correct
5 Correct 14 ms 27732 KB Output is correct
6 Correct 13 ms 27732 KB Output is correct
7 Correct 14 ms 27764 KB Output is correct
8 Correct 14 ms 27748 KB Output is correct
9 Correct 17 ms 27732 KB Output is correct
10 Correct 16 ms 27740 KB Output is correct
11 Correct 14 ms 27732 KB Output is correct
12 Correct 14 ms 27732 KB Output is correct
13 Correct 14 ms 27728 KB Output is correct
14 Correct 15 ms 27732 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27748 KB Output is correct
2 Correct 14 ms 27660 KB Output is correct
3 Correct 16 ms 27756 KB Output is correct
4 Correct 14 ms 27732 KB Output is correct
5 Correct 14 ms 27732 KB Output is correct
6 Correct 13 ms 27732 KB Output is correct
7 Correct 14 ms 27764 KB Output is correct
8 Correct 14 ms 27748 KB Output is correct
9 Correct 17 ms 27732 KB Output is correct
10 Correct 16 ms 27740 KB Output is correct
11 Correct 14 ms 27732 KB Output is correct
12 Correct 14 ms 27732 KB Output is correct
13 Correct 14 ms 27728 KB Output is correct
14 Correct 15 ms 27732 KB Output is correct
15 Correct 16 ms 27760 KB Output is correct
16 Correct 15 ms 27744 KB Output is correct
17 Correct 15 ms 27732 KB Output is correct
18 Correct 15 ms 27840 KB Output is correct
19 Correct 15 ms 27836 KB Output is correct
20 Correct 14 ms 27776 KB Output is correct
21 Correct 15 ms 27752 KB Output is correct
22 Correct 23 ms 27952 KB Output is correct
23 Correct 15 ms 27732 KB Output is correct
24 Correct 14 ms 27772 KB Output is correct
25 Correct 15 ms 27800 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27732 KB Output is correct
2 Correct 14 ms 27716 KB Output is correct
3 Correct 14 ms 27732 KB Output is correct
4 Correct 13 ms 27732 KB Output is correct
5 Correct 911 ms 222784 KB Output is correct
6 Correct 899 ms 222872 KB Output is correct
7 Correct 904 ms 222840 KB Output is correct
8 Correct 902 ms 222796 KB Output is correct
9 Correct 911 ms 222796 KB Output is correct
10 Correct 47 ms 35804 KB Output is correct
11 Correct 15 ms 27732 KB Output is correct
12 Correct 14 ms 27780 KB Output is correct
13 Correct 1650 ms 222960 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27748 KB Output is correct
2 Correct 14 ms 27660 KB Output is correct
3 Correct 16 ms 27756 KB Output is correct
4 Correct 14 ms 27732 KB Output is correct
5 Correct 14 ms 27732 KB Output is correct
6 Correct 13 ms 27732 KB Output is correct
7 Correct 14 ms 27764 KB Output is correct
8 Correct 14 ms 27748 KB Output is correct
9 Correct 17 ms 27732 KB Output is correct
10 Correct 16 ms 27740 KB Output is correct
11 Correct 14 ms 27732 KB Output is correct
12 Correct 14 ms 27732 KB Output is correct
13 Correct 14 ms 27728 KB Output is correct
14 Correct 15 ms 27732 KB Output is correct
15 Correct 16 ms 27760 KB Output is correct
16 Correct 15 ms 27744 KB Output is correct
17 Correct 15 ms 27732 KB Output is correct
18 Correct 15 ms 27840 KB Output is correct
19 Correct 15 ms 27836 KB Output is correct
20 Correct 14 ms 27776 KB Output is correct
21 Correct 15 ms 27752 KB Output is correct
22 Correct 23 ms 27952 KB Output is correct
23 Correct 15 ms 27732 KB Output is correct
24 Correct 14 ms 27772 KB Output is correct
25 Correct 15 ms 27800 KB Output is correct
26 Correct 46 ms 35792 KB Output is correct
27 Correct 47 ms 35336 KB Output is correct
28 Correct 51 ms 35352 KB Output is correct
29 Correct 58 ms 35852 KB Output is correct
30 Correct 59 ms 35780 KB Output is correct
31 Correct 541 ms 43928 KB Output is correct
32 Correct 45 ms 35788 KB Output is correct
33 Correct 46 ms 35852 KB Output is correct
34 Correct 62 ms 35628 KB Output is correct
35 Correct 595 ms 44324 KB Output is correct
36 Correct 36 ms 34892 KB Output is correct
37 Correct 58 ms 35580 KB Output is correct
38 Correct 47 ms 35372 KB Output is correct
39 Correct 44 ms 35192 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 27748 KB Output is correct
2 Correct 14 ms 27660 KB Output is correct
3 Correct 16 ms 27756 KB Output is correct
4 Correct 14 ms 27732 KB Output is correct
5 Correct 14 ms 27732 KB Output is correct
6 Correct 13 ms 27732 KB Output is correct
7 Correct 14 ms 27764 KB Output is correct
8 Correct 14 ms 27748 KB Output is correct
9 Correct 17 ms 27732 KB Output is correct
10 Correct 16 ms 27740 KB Output is correct
11 Correct 14 ms 27732 KB Output is correct
12 Correct 14 ms 27732 KB Output is correct
13 Correct 14 ms 27728 KB Output is correct
14 Correct 15 ms 27732 KB Output is correct
15 Correct 16 ms 27760 KB Output is correct
16 Correct 15 ms 27744 KB Output is correct
17 Correct 15 ms 27732 KB Output is correct
18 Correct 15 ms 27840 KB Output is correct
19 Correct 15 ms 27836 KB Output is correct
20 Correct 14 ms 27776 KB Output is correct
21 Correct 15 ms 27752 KB Output is correct
22 Correct 23 ms 27952 KB Output is correct
23 Correct 15 ms 27732 KB Output is correct
24 Correct 14 ms 27772 KB Output is correct
25 Correct 15 ms 27800 KB Output is correct
26 Correct 14 ms 27732 KB Output is correct
27 Correct 14 ms 27716 KB Output is correct
28 Correct 14 ms 27732 KB Output is correct
29 Correct 13 ms 27732 KB Output is correct
30 Correct 911 ms 222784 KB Output is correct
31 Correct 899 ms 222872 KB Output is correct
32 Correct 904 ms 222840 KB Output is correct
33 Correct 902 ms 222796 KB Output is correct
34 Correct 911 ms 222796 KB Output is correct
35 Correct 47 ms 35804 KB Output is correct
36 Correct 15 ms 27732 KB Output is correct
37 Correct 14 ms 27780 KB Output is correct
38 Correct 1650 ms 222960 KB Output is correct
39 Correct 46 ms 35792 KB Output is correct
40 Correct 47 ms 35336 KB Output is correct
41 Correct 51 ms 35352 KB Output is correct
42 Correct 58 ms 35852 KB Output is correct
43 Correct 59 ms 35780 KB Output is correct
44 Correct 541 ms 43928 KB Output is correct
45 Correct 45 ms 35788 KB Output is correct
46 Correct 46 ms 35852 KB Output is correct
47 Correct 62 ms 35628 KB Output is correct
48 Correct 595 ms 44324 KB Output is correct
49 Correct 36 ms 34892 KB Output is correct
50 Correct 58 ms 35580 KB Output is correct
51 Correct 47 ms 35372 KB Output is correct
52 Correct 44 ms 35192 KB Output is correct
53 Correct 1008 ms 211780 KB Output is correct
54 Correct 975 ms 210892 KB Output is correct
55 Correct 1497 ms 221228 KB Output is correct
56 Correct 1498 ms 221260 KB Output is correct
57 Correct 904 ms 222620 KB Output is correct
58 Correct 900 ms 222880 KB Output is correct
59 Correct 907 ms 222924 KB Output is correct
60 Correct 1713 ms 218820 KB Output is correct
61 Correct 601 ms 198736 KB Output is correct
62 Correct 1479 ms 215092 KB Output is correct
63 Correct 1222 ms 210664 KB Output is correct
64 Correct 930 ms 206016 KB Output is correct