QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#537703 | #3503. Misspelling | Max_s_xaM# | 8 | 75ms | 89176kb | C++17 | 4.0kb | 2024-08-30 17:34:28 | 2024-08-30 17:34:29 |
Judging History
answer
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
typedef long long ll;
typedef double lf;
// #define DEBUG 1
struct IO
{
#define MAXSIZE (1 << 20)
#define isdigit(x) (x >= '0' && x <= '9')
char buf[MAXSIZE], *p1, *p2;
char pbuf[MAXSIZE], *pp;
#if DEBUG
#else
IO() : p1(buf), p2(buf), pp(pbuf) {}
~IO() {fwrite(pbuf, 1, pp - pbuf, stdout);}
#endif
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) ? ' ' : *p1++)
#define blank(x) (x == ' ' || x == '\n' || x == '\r' || x == '\t')
template <typename T>
void Read(T &x)
{
#if DEBUG
std::cin >> x;
#else
bool sign = 0; char ch = gc(); x = 0;
for (; !isdigit(ch); ch = gc())
if (ch == '-') sign = 1;
for (; isdigit(ch); ch = gc()) x = x * 10 + (ch ^ 48);
if (sign) x = -x;
#endif
}
void Read(char *s)
{
#if DEBUG
std::cin >> s;
#else
char ch = gc();
for (; blank(ch); ch = gc());
for (; !blank(ch); ch = gc()) *s++ = ch;
*s = 0;
#endif
}
void Read(char &c) {for (c = gc(); blank(c); c = gc());}
void Push(const char &c)
{
#if DEBUG
putchar(c);
#else
if (pp - pbuf == MAXSIZE) fwrite(pbuf, 1, MAXSIZE, stdout), pp = pbuf;
*pp++ = c;
#endif
}
template <typename T>
void Write(T x)
{
if (x < 0) x = -x, Push('-');
static T sta[35];
int top = 0;
do sta[top++] = x % 10, x /= 10; while (x);
while (top) Push(sta[--top] ^ 48);
}
template <typename T>
void Write(T x, char lst) {Write(x), Push(lst);}
} IO;
#define Read(x) IO.Read(x)
#define Write(x, y) IO.Write(x, y)
#define Put(x) IO.Push(x)
using namespace std;
const int MAXN = 5e5 + 10, mod = 1e9 + 7;
inline ll Qpow(ll x, ll y) { ll res = 1; while (y) (y & 1) && (res = res * x % mod), x = x * x % mod, y >>= 1; return res; }
inline void add(int &x, int y) { (x += y) >= mod && (x -= mod); }
inline int adu(int x, int y) { return (x += y) >= mod ? x - mod : x; }
inline int sbu(int x, int y) { return (x -= y) < 0 ? x + mod : x; }
int n, m;
struct inter
{
int l, r; bool tp;
}a[MAXN];
vector <int> vec[MAXN];
set <pair <int, int>, greater <pair <int, int>>> st[2];
int f[26], g[26][MAXN];
int main()
{
#if DEBUG
#else
ios::sync_with_stdio(0), cin.tie(0);
#endif
Read(n), Read(m);
for (int i = 1, x, y; i <= m; i++)
{
Read(x), Read(y);
if (x < y) a[i] = {x, y, 1};
else a[i] = {y, x, 0};
}
for (int i = 1; i <= m; i++) vec[a[i].l].emplace_back(i), vec[a[i].r].emplace_back(-i);
for (int i = 0; i < 26; i++) g[i][0] = 1;
for (int i = 1; i <= n; i++)
{
for (auto x : vec[i])
{
if (x > 0) st[a[x].tp].emplace(a[x].l, x);
else st[a[-x].tp].erase(make_pair(a[-x].l, -x));
}
for (int j = 0; j < 26; j++) f[j] = 0;
int p0 = (st[0].size() ? st[0].begin() -> first : 0), p1 = (st[1].size() ? st[1].begin() -> first : 0);
int pos = max(p0, p1);
if (pos < i)
{
int sum = 0;
for (int j = 0; j < 26; j++) f[j] = g[j][i - 1] - (pos ? g[j][pos - 1] : 0), add(sum, f[j]);
for (int j = 0; j < 26; j++) f[j] = sbu(sum, f[j]);
}
if (p0 < p1)
{
int sum = 0;
for (int j = 25; ~j; j--) add(f[j], sum), add(sum, g[j][p1 - 1] - (p0 ? g[j][p0 - 1] : 0));
}
else if (p1 < p0)
{
int sum = 0;
for (int j = 0; j < 26; j++) add(f[j], sum), add(sum, g[j][p0 - 1] - (p0 ? g[j][p1 - 1] : 0));
}
for (int j = 0; j < 26; j++) g[j][i] = adu(g[j][i - 1], f[j]);
}
int sum = 0;
for (int j = 0; j < 26; j++) add(sum, f[j]);
cout << (ll)sum * Qpow(25, mod - 2) % mod << '\n';
return 0;
}
详细
Subtask #1:
score: 8
Accepted
Test #1:
score: 8
Accepted
time: 4ms
memory: 69372kb
input:
10 9 3 4 4 2 6 2 7 6 7 8 8 5 5 10 10 9 9 1
output:
344750796
result:
ok single line: '344750796'
Test #2:
score: 8
Accepted
time: 0ms
memory: 69144kb
input:
10 9 3 7 7 4 4 9 6 9 8 6 8 5 5 10 10 1 1 2
output:
1506401
result:
ok single line: '1506401'
Test #3:
score: 8
Accepted
time: 0ms
memory: 67044kb
input:
10 10 2 8 1 5 9 3 3 9 2 9 7 10 7 3 7 8 4 1 5 6
output:
351
result:
ok single line: '351'
Test #4:
score: 8
Accepted
time: 0ms
memory: 67252kb
input:
10 90 5 2 4 2 3 6 1 10 7 1 10 9 1 7 2 3 10 3 7 6 8 5 5 3 9 1 6 3 8 1 3 5 6 2 5 1 2 10 2 8 8 7 3 4 6 7 3 10 4 8 7 3 1 8 2 9 9 2 3 2 9 6 2 1 1 9 1 5 8 3 4 5 8 10 4 3 9 8 2 6 10 2 3 7 4 9 8 9 7 5 5 7 10 5 9 4 1 4 10 7 9 10 9 7 6 10 7 9 2 4 5 9 2 7 1 3 3 9 6 9 2 5 6 1 9 3 7 10 5 10 8 4 8 6 3 8 8 2 3 1 5...
output:
26
result:
ok single line: '26'
Test #5:
score: 8
Accepted
time: 4ms
memory: 67104kb
input:
10 1 4 2
output:
960864167
result:
ok single line: '960864167'
Test #6:
score: 8
Accepted
time: 0ms
memory: 67244kb
input:
10 5 6 3 9 4 4 10 9 5 9 2
output:
1682226
result:
ok single line: '1682226'
Test #7:
score: 8
Accepted
time: 4ms
memory: 67028kb
input:
2 1 1 2
output:
351
result:
ok single line: '351'
Test #8:
score: 8
Accepted
time: 0ms
memory: 69372kb
input:
2 2 2 1 1 2
output:
26
result:
ok single line: '26'
Subtask #2:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #9:
score: 0
Wrong Answer
time: 0ms
memory: 67288kb
input:
200 100 1 30 10 179 12 115 15 117 17 161 19 84 22 146 23 46 27 188 29 108 37 69 39 48 41 55 44 158 47 63 50 71 51 91 54 107 55 148 56 61 58 71 61 186 62 92 63 168 65 158 66 145 67 90 71 95 73 125 76 101 79 196 80 104 82 153 84 98 85 111 86 143 88 107 90 177 91 111 92 99 93 177 94 123 95 113 96 128 9...
output:
706132196
result:
wrong answer 1st lines differ - expected: '141223392', found: '706132196'
Subtask #3:
score: 0
Wrong Answer
Test #19:
score: 0
Wrong Answer
time: 75ms
memory: 89176kb
input:
500000 499999 5 6 6 7 7 11 11 15 15 18 18 20 20 21 21 22 22 23 23 27 27 28 28 29 29 30 30 32 32 33 33 35 35 36 36 37 37 43 43 44 44 46 46 47 47 48 48 49 49 51 51 52 52 53 53 54 54 58 58 61 61 63 63 64 64 65 65 66 66 69 69 70 70 76 76 77 77 78 78 80 80 81 81 83 83 87 87 88 88 90 90 92 92 93 93 96 96 ...
output:
-536549268
result:
wrong answer 1st lines differ - expected: '19934265', found: '-536549268'
Subtask #4:
score: 0
Skipped
Dependency #2:
0%
Subtask #5:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%