oj.uz

Submission #573786

# Submission time Handle Problem Language Result Execution time Memory
573786 2022-06-07T07:59:19 Z InternetPerson10 Sightseeing in Kyoto (JOI22_kyoto) C++17
0 / 100
 1 ms 468 KB 
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

const int MOD = 1e9 + 7;

struct s {
    int ans[26];
    s() {
        for(int i = 0; i < 26; i++) ans[i] = 0;
    }
};

struct pairhash {
    size_t operator()(pair<int, int> const& p) const noexcept {
        return (p.first ^ p.second ^ (p.first + p.second));
    }
};

vector<vector<pair<int, int>>> ops;
unordered_map<pair<int, int>, s, pairhash> ma, ma2;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m; 
    cin >> n >> m;
    pair<int, int> pee = {-1, -1};
    for(int i = 0; i < 26; i++) {
        ma[pee].ans[i] = 1;
    }
    ops.resize(n);
    for(int z = 0; z < m; z++) {
        int x, y;
        cin >> x >> y;
        if(x < y) {
            ops[x].push_back({y, 1});
        }
        else {
            ops[y].push_back({x, -1});
        }
    }
    for(int i = 1; i < n; i++) {
        for(auto pa : ma) {
            s ss;
            pair<int, int> p;
            tie(p, ss) = pa;
            for(auto pp : ops[i]) {
                if(pp.second == -1) {
                    p.first = max(p.first, pp.first);
                }
                else {
                    p.second = max(p.second, pp.first);
                }
            }
            if(p.first == i) p.first = -1;
            if(p.second == i) p.second = -1;
            if(p.first == -1) {
                int sum = 0;
                for(int i = 25; i >= 0; i--) {
                    sum += ss.ans[i];
                    sum %= MOD;
                    if(i) ma2[pee].ans[i-1] += sum;
                    if(i) ma2[pee].ans[i-1] %= MOD;
                }
            }
            if(p.second == -1) {
                int sum = 0;
                for(int i = 0; i < 26; i++) {
                    sum += ss.ans[i];
                    sum %= MOD;
                    if(i != 25) ma2[pee].ans[i+1] += sum;
                    if(i != 25) ma2[pee].ans[i+1] %= MOD;
                }
            }
            for(int i = 0; i < 26; i++) {
                ma2[p].ans[i] += ss.ans[i];
                ma2[p].ans[i] %= MOD;
            }
        }
        unordered_map<pair<int, int>, s, pairhash>().swap(ma);
        swap(ma, ma2);
    }
    int sum = 0;
    for(auto p : ma) {
        for(int i = 0; i < 26; i++) {
            sum += p.second.ans[i];
            sum %= MOD;
        }
    }
    cout << sum << '\n';
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 30.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 452 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -