QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#78281#4743. RóżnorodnośćIndus40 2082ms136860kbC++142.1kb2023-02-17 16:21:512023-02-17 16:21:53

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-02-17 16:21:53]
  • 评测
  • 测评结果:40
  • 用时:2082ms
  • 内存:136860kb
  • [2023-02-17 16:21:51]
  • 提交

answer

#include <cstdio>
#include <iostream>
#include <set>
#define IN inline
using namespace std;

namespace IO {
    const int SIZE = (1 << 21) + 1;
    char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[55]; int ff, qr;
    #define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
    IN void flush(){fwrite (obuf, 1, oS - obuf, stdout); oS = obuf;}
    IN void putcc(char x){*oS ++ = x; if (oS == oT) flush();}
    template <class I>
    IN void read(I &x) {
        for (ff = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') ff = -1;
        for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); x *= ff;
    }
}
using namespace IO;

typedef long long LL;
const int N = 3005, M = 1e5 + 5;
int n, m, K, a[N][N], d[N], f[N];

struct node {
	int x, y;
	IN bool operator < (const node &c) const {return y < c.y ? 1 : (y == c.y ? x > c.x : 0);}
};
set<node> S[M];
typedef set<node>::iterator IT;

int main() {
	read(n), read(m), read(K);
	for(int i = 1; i <= n; ++i)
		for(int j = 1; j <= m; ++j) read(a[i][j]);
	int Mx = 0; LL sum = 0;
	for(int i = 1; i <= n; ++i) {
		if (i > K) {
			for(int j = 1; j <= m; ++j) {
				int l = j, r = min(j + K, m + 1);
				IT it = S[a[i - K][j]].lower_bound(node{i - K, j}), itt = it;
				if (it != S[a[i - K][j]].begin()) --itt, l = max(l, min((*itt).y + K, m + 1));
				++it;
				if (it != S[a[i - K][j]].end()) r = min(r, (*it).y);
				if (l < r) --d[l], ++d[r];
				S[a[i - K][j]].erase(--it);
			}
		}
		for(int j = 1; j <= m; ++j) {
			IT it = S[a[i][j]].insert(node{i, j}).first, itt = it;
			int l = j, r = min(j + K, m + 1);
			if (it != S[a[i][j]].begin()) --itt, l = max(l, min((*itt).y + K, m + 1));
			++it;
			if (it != S[a[i][j]].end()) r = min(r, (*it).y);
			if (l < r) ++d[l], --d[r];
		}
		for(int j = 1; j <= m; ++j) d[j] += d[j - 1], f[j] += d[j];
		for(int j = 1; j <= m; ++j) d[j] = 0;
		if (i >= K) for(int j = K; j <= m; ++j) Mx = max(Mx, f[j]), sum += f[j];
	}
	printf("%d %lld\n", Mx, sum);
}

詳細信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 2ms
memory: 11272kb

input:

3 5 2
1 5 3 3 3
4 1 3 3 4
4 2 4 4 3

output:

4 20

result:

points 1.0 read (4 20), answer is (4 20)

Test #2:

score: 10
Accepted
time: 5ms
memory: 12136kb

input:

100 100 10
91306 51479 54826 75223 35428 85264 75004 65924 21947 6904 8963 238 45279 67937 69262 197 73305 97207 47430 10715 53574 72318 80995 2100 58351 42451 71480 58479 47271 14042 37966 64247 68664 60734 38622 60010 20065 17992 10679 23838 78816 33323 86014 44651 6705 47297 82184 3143 56316 4527...

output:

100 827720

result:

points 1.0 read (100 827720), answer is (100 827720)

Test #3:

score: 10
Accepted
time: 1ms
memory: 12640kb

input:

100 100 50
64496 38874 48189 11899 33120 21851 53413 48452 59973 92990 80131 95134 61257 66659 99155 70782 9812 58126 93021 16288 12001 34171 26503 97321 39686 44903 6830 75325 92471 30121 8878 84556 42748 15619 53158 249 99909 3303 31069 38472 70566 43888 78572 48496 76411 62834 41068 87383 65776 8...

output:

2461 4934018

result:

points 1.0 read (2461 4934018), answer is (2461 4934018)

Test #4:

score: 10
Accepted
time: 3ms
memory: 12296kb

input:

100 99 10
54966 24501 49186 8761 98087 62704 46742 20275 55333 31056 3316 1522 47428 12673 79139 49186 67062 12575 76801 28656 40880 97132 71122 64898 53558 7824 55333 52030 34197 38563 81163 61038 94168 95662 27212 60371 77054 96664 48234 46004 89724 9825 59941 62188 25732 62688 30273 61545 7746 50...

output:

99 743402

result:

points 1.0 read (99 743402), answer is (99 743402)

Test #5:

score: 10
Accepted
time: 0ms
memory: 12244kb

input:

77 100 48
65113 40586 77535 74708 35660 7422 12773 34227 67276 59851 55836 26908 50992 29709 32592 54485 37822 80836 85471 89027 27520 84363 83749 85177 63590 91437 9837 44480 19273 68621 87795 35212 15194 35214 26336 87995 66796 50605 8441 85031 89625 18644 579 74637 18526 71917 34547 22258 67907 1...

output:

2270 3585449

result:

points 1.0 read (2270 3585449), answer is (2270 3585449)

Test #6:

score: 10
Accepted
time: 1ms
memory: 13648kb

input:

100 100 100
40193 76965 66973 15861 36722 31393 40205 54166 47864 19556 69661 13235 6988 69616 60048 34495 87573 25362 90962 72124 70512 91262 24810 27503 21691 86430 108 787 69795 72772 66208 41811 47875 36008 43416 63755 31020 27226 79287 29143 48600 85038 81493 60514 29384 80776 67363 44177 42946...

output:

9267 9267

result:

points 1.0 read (9267 9267), answer is (9267 9267)

Test #7:

score: 10
Accepted
time: 2ms
memory: 10644kb

input:

3 3 2
2 2 1
2 1 1
1 2 1

output:

2 8

result:

points 1.0 read (2 8), answer is (2 8)

Test #8:

score: 10
Accepted
time: 0ms
memory: 11532kb

input:

20 100 10
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...

output:

19 19019

result:

points 1.0 read (19 19019), answer is (19 19019)

Subtask #2:

score: 10
Accepted

Test #9:

score: 10
Accepted
time: 80ms
memory: 19048kb

input:

500 600 20
9042 72142 87980 57669 71456 73645 50464 87980 381 11369 81915 15547 18828 12406 35258 24586 50678 9028 5258 31692 61388 21878 68402 51732 31692 18347 85203 28349 47466 33500 15996 90722 87875 36339 18347 91251 67303 96279 57669 34595 38664 44806 750 83771 57500 9042 11625 11625 54591 218...

output:

100 27442112

result:

points 1.0 read (100 27442112), answer is (100 27442112)

Test #10:

score: 10
Accepted
time: 57ms
memory: 20760kb

input:

500 312 150
40498 26427 34930 91737 14640 39502 47569 37881 72731 82817 39502 20629 37345 21521 37646 21875 39502 34930 36028 37881 92237 41047 97318 30759 69561 89609 91737 67742 58867 35221 37881 6061 82817 48897 68348 96467 90436 23408 42540 83596 9278 89609 56847 17958 54135 73224 20629 29360 79...

output:

99 5629364

result:

points 1.0 read (99 5629364), answer is (99 5629364)

Test #11:

score: 10
Accepted
time: 89ms
memory: 20132kb

input:

500 599 30
25379 6767 25379 1162 6767 13531 13531 57620 13531 57620 13531 6767 57620 1162 6767 6767 6767 6767 6767 13531 6767 1162 25379 6767 1162 57620 13531 57620 25379 13531 6767 6767 6767 1162 1162 6767 25379 57620 1162 57620 25379 25379 25379 1162 25379 57620 6767 13531 1162 13531 25379 6767 25...

output:

6 1350720

result:

points 1.0 read (6 1350720), answer is (6 1350720)

Test #12:

score: 10
Accepted
time: 156ms
memory: 26580kb

input:

600 500 298
58302 64277 8389 79078 61986 50373 78876 58302 57350 1896 41918 64678 73366 75168 94586 73366 19884 47757 44739 64277 75716 8389 53185 69281 62367 41918 377 61986 77711 92306 79078 5427 57350 64678 58302 23544 41918 43122 8389 97345 94586 8389 103 57737 62367 53185 1896 9855 79078 99499 ...

output:

56 3206707

result:

points 1.0 read (56 3206707), answer is (56 3206707)

Test #13:

score: 10
Accepted
time: 192ms
memory: 29608kb

input:

599 597 300
34303 96991 52163 47668 81969 95509 14004 46249 52163 21323 14004 42397 54380 14004 78341 58801 85277 43134 48361 52163 61744 61744 73008 59383 96761 79835 62658 96991 13437 93321 34236 75984 66159 34303 11047 21323 53494 48636 96761 62658 96761 81969 11047 47668 42397 79835 84761 50514 ...

output:

100 8940000

result:

points 1.0 read (100 8940000), answer is (100 8940000)

Subtask #3:

score: 20
Accepted

Dependency #1:

100%
Accepted

Test #14:

score: 20
Accepted
time: 52ms
memory: 23100kb

input:

600 600 100
53169 75015 3584 33705 94686 32491 68237 16354 84798 12258 67365 5443 63163 33255 61895 81897 61002 44897 3873 19255 21129 17753 4138 69104 63785 73638 36739 8697 71733 77413 62370 5534 18298 6794 98480 20942 27018 15585 75412 92609 33049 80876 51622 42965 25392 61287 24420 31124 22381 6...

output:

9592 2387932623

result:

points 1.0 read (9592 2387932623), answer is (9592 2387932623)

Test #15:

score: 20
Accepted
time: 30ms
memory: 19908kb

input:

600 600 5
6968 24815 93646 84863 77609 40598 6011 43001 25469 32756 25213 31187 48747 87097 96833 50761 39568 69951 75376 69367 40233 5286 44891 20310 32750 94523 50398 81886 8358 51824 31767 78540 46698 71141 14943 32554 72771 48349 87867 273 22645 54876 37689 23303 21366 72771 93429 64309 93486 64...

output:

25 8400862

result:

points 1.0 read (25 8400862), answer is (25 8400862)

Test #16:

score: 20
Accepted
time: 87ms
memory: 34968kb

input:

600 600 500
94408 25551 26106 17499 33966 11993 60914 65730 52906 1455 82794 73795 93412 45890 99934 11687 92321 92137 66466 31214 33613 75980 7050 48011 57463 63723 79159 72353 38799 3627 91506 26571 77219 85065 855 62559 26969 60930 5866 8582 44360 45945 36142 36545 77505 42759 43631 85010 65610 7...

output:

91990 937624827

result:

points 1.0 read (91990 937624827), answer is (91990 937624827)

Test #17:

score: 20
Accepted
time: 114ms
memory: 29588kb

input:

599 597 300
89055 74576 25792 58850 55997 87049 4799 83419 49059 97961 18167 25085 58107 53309 70962 49381 69164 78143 15307 65735 97850 36627 87682 66466 30999 31061 94967 32637 60460 71131 86691 39292 90365 15876 94354 93943 30765 35964 11540 13383 7889 78449 27807 24563 53104 53740 21252 19404 94...

output:

9450 839975421

result:

points 1.0 read (9450 839975421), answer is (9450 839975421)

Test #18:

score: 20
Accepted
time: 1ms
memory: 15856kb

input:

200 200 200
71769 43808 76881 31664 70849 51682 63553 16532 53486 41555 70173 94815 42118 13658 83060 52554 85652 50182 90980 83181 18552 82661 47268 25457 44694 18291 36101 23808 21044 64196 33849 74469 74148 33191 90590 87787 33241 11257 90177 76598 96953 28448 86365 93417 68172 15566 73419 4208 3...

output:

40000 40000

result:

points 1.0 read (40000 40000), answer is (40000 40000)

Subtask #4:

score: 0
Time Limit Exceeded

Test #19:

score: 45
Accepted
time: 1ms
memory: 23084kb

input:

1000 1 1
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
13
...

output:

1 1000

result:

points 1.0 read (1 1000), answer is (1 1000)

Test #20:

score: 45
Accepted
time: 2082ms
memory: 136860kb

input:

1500 1500 1500
2057 97289 11714 37286 42177 16754 79528 59246 64175 45623 4520 39496 11777 29875 37503 14157 31214 26265 89910 16164 22254 9643 11083 68021 52923 15438 30801 36202 82991 50951 48515 2156 28524 39879 15191 67450 48448 7429 47735 89030 34952 65783 8838 71730 42366 25873 4974 17173 8855...

output:

996 996

result:

points 1.0 read (996 996), answer is (996 996)

Test #21:

score: 45
Accepted
time: 598ms
memory: 84740kb

input:

1111 1111 1110
78578 53876 79527 19973 6069 60807 57219 24646 85707 38724 18215 36654 79802 31672 45974 31586 9376 94679 80478 3712 20617 59216 46217 62567 48013 45958 57577 53871 8063 48895 44884 59181 83491 85355 36105 62788 35545 58042 99327 45680 60765 30825 30746 73309 56898 54912 88701 82080 2...

output:

100000 400000

result:

points 1.0 read (100000 400000), answer is (100000 400000)

Test #22:

score: 0
Time Limit Exceeded

input:

3000 3000 1500
9697 30328 70153 69385 32612 1369 48645 51241 62 49586 6227 85468 84509 45231 94421 17466 52320 87303 95659 50899 63939 14146 2692 46715 55147 17380 54892 54242 8297 12874 33367 28839 18771 84346 60591 89791 6227 34671 90327 34143 50012 39722 75650 28602 49266 90327 49511 14757 41616 ...

output:


result:


Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

0%