QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#537703#3503. MisspellingMax_s_xaM#8 75ms89176kbC++174.0kb2024-08-30 17:34:282024-08-30 17:34:29

Judging History

你现在查看的是最新测评结果

  • [2024-08-30 17:34:29]
  • 评测
  • 测评结果:8
  • 用时:75ms
  • 内存:89176kb
  • [2024-08-30 17:34:28]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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%