QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #406347 | #6833. My University Is Better Than Yours | james1BadCreeper# | TL | 863ms | 42732kb | C++17 | 1.2kb | 2024-05-07 10:24:02 | 2024-05-07 10:24:02 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, m, L[N], ans[N], cnt;
vector<int> a[N], idx[N];
unordered_set<int> s;
bool svd[N];
void solve(int val) {
// assert(++cnt <= );
if (svd[val]) return;
s.insert(val); svd[val] = 1;
for (int j = 1; j <= m; ++j) {
int p = idx[j][val];
if (L[j] >= p) {
for (int k = p; k <= L[j]; ++k)
s.insert(a[j][k]);
}
}
for (int j = 1; j <= m; ++j) {
int p = idx[j][val];
if (L[j] >= p) {
for (int k = p; k <= L[j]; ++k)
solve(a[j][k]);
L[j] = p - 1;
}
}
}
int main(void) {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
a[i].resize(n + 1); idx[i].resize(n + 1); L[i] = n;
for (int j = 1; j <= n; ++j) cin >> a[i][j], idx[i][a[i][j]] = j;
}
for (int i = n; i >= 1; --i) {
int val = a[1][i]; solve(val);
ans[a[1][i]] = s.size() - 1;
}
for (int i = 1; i <= n; ++i) cout << ans[i] << " \n"[i == n];
// cerr << cnt << "\n";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 4ms
memory: 30876kb
input:
4 2 1 2 3 4 1 3 2 4
output:
3 2 2 0
result:
ok 4 number(s): "3 2 2 0"
Test #2:
score: 0
Accepted
time: 4ms
memory: 30228kb
input:
4 2 1 2 3 4 4 3 2 1
output:
3 3 3 3
result:
ok 4 number(s): "3 3 3 3"
Test #3:
score: 0
Accepted
time: 4ms
memory: 30156kb
input:
5 2 5 4 3 2 1 5 4 3 2 1
output:
0 1 2 3 4
result:
ok 5 number(s): "0 1 2 3 4"
Test #4:
score: 0
Accepted
time: 3ms
memory: 30284kb
input:
10 5 3 6 1 10 9 7 2 5 8 4 3 6 10 1 9 7 2 5 8 4 3 1 10 9 7 6 5 8 2 4 3 7 1 9 6 10 8 2 5 4 3 6 9 1 7 10 2 5 8 4
output:
8 3 9 0 3 8 8 3 8 8
result:
ok 10 numbers
Test #5:
score: 0
Accepted
time: 0ms
memory: 30476kb
input:
10 5 1 7 5 9 10 8 2 6 4 3 5 1 7 9 10 8 2 6 4 3 5 7 1 9 8 2 6 10 4 3 1 7 5 9 10 6 2 8 3 4 1 7 5 9 8 2 6 10 3 4
output:
9 5 1 1 9 5 9 5 6 5
result:
ok 10 numbers
Test #6:
score: 0
Accepted
time: 7ms
memory: 29608kb
input:
10 5 5 7 8 9 1 10 4 2 6 3 8 5 7 9 1 10 3 6 4 2 7 8 5 1 10 9 6 4 2 3 8 7 5 1 10 9 3 4 6 2 5 8 7 9 10 1 3 4 2 6
output:
6 3 3 3 9 3 9 9 6 6
result:
ok 10 numbers
Test #7:
score: 0
Accepted
time: 6ms
memory: 29392kb
input:
100 100 48 32 13 55 64 27 74 82 24 94 87 58 28 50 7 2 78 51 89 97 29 10 47 25 61 70 39 79 60 68 37 80 14 23 88 8 43 34 45 46 99 33 17 35 76 63 84 66 20 56 36 44 73 40 75 69 95 42 22 21 77 53 85 62 5 86 71 52 16 15 12 3 19 49 6 26 18 4 9 57 31 93 98 54 90 59 11 67 38 96 83 30 91 1 92 100 65 72 41 81 ...
output:
10 99 35 23 35 35 99 65 23 99 23 35 99 77 35 35 65 23 35 52 46 46 77 99 77 35 99 99 99 10 23 99 65 65 65 52 77 23 77 46 10 46 65 52 65 65 77 99 35 99 99 35 46 23 99 52 23 99 23 77 77 46 65 99 10 52 23 77 46 77 35 10 52 99 46 65 46 99 77 77 10 99 10 65 46 35 99 65 99 23 10 10 23 99 46 10 99 23 65 10
result:
ok 100 numbers
Test #8:
score: 0
Accepted
time: 4ms
memory: 28992kb
input:
100 100 17 19 33 40 49 80 64 83 41 1 94 60 48 57 47 51 79 30 28 2 3 13 39 15 71 54 91 95 68 14 25 53 96 18 59 72 67 42 20 78 56 69 7 52 90 76 26 4 9 93 70 34 66 98 29 75 62 35 5 12 38 84 27 88 22 43 50 10 44 58 73 65 97 81 99 87 11 21 100 92 23 8 24 77 32 45 82 63 6 74 55 46 36 16 31 61 89 85 37 86 ...
output:
91 91 91 61 49 22 61 22 61 32 32 49 78 78 78 8 99 78 99 61 22 49 22 22 78 61 49 91 49 91 8 22 99 49 49 8 8 49 78 99 91 78 49 32 22 8 91 91 99 49 91 61 78 78 22 61 91 32 78 91 8 49 22 99 32 49 78 78 61 49 78 78 32 22 49 61 22 61 91 99 32 22 99 49 8 8 32 49 8 61 78 22 61 91 78 78 32 49 32 22
result:
ok 100 numbers
Test #9:
score: 0
Accepted
time: 0ms
memory: 29420kb
input:
100 100 14 69 74 87 67 49 22 19 60 52 37 3 56 68 27 30 61 77 55 45 28 73 84 63 5 35 54 83 97 57 7 9 47 53 18 100 70 94 29 79 12 91 64 24 51 16 21 41 32 82 62 58 39 15 95 78 11 93 23 76 98 90 86 31 81 66 85 50 36 48 80 2 44 42 96 4 89 75 71 40 92 25 13 46 6 10 8 20 1 99 59 72 33 34 88 17 26 43 65 38 ...
output:
22 34 99 34 84 22 72 22 72 22 49 62 22 99 49 62 6 72 99 22 62 99 49 62 22 6 99 84 62 84 49 62 22 6 84 34 99 6 49 22 62 34 6 34 84 22 72 34 99 34 62 99 72 84 84 99 72 49 22 99 84 49 84 62 6 34 99 99 99 72 22 22 84 99 22 49 84 49 62 34 49 62 72 84 34 49 99 6 34 49 62 22 49 62 49 34 72 49 22 72
result:
ok 100 numbers
Test #10:
score: 0
Accepted
time: 33ms
memory: 31708kb
input:
3000 30 2850 2083 2621 666 1485 2488 2724 2240 2420 902 2198 1373 2838 857 2514 1847 2552 396 1724 2374 2647 927 106 2827 1134 2812 1878 2575 1984 920 1250 518 2383 2319 2221 2569 1694 2049 693 926 68 2846 535 782 1637 2922 1194 692 1062 159 1130 2860 1604 1528 1540 2824 440 575 1943 2220 638 2487 1...
output:
2101 1812 540 1613 2493 1530 2306 2008 438 823 2898 1423 1709 823 1022 2580 2580 2898 1316 2390 823 931 540 105 216 105 639 2675 1812 1709 2580 1530 2780 1530 1225 1902 438 2780 931 2675 2008 105 540 1530 2306 1121 2203 1225 1709 2580 2780 1530 2999 438 2580 2898 1812 316 2008 2493 931 1423 1812 540...
result:
ok 3000 numbers
Test #11:
score: 0
Accepted
time: 26ms
memory: 31232kb
input:
3000 30 2568 1369 1963 197 594 2823 2603 1256 2936 784 2050 474 1152 2529 84 786 826 1367 2013 1581 1436 714 2195 2892 1522 1463 1430 528 2896 1837 1499 1728 140 1403 2783 1606 1807 1251 2340 1876 982 1103 1144 1427 2737 2364 1041 1380 5 2049 2045 1765 2489 491 2763 634 2877 1870 2718 31 973 215 477...
output:
864 566 1474 2896 2999 2501 2501 1778 781 864 683 1565 1369 1369 566 1778 2701 477 2383 1260 781 975 2600 1175 1074 864 975 1369 1778 683 2999 2701 2383 2383 864 1881 781 781 2794 204 2270 1175 1982 864 2794 2701 975 2176 1369 975 2071 1474 1474 781 1881 2383 379 204 379 1474 1565 2600 2383 2600 250...
result:
ok 3000 numbers
Test #12:
score: 0
Accepted
time: 34ms
memory: 31064kb
input:
3000 30 2722 1084 373 2550 4 1389 1704 812 676 2775 559 2738 2354 2392 138 1981 729 2208 64 1091 1809 1186 44 1356 2469 1129 2441 2298 2667 822 833 2389 1681 1660 1277 2303 2003 1284 2083 137 403 1326 174 298 304 1780 1890 2425 2287 802 1542 1480 2842 1395 1822 2379 531 1329 821 228 470 707 2411 168...
output:
1582 2007 294 2999 95 199 799 703 2819 2117 799 1180 2117 2198 2819 2198 1896 2915 2117 1278 199 2117 2293 1896 2680 2680 2680 1478 799 1278 2819 381 2198 2293 1788 2480 1278 1691 1896 2378 799 1691 2480 2999 2293 1691 703 2007 2117 1090 1691 2580 2198 2007 1478 2819 2480 2198 2915 199 703 2480 1582...
result:
ok 3000 numbers
Test #13:
score: 0
Accepted
time: 335ms
memory: 38532kb
input:
3000 333 680 1795 1926 242 2778 468 264 2132 102 221 2992 2723 2394 2095 2203 1787 1130 1211 2830 2296 2973 1584 2843 2511 2255 1825 2099 1183 1248 2501 2735 2733 1923 1363 2703 2113 2193 2526 2851 2845 2320 1430 1800 2769 1963 1159 2134 2821 1945 661 2555 1002 59 2257 1047 708 2800 30 1182 390 765 ...
output:
92 1581 2171 282 1481 1767 485 2902 1398 1208 485 2171 1208 2280 2819 905 2902 687 687 185 185 2902 1662 1581 485 2506 687 485 1303 2999 1767 1581 687 1398 2095 1767 2280 1004 584 2716 2391 2391 2999 2506 1481 1398 2391 801 1767 2819 485 185 801 2391 400 400 485 400 2999 2819 485 687 282 2612 2506 4...
result:
ok 3000 numbers
Test #14:
score: 0
Accepted
time: 318ms
memory: 37220kb
input:
3000 333 2970 219 1115 2730 2394 2110 1630 246 1440 2023 1031 970 2719 2467 2131 1712 394 1277 302 629 576 662 1653 2699 757 167 929 543 254 918 1469 2834 1770 1130 2907 2494 1655 1144 2001 1736 1473 534 87 2175 2041 181 1846 705 2370 91 65 1544 1704 2521 1570 2697 2869 654 2565 32 2053 147 1579 82 ...
output:
277 805 1601 2495 2284 1496 2184 194 2601 700 1422 2495 1086 1798 1086 603 1896 2601 805 700 1798 899 1896 2284 2388 277 1798 2699 603 2601 1321 2999 2388 2799 2904 1798 390 700 277 93 277 996 899 1086 1422 1496 1207 277 1422 390 2699 194 996 277 2699 1601 2699 1496 2495 2999 1086 603 390 805 2999 2...
result:
ok 3000 numbers
Test #15:
score: 0
Accepted
time: 863ms
memory: 41864kb
input:
100000 10 87622 15440 99929 63938 32210 16179 89583 9979 62875 51423 87887 76227 50916 59602 3454 29414 60989 63192 64574 41259 38684 13606 54802 9695 70894 39678 80292 72357 36545 17295 64261 3794 38384 32653 32229 48301 41998 81383 95781 98420 64899 51642 44597 45736 60273 84733 40945 96408 23768 ...
output:
18289 46488 17298 51922 64855 87826 4621 93958 32132 37357 46488 54328 10274 87826 13627 11241 94930 84410 66256 52596 20652 27913 55969 78457 45788 77786 15299 54328 1933 50264 5924 78106 63858 80102 43758 96653 66915 40705 5614 9567 52251 60231 99999 30524 67250 47842 38716 70612 57947 70280 9253 ...
result:
ok 100000 numbers
Test #16:
score: 0
Accepted
time: 861ms
memory: 42480kb
input:
100000 10 38952 45137 8328 76738 17830 22666 23245 90615 69197 9079 81528 14072 10882 53343 72179 54893 94553 18420 59624 70159 18566 79801 12125 52386 41406 50931 33028 38579 20057 83112 59225 93909 17262 96021 77983 70071 73110 16148 28263 29549 62967 69186 13246 35973 59392 75357 76895 18367 6095...
output:
16611 96992 68368 35096 25294 34439 7928 78476 10880 70349 8889 15236 93009 48540 94666 90038 41335 71685 59573 99292 51210 83059 15596 54582 45461 73985 53563 30994 50849 93685 30994 58921 26936 41335 63629 40692 75635 24589 30640 54251 32708 75938 1301 56559 51537 4021 66293 3659 39345 46523 96992...
result:
ok 100000 numbers
Test #17:
score: 0
Accepted
time: 179ms
memory: 41404kb
input:
100000 10 27556 5190 6330 97131 77410 22985 72703 94441 25175 87158 24005 10589 48589 4737 81840 16398 40308 89524 66077 46048 55046 57116 48230 91537 71378 71267 66028 57315 30919 3899 46595 12595 51936 46757 18311 5414 43657 96632 86440 35145 31928 76201 79149 60375 24443 7842 52014 10443 43279 14...
output:
83014 75071 59088 82357 85246 91730 45462 93118 43606 74907 73424 31805 18425 16305 23757 25735 45121 64242 12687 45585 59668 67514 42580 65792 97016 47781 28373 88559 74837 80057 93791 32339 82557 68529 24021 97495 38018 30881 60124 12000 68897 25871 4105 28133 58521 20183 55184 73187 64050 88488 1...
result:
ok 100000 numbers
Test #18:
score: 0
Accepted
time: 160ms
memory: 42732kb
input:
100000 10 78955 48058 22974 27565 30018 8461 89813 33317 9683 63141 75863 38473 60151 56040 16128 42391 33567 43360 21203 25874 41090 47850 81262 87143 73296 65112 64152 98783 38726 37759 44336 62321 11156 32760 41512 74612 69342 30137 42354 27431 7457 63221 90724 19641 20809 14899 10789 9236 7780 1...
output:
41272 94111 22620 45497 97503 6731 45522 64317 36281 86697 36818 42647 6867 32026 12454 97240 18459 11008 75037 62070 5933 95554 99888 75408 2024 78361 99395 27389 41747 54085 61662 22275 93640 23757 68058 1041 66166 71146 366 30435 87117 56120 39936 63305 89365 80862 74886 89329 61593 28485 92134 5...
result:
ok 100000 numbers
Test #19:
score: -100
Time Limit Exceeded
input:
100000 10 86419 18202 19817 86136 8685 38741 5212 9472 92095 38638 49349 7129 92261 62984 25799 72862 76089 75105 42003 95240 54490 589 85877 64752 99450 79220 53399 24513 18807 77519 90809 22390 846 24058 1385 37687 35001 37015 42418 96554 13509 67153 5057 71612 21028 88148 89779 28839 45873 4567 5...