Submission #61917
Source Code Expand
#include <iostream> #include <vector> #include <map> #include <algorithm> using namespace std; typedef pair<int, int> Pair; const int kMod = 1000000007; struct Train { int s, t; bool operator<(const Train& other) const { if (s != other.s) return s < other.s; return t < other.t; } }; int main() { ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; vector<Train> trains(m); for (int i = 0; i < m; i++) { cin >> trains[i].s >> trains[i].t; --trains[i].s, --trains[i].t; } sort(trains.begin(), trains.end()); map<Pair, int> counts; counts[Pair(0, 0)] = 1; for (int i = 0; i < m; i++) { int s = trains[i].s; int t = trains[i].t + 1; map<Pair, int> next(counts); for (map<Pair, int>::reverse_iterator p = counts.rbegin(); p != counts.rend(); ++p) { int u = p->first.first, v = p->first.second; if (t <= u) { next[Pair(u, v)] = (next[Pair(u, v)] + counts[Pair(u, v)]) % kMod; continue; } if (t <= v) { int w = (s <= u ? t : u); next[Pair(w, v)] = (next[Pair(w, v)] + counts[Pair(u, v)]) % kMod; continue; } if (s <= u) { next[Pair(v, t)] = (next[Pair(v, t)] + counts[Pair(u, v)]) % kMod; continue; } if (s <= v) { next[Pair(u, t)] = (next[Pair(u, t)] + counts[Pair(u, v)]) % kMod; continue; } } counts.swap(next); } cout << counts[Pair(n, n)] << endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | H - ダイヤグラム |
User | yuizumi |
Language | C++ (G++ 4.6.4) |
Score | 100 |
Code Size | 1777 Byte |
Status | AC |
Exec Time | 432 ms |
Memory | 3244 KB |
Judge Result
Set Name | small | medium | large | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 10 / 10 | 40 / 40 | 50 / 50 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
small | small/case_000.txt, small/case_001.txt, small/case_002.txt, small/case_003.txt, small/case_004.txt, small/case_005.txt, small/case_006.txt, small/case_007.txt, small/case_008.txt, small/case_009.txt, small/case_010.txt, small/case_011.txt, small/case_012.txt, small/case_013.txt, small/case_014.txt, small/case_015.txt, small/case_016.txt, small/case_017.txt, small/case_018.txt, small/case_019.txt, small/case_020.txt, small/case_021.txt, small/case_022.txt, small/case_023.txt |
medium | medium/case_000.txt, medium/case_001.txt, medium/case_002.txt, medium/case_003.txt, medium/case_004.txt, medium/case_005.txt, medium/case_006.txt, medium/case_007.txt, medium/case_008.txt, medium/case_009.txt, medium/case_010.txt, medium/case_011.txt, medium/case_012.txt, medium/case_013.txt, medium/case_014.txt, medium/case_015.txt, medium/case_016.txt, medium/case_017.txt, medium/case_018.txt, medium/case_019.txt, medium/case_020.txt, medium/case_021.txt, medium/case_022.txt, medium/case_023.txt, medium/medium_case_000.txt, medium/medium_case_001.txt, medium/medium_case_002.txt, medium/medium_case_003.txt, medium/medium_case_004.txt, medium/medium_case_005.txt, medium/medium_case_006.txt, medium/medium_case_007.txt, medium/medium_case_008.txt, medium/medium_case_009.txt, medium/medium_case_010.txt, medium/medium_case_011.txt, medium/medium_case_012.txt, medium/medium_case_013.txt, medium/medium_case_014.txt, medium/medium_case_015.txt, medium/medium_case_016.txt, medium/medium_case_017.txt, medium/medium_case_018.txt, medium/medium_case_019.txt, medium/medium_case_020.txt |
large | large/case_000.txt, large/case_001.txt, large/case_002.txt, large/case_003.txt, large/case_004.txt, large/case_005.txt, large/case_006.txt, large/case_007.txt, large/case_008.txt, large/case_009.txt, large/case_010.txt, large/case_011.txt, large/case_012.txt, large/case_013.txt, large/case_014.txt, large/case_015.txt, large/case_016.txt, large/case_017.txt, large/case_018.txt, large/case_019.txt, large/case_020.txt, large/case_021.txt, large/case_022.txt, large/case_023.txt, large/large_case_000.txt, large/large_case_001.txt, large/large_case_002.txt, large/large_case_003.txt, large/large_case_004.txt, large/large_case_005.txt, large/large_case_006.txt, large/large_case_007.txt, large/large_case_008.txt, large/large_case_009.txt, large/large_case_010.txt, large/large_case_011.txt, large/large_case_012.txt, large/large_case_013.txt, large/large_case_014.txt, large/large_case_015.txt, large/large_case_016.txt, large/large_case_017.txt, large/large_case_018.txt, large/large_case_019.txt, large/large_case_020.txt, large/large_case_021.txt, large/large_case_022.txt, large/large_case_023.txt, large/large_case_024.txt, large/large_case_025.txt, large/large_case_026.txt, large/large_case_027.txt, large/large_case_028.txt, large/large_case_029.txt, large/medium_case_000.txt, large/medium_case_001.txt, large/medium_case_002.txt, large/medium_case_003.txt, large/medium_case_004.txt, large/medium_case_005.txt, large/medium_case_006.txt, large/medium_case_007.txt, large/medium_case_008.txt, large/medium_case_009.txt, large/medium_case_010.txt, large/medium_case_011.txt, large/medium_case_012.txt, large/medium_case_013.txt, large/medium_case_014.txt, large/medium_case_015.txt, large/medium_case_016.txt, large/medium_case_017.txt, large/medium_case_018.txt, large/medium_case_019.txt, large/medium_case_020.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
large/case_000.txt | AC | 20 ms | 812 KB |
large/case_001.txt | AC | 20 ms | 792 KB |
large/case_002.txt | AC | 20 ms | 788 KB |
large/case_003.txt | AC | 20 ms | 788 KB |
large/case_004.txt | AC | 29 ms | 840 KB |
large/case_005.txt | AC | 20 ms | 780 KB |
large/case_006.txt | AC | 19 ms | 780 KB |
large/case_007.txt | AC | 19 ms | 788 KB |
large/case_008.txt | AC | 19 ms | 788 KB |
large/case_009.txt | AC | 19 ms | 784 KB |
large/case_010.txt | AC | 20 ms | 780 KB |
large/case_011.txt | AC | 19 ms | 780 KB |
large/case_012.txt | AC | 20 ms | 780 KB |
large/case_013.txt | AC | 20 ms | 792 KB |
large/case_014.txt | AC | 20 ms | 784 KB |
large/case_015.txt | AC | 19 ms | 784 KB |
large/case_016.txt | AC | 20 ms | 760 KB |
large/case_017.txt | AC | 20 ms | 792 KB |
large/case_018.txt | AC | 20 ms | 788 KB |
large/case_019.txt | AC | 20 ms | 784 KB |
large/case_020.txt | AC | 19 ms | 788 KB |
large/case_021.txt | AC | 20 ms | 700 KB |
large/case_022.txt | AC | 19 ms | 784 KB |
large/case_023.txt | AC | 20 ms | 788 KB |
large/large_case_000.txt | AC | 401 ms | 3000 KB |
large/large_case_001.txt | AC | 388 ms | 3008 KB |
large/large_case_002.txt | AC | 378 ms | 3136 KB |
large/large_case_003.txt | AC | 425 ms | 3120 KB |
large/large_case_004.txt | AC | 404 ms | 3120 KB |
large/large_case_005.txt | AC | 425 ms | 3096 KB |
large/large_case_006.txt | AC | 429 ms | 3128 KB |
large/large_case_007.txt | AC | 414 ms | 2996 KB |
large/large_case_008.txt | AC | 400 ms | 3120 KB |
large/large_case_009.txt | AC | 405 ms | 3244 KB |
large/large_case_010.txt | AC | 212 ms | 1464 KB |
large/large_case_011.txt | AC | 64 ms | 948 KB |
large/large_case_012.txt | AC | 185 ms | 1460 KB |
large/large_case_013.txt | AC | 112 ms | 1200 KB |
large/large_case_014.txt | AC | 155 ms | 1336 KB |
large/large_case_015.txt | AC | 44 ms | 940 KB |
large/large_case_016.txt | AC | 166 ms | 1468 KB |
large/large_case_017.txt | AC | 208 ms | 1456 KB |
large/large_case_018.txt | AC | 189 ms | 1464 KB |
large/large_case_019.txt | AC | 22 ms | 788 KB |
large/large_case_020.txt | AC | 432 ms | 3124 KB |
large/large_case_021.txt | AC | 399 ms | 3128 KB |
large/large_case_022.txt | AC | 410 ms | 3120 KB |
large/large_case_023.txt | AC | 424 ms | 3120 KB |
large/large_case_024.txt | AC | 421 ms | 2996 KB |
large/large_case_025.txt | AC | 395 ms | 3124 KB |
large/large_case_026.txt | AC | 383 ms | 3008 KB |
large/large_case_027.txt | AC | 401 ms | 3124 KB |
large/large_case_028.txt | AC | 423 ms | 3000 KB |
large/large_case_029.txt | AC | 395 ms | 3124 KB |
large/medium_case_000.txt | AC | 20 ms | 788 KB |
large/medium_case_001.txt | AC | 24 ms | 780 KB |
large/medium_case_002.txt | AC | 19 ms | 784 KB |
large/medium_case_003.txt | AC | 20 ms | 664 KB |
large/medium_case_004.txt | AC | 20 ms | 692 KB |
large/medium_case_005.txt | AC | 19 ms | 788 KB |
large/medium_case_006.txt | AC | 20 ms | 788 KB |
large/medium_case_007.txt | AC | 20 ms | 792 KB |
large/medium_case_008.txt | AC | 20 ms | 792 KB |
large/medium_case_009.txt | AC | 19 ms | 788 KB |
large/medium_case_010.txt | AC | 20 ms | 788 KB |
large/medium_case_011.txt | AC | 20 ms | 692 KB |
large/medium_case_012.txt | AC | 21 ms | 780 KB |
large/medium_case_013.txt | AC | 20 ms | 792 KB |
large/medium_case_014.txt | AC | 20 ms | 672 KB |
large/medium_case_015.txt | AC | 20 ms | 788 KB |
large/medium_case_016.txt | AC | 19 ms | 784 KB |
large/medium_case_017.txt | AC | 20 ms | 780 KB |
large/medium_case_018.txt | AC | 20 ms | 784 KB |
large/medium_case_019.txt | AC | 20 ms | 788 KB |
large/medium_case_020.txt | AC | 20 ms | 780 KB |
medium/case_000.txt | AC | 20 ms | 700 KB |
medium/case_001.txt | AC | 19 ms | 792 KB |
medium/case_002.txt | AC | 20 ms | 812 KB |
medium/case_003.txt | AC | 19 ms | 788 KB |
medium/case_004.txt | AC | 20 ms | 780 KB |
medium/case_005.txt | AC | 19 ms | 780 KB |
medium/case_006.txt | AC | 20 ms | 776 KB |
medium/case_007.txt | AC | 20 ms | 788 KB |
medium/case_008.txt | AC | 20 ms | 792 KB |
medium/case_009.txt | AC | 19 ms | 784 KB |
medium/case_010.txt | AC | 20 ms | 788 KB |
medium/case_011.txt | AC | 19 ms | 792 KB |
medium/case_012.txt | AC | 19 ms | 788 KB |
medium/case_013.txt | AC | 20 ms | 688 KB |
medium/case_014.txt | AC | 20 ms | 692 KB |
medium/case_015.txt | AC | 20 ms | 768 KB |
medium/case_016.txt | AC | 20 ms | 788 KB |
medium/case_017.txt | AC | 20 ms | 780 KB |
medium/case_018.txt | AC | 20 ms | 780 KB |
medium/case_019.txt | AC | 19 ms | 776 KB |
medium/case_020.txt | AC | 20 ms | 684 KB |
medium/case_021.txt | AC | 20 ms | 700 KB |
medium/case_022.txt | AC | 20 ms | 784 KB |
medium/case_023.txt | AC | 20 ms | 784 KB |
medium/medium_case_000.txt | AC | 19 ms | 792 KB |
medium/medium_case_001.txt | AC | 20 ms | 780 KB |
medium/medium_case_002.txt | AC | 20 ms | 780 KB |
medium/medium_case_003.txt | AC | 20 ms | 780 KB |
medium/medium_case_004.txt | AC | 20 ms | 684 KB |
medium/medium_case_005.txt | AC | 19 ms | 696 KB |
medium/medium_case_006.txt | AC | 19 ms | 792 KB |
medium/medium_case_007.txt | AC | 20 ms | 788 KB |
medium/medium_case_008.txt | AC | 20 ms | 788 KB |
medium/medium_case_009.txt | AC | 20 ms | 776 KB |
medium/medium_case_010.txt | AC | 20 ms | 784 KB |
medium/medium_case_011.txt | AC | 19 ms | 780 KB |
medium/medium_case_012.txt | AC | 19 ms | 788 KB |
medium/medium_case_013.txt | AC | 20 ms | 792 KB |
medium/medium_case_014.txt | AC | 20 ms | 704 KB |
medium/medium_case_015.txt | AC | 20 ms | 792 KB |
medium/medium_case_016.txt | AC | 20 ms | 784 KB |
medium/medium_case_017.txt | AC | 20 ms | 788 KB |
medium/medium_case_018.txt | AC | 20 ms | 784 KB |
medium/medium_case_019.txt | AC | 20 ms | 792 KB |
medium/medium_case_020.txt | AC | 20 ms | 784 KB |
small/case_000.txt | AC | 20 ms | 792 KB |
small/case_001.txt | AC | 20 ms | 792 KB |
small/case_002.txt | AC | 19 ms | 784 KB |
small/case_003.txt | AC | 20 ms | 632 KB |
small/case_004.txt | AC | 19 ms | 780 KB |
small/case_005.txt | AC | 20 ms | 788 KB |
small/case_006.txt | AC | 20 ms | 792 KB |
small/case_007.txt | AC | 20 ms | 700 KB |
small/case_008.txt | AC | 20 ms | 780 KB |
small/case_009.txt | AC | 19 ms | 788 KB |
small/case_010.txt | AC | 19 ms | 792 KB |
small/case_011.txt | AC | 19 ms | 792 KB |
small/case_012.txt | AC | 19 ms | 788 KB |
small/case_013.txt | AC | 20 ms | 784 KB |
small/case_014.txt | AC | 20 ms | 784 KB |
small/case_015.txt | AC | 20 ms | 792 KB |
small/case_016.txt | AC | 21 ms | 788 KB |
small/case_017.txt | AC | 20 ms | 780 KB |
small/case_018.txt | AC | 20 ms | 784 KB |
small/case_019.txt | AC | 19 ms | 788 KB |
small/case_020.txt | AC | 20 ms | 784 KB |
small/case_021.txt | AC | 19 ms | 784 KB |
small/case_022.txt | AC | 19 ms | 784 KB |
small/case_023.txt | AC | 20 ms | 792 KB |