QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#397228#8115. AN2DLlfxxx#110 ✓1083ms139672kbC++141.4kb2024-04-23 19:56:222024-07-04 03:37:11

Judging History

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

  • [2024-07-04 03:37:11]
  • 评测
  • 测评结果:110
  • 用时:1083ms
  • 内存:139672kb
  • [2024-04-23 19:56:22]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#ifdef IAKIOI
	#define cin fin
    ifstream cin("in.txt");
#endif
#define fi first
#define se second
template<typename cmp>
struct Queue
{
	int k, cnt;
	deque<pair<int,int>>q;
	inline void init(int _k)
	{
		k = _k;
		cnt = 0;
	}
	inline void push(int x)
	{
		++cnt;
		if (!q.empty() && cnt - q.front().se + 1 > k)
		{
			q.pop_front();
		}
		while (!q.empty() && cmp()(x, q.back().fi)) 
			q.pop_back();
		q.emplace_back(x, cnt);
	}
	inline int qry()
	{
		return q.front().fi;
	}
};
constexpr int N = 4005;
int c[N][N], dx[N][N], ans[N][N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a, b, n, m;
    cin >> a >> b;
    for (int i = 1; i <= a; ++i)
    	for (int j = 1; j <= b; ++j)
    		cin >> c[i][j];
    cin >> n >> m;
    for (int i = 1; i <= a; ++i) {
    	Queue<greater<int>>mx;
    	mx.init(m);
    	for (int j = 1; j <= b; ++j) {
    		mx.push(c[i][j]);
    		dx[i][j] = mx.qry();
		}
	}
	for (int j = m; j <= b; ++j) {
    	Queue<greater<int>>mx;
    	mx.init(n);
		for (int i = 1; i <= a; ++i) {
			mx.push(dx[i][j]);
			if (i >= n) {
                ans[i][j] = mx.qry();
            }
		}
	}
    for (int i = n; i <= a; ++i) {
        for (int j = m; j <= b; ++j) {
            cout << ans[i][j] << ' ';
        } cout << '\n';
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 12
Accepted

Test #1:

score: 12
Accepted
time: 2ms
memory: 9684kb

input:

39 1
-6034
1538
-3756
-2969
-9756
-169
-5571
-7688
4137
-9329
-4145
5131
8463
7292
8658
5970
-6970
5513
8331
-2350
-7728
3123
-3608
-4237
7927
7321
-215
3011
1919
-3547
-1363
1484
-7992
-6786
3802
1690
1930
-3516
-1648
39 1

output:

8658 

result:

ok single line: '8658 '

Test #2:

score: 0
Accepted
time: 2ms
memory: 9652kb

input:

39 17
-3287 8857 -995 -5489 7749 -3276 -4406 -3014 7576 -1085 7133 -7045 2215 -4976 -3335 -3037 -9046
-2842 -7200 -2164 -550 3381 6167 -5931 -9910 -3579 8609 1061 -9730 -2579 911 5351 5847 -696
-6179 -3534 -5080 -3523 -8782 -8337 -2031 5144 -2097 3779 5199 -5909 -3382 5785 -2879 -9485 1858
6186 -726...

output:

9988 

result:

ok single line: '9988 '

Test #3:

score: 0
Accepted
time: 0ms
memory: 9696kb

input:

27 16
401 -5548 -1905 461 5851 -7645 1656 -4668 5947 -1537 6575 8469 9904 7777 -2114 2821
-8362 735 6178 3674 -5315 -710 -3673 2255 -5890 -7424 3871 -4865 -9483 1233 9452 -2183
-2908 -5192 -751 -2480 6883 7075 1989 3088 -2711 -9289 -1869 4795 -9473 4293 5789 7703
-6794 -604 2428 6513 2039 2094 2567 ...

output:

9904 

result:

ok single line: '9904 '

Test #4:

score: 0
Accepted
time: 1ms
memory: 7640kb

input:

10 3
338 -9720 6072
3033 -1562 -869
-2381 4372 870
2684 -4727 -1522
-7939 7787 3161
-7829 7018 6410
9607 185 -1283
-7830 9528 618
-2382 -7553 -5811
6996 9145 6898
10 3

output:

9607 

result:

ok single line: '9607 '

Test #5:

score: 0
Accepted
time: 0ms
memory: 9696kb

input:

40 40
-5035 -8305 6773 -4361 -9527 9243 -7837 9810 6691 9699 -8587 4921 -2517 -2724 -8078 7940 -8182 -9257 -1403 3181 4607 1238 -1175 4511 2096 -8617 -2045 -1981 -4292 -5485 -5073 951 -9937 -1778 4365 -8615 -7207 -9609 -9553 -9359
7988 2693 2265 -2770 3663 4329 7643 -4665 7460 -1206 -2948 -7471 8889...

output:

9999 

result:

ok single line: '9999 '

Subtask #2:

score: 17
Accepted

Test #6:

score: 17
Accepted
time: 0ms
memory: 9956kb

input:

37 17
-1484 -4010 -2261 -104 3948 -7329 1159 826 -9954 1006 -6089 3055 2455 3487 -6661 -4265 -556
1834 6829 2580 4686 6756 5530 7573 8933 -2322 4822 6123 -1234 5325 7483 2833 4449 6575
-6118 -6728 -1721 -7158 -4042 -8213 1889 9626 2342 26 -7217 6898 8587 9614 -8671 5251 1430
5721 -9465 3796 -3647 -3...

output:

9833 9833 9805 9805 9805 9805 

result:

ok single line: '9833 9833 9805 9805 9805 9805 '

Test #7:

score: 0
Accepted
time: 1ms
memory: 7884kb

input:

23 35
-7341 9821 -6949 -955 7654 -8356 -4722 -8397 7233 -5035 -9421 -3564 -8882 -8987 3082 1261 -4941 7973 8467 4529 -5066 -4192 8699 -3196 -3352 -1813 -4990 8672 -1264 -3014 -1482 -4173 -3209 -7441 -6400
-1159 8419 -4703 2281 -6477 6063 1185 8014 -8895 -700 -180 -9366 7535 -2917 -5003 -8649 8409 -8...

output:

9963 9939 9939 9939 9939 9939 9939 9939 9939 9939 9939 9939 9939 9939 
9963 9939 9939 9939 9939 9939 9939 9939 9939 9939 9939 9939 9939 9939 
9963 9939 9939 9939 9939 9939 9939 9939 9939 9939 9939 9939 9939 9939 
9998 9998 9998 9998 9998 9998 9998 9998 9998 9998 9998 9998 9998 9998 

result:

ok 4 lines

Test #8:

score: 0
Accepted
time: 0ms
memory: 7756kb

input:

3 32
731 -500 -7509 1429 -4738 1763 -6611 -1397 5654 -5667 -7533 1888 -4439 -4664 -4659 2656 4845 -8047 -9509 -5438 -9859 898 -7782 -2042 7810 -2045 8887 -4562 -2268 8849 -2989 3953
-9112 -8827 -1731 -7218 9825 8779 -1728 -1911 3206 -1657 9844 6626 -3111 7947 -6138 7501 -9595 3690 8898 6249 -396 -11...

output:

731 -500 1429 1429 1763 1763 -1397 5654 5654 -5667 1888 1888 -4439 -4659 2656 4845 4845 -8047 -5438 -5438 898 898 -2042 7810 7810 8887 8887 -2268 8849 8849 3953 
-8827 -1731 -1731 9825 9825 8779 -1728 3206 3206 9844 9844 6626 7947 7947 7501 7501 3690 8898 8898 6249 -396 -1157 -8615 -4106 3943 3943 -...

result:

ok 3 lines

Test #9:

score: 0
Accepted
time: 2ms
memory: 9924kb

input:

40 40
-6790 -3746 -1167 3678 9775 5445 2017 -8552 8437 6476 -7679 -9943 266 9705 4872 5297 347 -4492 -3996 -5054 9245 3068 -208 1388 7676 -5859 -1002 -4502 -7239 6886 7736 2423 4611 -4405 7133 -6444 9851 -4725 -8240 81
-2515 4282 -8803 -2012 -3321 6408 4929 6541 -9513 3193 -1641 -1759 1584 5406 1782...

output:

-6790 -3746 -1167 3678 9775 5445 2017 -8552 8437 6476 -7679 -9943 266 9705 4872 5297 347 -4492 -3996 -5054 9245 3068 -208 1388 7676 -5859 -1002 -4502 -7239 6886 7736 2423 4611 -4405 7133 -6444 9851 -4725 -8240 81 
-2515 4282 -8803 -2012 -3321 6408 4929 6541 -9513 3193 -1641 -1759 1584 5406 1782 -251...

result:

ok 40 lines

Test #10:

score: 0
Accepted
time: 0ms
memory: 7772kb

input:

40 40
3489 -7189 7960 147 9471 -1570 -6899 4208 -164 5436 -9651 5150 3150 1557 7452 -9086 4592 529 4033 -9439 324 3558 3103 1054 -527 -5408 -4669 -9713 5659 -415 5278 -9547 -2366 -1213 -197 -5044 -9923 -3735 4323 -1055
-758 -3634 1234 5230 -3400 7941 -5408 -7035 -8110 -1592 253 2881 -9405 -8819 -574...

output:

9863 9863 9842 9721 9721 9721 9721 9654 9654 9654 9654 9656 9656 9656 9656 9656 9656 9656 9782 9834 9834 9834 9947 9947 9947 9947 9969 9969 9969 9969 9969 9969 
9863 9863 9842 9721 9721 9721 9721 9654 9654 9654 9654 9656 9656 9656 9656 9656 9656 9656 9782 9834 9834 9834 9947 9947 9947 9947 9969 9969...

result:

ok 17 lines

Subtask #3:

score: 25
Accepted

Test #11:

score: 25
Accepted
time: 8ms
memory: 18368kb

input:

188 641
9763 -630 -8216 4120 -499 -8808 -4873 3786 7259 -5915 -4726 9926 6444 971 -6267 5304 1000 7379 8780 4343 -4369 -6543 355 1458 -6705 -3129 7887 1816 2076 -2196 4775 -8403 -8319 -5709 1832 8648 5576 -486 -6282 -3234 8535 -4044 -4064 -7324 593 2999 94 -6678 8507 7575 -265 5540 -5856 3068 -6025 ...

output:

9926 9926 9926 9926 9926 9926 9926 9926 9926 9926 9926 9926 8780 8780 8780 8780 8780 8780 8780 8648 8648 8648 8648 8648 8648 8648 8648 8648 8648 8648 8648 8648 8648 8648 8648 8648 8535 8535 8535 8535 8535 8507 8507 8507 8507 8507 8507 8507 8507 8185 8185 8185 8185 8185 8185 8185 9728 9728 9728 9728 ...

result:

ok 187 lines

Test #12:

score: 0
Accepted
time: 52ms
memory: 35324kb

input:

632 942
956 2297 -5117 6371 9629 -433 8657 1849 -3875 -2106 2505 8078 7963 5528 8208 9340 8180 -8102 -6104 4896 -688 1371 -7263 -6775 3856 8932 1509 -2813 7202 -5499 -9603 -3586 -1617 -8862 -6211 1138 9592 8872 -9555 1108 8585 9094 7368 7539 6725 -6968 9804 987 -8457 460 -9695 6547 -3326 -4347 -8261...

output:

9747 9747 9903 9903 9903 9903 9903 9903 9903 9903 9903 9903 9903 9903 9903 9903 9903 9903 9903 9801 9801 9801 9801 9801 9977 9977 9977 9977 9977 9977 9977 9977 9977 9977 9977 9977 9977 9977 9977 9977 9977 9945 9945 9945 9945 9945 9945 9945 9945 9945 9945 9918 9918 9918 9918 9918 9918 9918 9918 9918 ...

result:

ok 619 lines

Test #13:

score: 0
Accepted
time: 9ms
memory: 37928kb

input:

818 77
-6841 9940 -1273 -2783 -1938 -716 -3636 1258 -6506 9162 2901 3838 259 1685 9493 -7731 -8374 -6053 1627 5216 -7966 -5907 5070 6340 2071 4045 1951 2906 -7872 2397 -9605 -5750 6318 2293 -2666 8044 3621 -7604 5801 8806 784 3883 9350 3610 6817 418 -6176 -9214 6991 -4620 8998 435 -632 639 4621 4315...

output:

9940 9940 9758 9664 9844 9844 9844 9590 9590 9322 9322 9322 9918 9918 9918 9204 9204 9128 9374 9868 9868 9868 9983 9983 9983 9793 9674 9903 9903 9903 9538 9582 9865 9865 9865 9862 9790 9964 9964 9964 9607 9350 9350 9762 9762 9762 9649 9649 9649 8998 9176 9176 9992 9992 9992 9594 9032 9911 9911 9911 ...

result:

ok 800 lines

Test #14:

score: 0
Accepted
time: 16ms
memory: 17948kb

input:

202 929
300 -2549 -1974 1701 -5755 7222 -6575 -9054 -1226 -2401 421 4921 5011 3520 -4097 -7501 1171 766 -5715 1568 5655 726 -8390 19 -4226 -3665 -605 7881 -9700 -9279 -8264 6201 -1747 -7728 8572 3030 399 -1383 -5726 1168 -1735 6652 1463 -7385 6423 1184 -9875 -8866 4046 6325 5100 -171 3917 -4176 7015...

output:

9999 9999 9999 9999 9930 9930 9575 9505 9505 9505 9665 9665 9665 9665 9665 9790 9790 9793 9793 9793 9793 9793 9793 9793 9915 9915 9915 9915 9915 9915 9915 9187 9313 9313 9313 9313 9313 9313 9828 9828 9828 9828 9979 9979 9979 9979 9979 9979 9979 9965 9592 9965 9965 9965 9965 9965 9965 9965 9802 9802 ...

result:

ok 193 lines

Test #15:

score: 0
Accepted
time: 35ms
memory: 30448kb

input:

485 659
5269 5957 -1075 -973 -5380 -9126 5153 -6424 -9013 -548 -7957 -4035 7861 -9578 -3401 -5892 -5644 -1535 1746 -7954 2579 1787 2378 -6646 3310 -1536 -5087 5347 9465 -1717 -4506 -6611 -2789 -7093 9652 8721 -9787 17 -8530 8885 8483 -226 1550 1732 -7617 -4320 1956 1683 -4995 -8074 5913 -2069 7283 9...

output:

9979 9979 9979 9979 9979 9979 9979 9979 9979 9979 9443 9949 9949 9949 9949 9949 9949 9962 9962 9962 9962 9962 9962 9962 9962 9962 9962 9962 9803 9987 9987 9987 9987 9987 9987 9987 9987 9987 9987 9987 9966 9966 9966 9966 9896 9896 9896 9573 9774 9774 9774 9774 9774 9774 9774 9774 9774 9774 9774 9946 ...

result:

ok 470 lines

Test #16:

score: 0
Accepted
time: 68ms
memory: 36280kb

input:

1000 1000
-7703 -6846 -6854 -4694 -9377 5975 -7571 -4709 -6282 9028 7655 6958 1888 -8870 -7463 -7290 7027 -6234 -6086 4825 8527 -4397 1954 8135 1592 -7006 -2511 9985 1070 -1892 7774 -1621 2209 -7050 -3313 9537 -1782 9822 -8212 6933 -9536 6986 8927 3743 -5313 -8479 -1663 8205 6506 -9345 9125 2772 -29...

output:

10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 ...

result:

ok 74 lines

Test #17:

score: 0
Accepted
time: 72ms
memory: 38552kb

input:

1000 1000
-5983 -6587 -9656 -6877 908 -5511 -3878 2995 4665 8018 -3211 329 8085 5209 -472 7102 -900 6768 7806 2559 3568 9218 -3567 5331 -3063 7861 -9594 -4980 -8570 5925 -6791 -4853 4405 4520 -218 -9660 -4814 3264 7327 -6591 223 -2865 7413 -8900 -2681 -1659 771 -6176 1800 9624 -248 7477 3442 -3528 -...

output:

10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 ...

result:

ok 352 lines

Subtask #4:

score: 56
Accepted

Test #18:

score: 56
Accepted
time: 412ms
memory: 83928kb

input:

2324 1757
-4612 2152 -4918 1667 1761 7376 7959 -401 5156 6032 -5381 2914 2742 -1165 -5916 -423 -1104 2576 -2549 7792 -3012 -4774 -7078 6887 4011 -5343 4663 -6066 2312 4300 -5993 -2041 7566 5532 -4702 9507 9879 96 6367 -573 9122 -9158 3140 7363 -675 5705 5864 8568 8123 8398 -2464 7615 -5350 2704 -132...

output:

4350 8535 6997 6913 9793 9861 7959 8594 6637 8576 8777 9799 5584 9676 9699 2924 9904 9928 8835 7792 3741 9927 8859 9835 5621 9713 4663 308 5128 9558 7234 6576 7566 9454 9163 9507 9879 9705 9287 8970 9122 9617 8742 7363 123 8515 6884 8568 9734 8398 6124 7615 5218 2704 4383 6456 8134 7058 6035 9602 74...

result:

ok 2318 lines

Test #19:

score: 0
Accepted
time: 8ms
memory: 12196kb

input:

79 2068
6738 -5517 7909 4511 -8447 5278 -61 -9793 9175 1817 5213 -6251 4826 -2869 -8572 -5938 -2181 -397 -3551 4552 1350 6201 -815 -7727 -6501 1 -2810 9147 5907 8392 9687 936 5894 1269 -8584 6913 863 2462 -5620 -1160 5095 4209 6331 3982 5080 -2732 7227 7727 -7486 441 152 2639 -5566 -3921 -7258 -8144...

output:

9974 9921 9945 8825 9684 9550 9504 7785 9943 5994 9602 8608 8982 9194 5727 7230 9339 9799 9909 9094 9785 9579 8768 9870 9400 8647 9321 9147 9195 9828 9936 9431 9482 9149 9995 9582 8982 9607 9916 9374 8621 9514 7412 7400 7700 9025 9806 9749 9161 9204 9829 7794 8642 8075 9752 8066 9313 7792 8407 8334 ...

result:

ok 60 lines

Test #20:

score: 0
Accepted
time: 395ms
memory: 67284kb

input:

1324 2756
-7835 -6362 7342 639 -4047 2809 2810 -4595 9292 -8540 809 -8728 5945 -1622 -5179 3385 2095 -6022 -2211 1843 -3877 -6130 4971 8024 9663 8129 8345 -2036 -6302 3436 -7749 -5011 7230 2474 -9408 1770 2085 7057 8566 1599 8607 -1143 2746 2161 995 9169 -2734 -6135 -1183 4380 9608 9140 -2747 -6575 ...

output:

7493 7342 7342 6748 9292 9489 9489 9489 9489 9489 6728 6728 6765 6765 6765 6765 6765 3334 4971 8024 9663 9663 9663 9663 9663 9870 9870 9870 9870 9870 9092 7230 7230 7120 8566 8566 8607 8607 8607 8607 8607 9169 9169 9169 9169 9169 9608 9608 9608 9608 9608 9140 8962 8962 8962 9843 9843 9843 9843 9843 ...

result:

ok 1323 lines

Test #21:

score: 0
Accepted
time: 267ms
memory: 88760kb

input:

2953 821
337 5972 6054 6702 6893 -2027 -8026 2108 -2425 6525 -9266 -740 -6408 -1692 -6131 -3112 1654 6567 3603 -725 -3838 460 -4187 -6328 -4242 303 -1801 -3936 -9605 4777 -8237 9120 7418 -4736 7297 -233 3531 -2829 3816 3661 974 5951 6778 -1303 7864 -7848 868 -366 -5481 4920 3855 2974 4419 4506 -2074...

output:

8093 8093 8093 8093 8093 8093 8004 8004 8004 8004 8004 7124 7124 7124 7124 7124 6567 6567 9875 9875 9875 9875 9875 9875 9875 9120 9120 9120 9120 9120 9120 9120 9017 9017 7321 8358 8358 8358 8358 8358 8358 8358 9405 9405 9405 9405 9405 9405 9405 4920 4506 5841 5841 5841 5841 5841 5841 5841 9868 9868 ...

result:

ok 2952 lines

Test #22:

score: 0
Accepted
time: 160ms
memory: 67176kb

input:

1309 1230
-1707 -4465 -9052 7135 45 -5665 6945 -6453 2885 4794 -2114 1414 9340 9924 6814 -8928 7670 -330 7540 848 5878 -5697 6848 -7014 -47 8306 1653 5770 5985 -9949 -6040 -6602 -6416 7006 -9862 -221 283 -4805 4996 -6398 696 -5004 -4939 -4152 6557 37 3926 -1009 -3487 3387 -4130 -1793 -6303 -5376 -74...

output:

9416 9416 9668 9982 9982 9982 9982 9982 9982 9982 9982 9982 9982 9969 9969 9969 9969 9969 9446 9446 9625 9625 9625 9625 9625 9625 9625 9625 9625 9625 9319 9402 9808 9894 9894 9894 9894 9894 9894 9894 9896 9896 9896 9896 9896 9896 9896 9896 9974 9974 9974 9974 9974 9974 9974 9974 9974 9974 9687 9512 ...

result:

ok 1298 lines

Test #23:

score: 0
Accepted
time: 1083ms
memory: 136260kb

input:

4000 4000
6890 -7122 -9895 1686 -9531 8957 -1518 -7838 -4239 -6894 6591 3689 -4950 -6964 -4455 -5232 -6630 -8795 -4031 -5148 154 -3491 -8194 -4747 191 -1939 5081 7304 4723 3700 -4432 -1147 -8981 5384 5599 -9476 -4379 -3546 -2377 -6553 5463 3209 7379 3895 -1460 7281 -4383 1850 5104 -3555 5744 -6078 5...

output:

10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 ...

result:

ok 568 lines

Test #24:

score: 0
Accepted
time: 970ms
memory: 139672kb

input:

4000 4000
8456 2319 -6932 -2508 3639 8132 1049 -6957 8106 4529 -2927 -4677 -1948 -1557 -4703 -2435 727 1148 -4397 -4318 7856 3936 1657 3387 6852 7895 -9850 1316 5898 2245 -5262 3593 4200 -7009 7761 -459 393 515 -774 -8371 -5141 4028 -2491 4126 1732 9263 7866 7942 -6087 -7778 7307 4561 4961 -4817 150...

output:

10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 10000 ...

result:

ok 1847 lines

Extra Test:

score: 0
Extra Test Passed