QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#116483	#1857. PlayerUnknown's Battlegrounds	Linshey^#	AC ✓	121ms	4528kb	C++14	1.2kb	2023-06-29 13:00:10	2023-06-29 13:00:14

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-06-29 13:00:14]
评测

测评结果：AC
用时：121ms
内存：4528kb

查看

[2023-06-29 13:00:10]
提交

answer


#include <bits/stdc++.h>

using namespace std; const int maxn = 3e2 + 5;

int n, m, a[maxn][maxn];

int b[maxn];

int sk[maxn], tp, pl[maxn], pr[maxn];

int ans[maxn * maxn];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) scanf("%d", &a[i][j]);
    for (int l = 1; l <= n; l++)
    {
        memset(b, 63, sizeof b);
        for (int r = l; r <= n; r++)
        {
            for (int i = 1; i <= m; i++) b[i] = min(b[i], a[r][i]);
            // for (int i = 1; i <= m; i++) cerr << b[i] << ' '; cerr << endl;
            sk[tp = 0] = 0;
            for (int i = 1; i <= m; i++)
            {
                while (tp && b[i] < b[sk[tp]]) tp--;
                pl[i] = i - sk[tp];
                sk[++tp] = i;
            }
            sk[tp = 0] = m + 1;
            for (int i = m; i; i--)
            {
                while (tp && b[i] < b[sk[tp]]) tp--;
                pr[i] = sk[tp] - i;
                sk[++tp] = i;
            }
            for (int i = 1; i <= m; i++) ans[b[i]] += pl[i] * pr[i];
        }
    }
    for (int i = 1; i <= n * m; i++) printf("%d\n", ans[i]);
    return 0;
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 3784kb

input:

2 3
2 5 1
6 3 4

output:

result:

ok 6 lines

Test #2:

score: 0

Accepted

time: 2ms

memory: 3708kb

input:

50 50
274 1151 2130 502 862 1007 692 1789 1912 37 59 805 2056 891 1341 673 2436 1647 1925 1226 2209 2134 511 1308 1881 1692 1885 216 2321 1032 1106 334 893 720 2269 45 1069 2031 1891 370 40 1916 1790 1671 269 1343 349 509 137 9
2386 1275 834 1519 1896 1729 66 2049 872 262 2240 1813 943 968 475 2051 ...

output:

result:

ok 2500 lines

Test #3:

score: 0

Accepted

time: 2ms

memory: 3604kb

input:

50 50
1486 846 1348 2280 1801 1630 1057 2035 323 2469 1053 2260 2277 2042 1591 2411 674 2116 498 2077 812 1872 691 708 2262 2130 1296 293 1915 1881 1592 2239 2303 1099 1833 2017 2021 1264 1543 2022 2498 421 1715 1995 393 790 1397 676 2418 1555
2218 1749 1664 697 1762 1462 800 1058 502 1358 309 497 8...

output:

result:

ok 2500 lines

Test #4:

score: 0

Accepted

time: 2ms

memory: 3764kb

input:

50 50
2138 647 2428 2499 1570 1856 1404 2335 211 1993 1780 1162 646 410 705 1883 732 2036 1329 1436 1000 216 2011 1202 1524 671 48 946 1811 941 299 1779 2250 1160 488 1469 2295 1163 1808 1886 1372 1217 1434 2060 1758 2349 414 986 1662 2085
1502 718 585 66 1988 2339 813 331 2419 246 38 593 2265 46 17...

output:

result:

ok 2500 lines

Test #5:

score: 0

Accepted

time: 120ms

memory: 4528kb

input:

300 300
62869 36574 33553 12817 22897 15133 47681 36233 67491 54917 41006 49014 48160 44060 77045 79875 17268 87377 12861 38227 3522 81853 49342 29811 24853 60983 88195 36678 63004 36708 16597 40920 84626 70608 42409 47374 89927 53727 43606 83716 58162 10492 76055 13968 54935 31604 38043 36699 56552...

output:

result:

ok 90000 lines

Test #6:

score: 0

Accepted

time: 118ms

memory: 4484kb

input:

300 300
45470 232 22266 37811 73295 59071 35489 86729 9157 59666 65520 67574 10048 48974 28141 72609 69920 22159 28840 70557 55169 71459 45238 43870 21468 2694 82397 71477 86900 58403 70079 55423 57708 39860 64954 54014 73154 74266 4670 39740 52864 80614 11702 25938 26073 22481 26634 43153 48068 365...

output:

result:

ok 90000 lines

Test #7:

score: 0

Accepted

time: 121ms

memory: 4236kb

input:

300 300
48838 2225 49487 56229 48109 80155 12953 20004 26056 53133 35980 77317 31398 31694 15501 56351 36490 83765 70693 56514 73192 19288 62255 7445 28343 6052 41481 77527 60748 24800 87768 32632 46930 55723 61018 84686 73289 11989 56234 69830 48137 83926 23142 83564 73193 7579 87451 34705 34653 20...

output:

result:

ok 90000 lines

Test #8:

score: 0

Accepted

time: 115ms

memory: 4512kb

input:

300 300
89972 18931 37884 86155 67792 5439 24143 39132 36005 30319 14694 5937 57146 50245 34632 423 33483 13702 30393 66593 22951 70844 39102 35484 28314 51809 45108 88376 34733 87985 49179 66657 73285 57804 48637 21401 18795 56009 25929 47050 53300 37548 28204 83993 87230 68528 17847 20840 45883 22...

output:

result:

ok 90000 lines

Test #9:

score: 0

Accepted

time: 112ms

memory: 4292kb

input:

300 300
87526 37426 1206 17684 78970 44855 45208 24738 50843 66352 25237 20040 14018 50807 19730 30804 8151 83460 35912 47299 53385 39894 37147 27474 23306 50264 81167 32059 79206 72284 79037 27149 70233 86034 64675 26314 14286 41314 71660 26390 46069 11197 74838 80061 43614 50614 22316 14350 21033 ...

output:

result:

ok 90000 lines

Test #10:

score: 0

Accepted

time: 116ms

memory: 4296kb

input:

300 300
56657 88399 19758 79640 79069 43198 35760 25518 26694 33358 58223 74453 29579 33426 35988 26246 6453 9589 48534 13776 53617 75064 4239 88395 51440 34956 59833 73424 75399 48459 72334 15565 37412 9467 5573 70132 23041 74608 20223 74473 79026 30254 56499 83640 58367 3289 14951 3776 84874 50138...

output:

result:

ok 90000 lines

Test #11:

score: 0

Accepted

time: 112ms

memory: 4344kb

input:

300 300
63620 14003 46865 7239 19188 48845 46577 21432 14705 76644 60803 85227 43456 34047 48992 69775 43876 80494 11415 15196 66551 48864 80083 61035 43641 58124 52192 8556 81418 48199 72538 43972 75569 69248 54808 41682 1049 56881 69966 43852 7078 31100 80992 75969 25023 84610 45475 79861 87584 68...

output:

result:

ok 90000 lines