oj.uz

Submission #143810

# Submission time Handle Problem Language Result Execution time Memory
143810 2019-08-15T08:37:17 Z ainta Rectangles (IOI19_rect) C++17
100 / 100
 3590 ms 803572 KB 
#include "rect.h"
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int n, m, w[2600][2600], T[2600];
vector<int>Right[2600][2600], Down[2600][2600];

int st[2600], RR[2600], LL[2600];

void PreCalc(int n) {
	int i, top = 0;
	for (i = 1; i <= n; i++)RR[i] = LL[i] = 0;
	for (i = 1; i <= n; i++) {
		while (top && T[st[top]] <= T[i]) {
			RR[st[top]] = i;
			top--;
		}
		st[++top] = i;
	}
	top = 0;
	for (i = n; i >= 1; i--) {
		while (top && T[st[top]] <= T[i]) {
			LL[st[top]] = i;
			top--;
		}
		st[++top] = i;
	}
}

int last[2600][2600], CC[2600][2600];
int lastH[2600], CH[2600];

struct point {
	int x, y, ck;
	bool operator<(const point &p)const {
		return x < p.x;
	}
}U[10100];

int BIT[2600];

void Add(int a, int b) {
	while (a <= m) {
		BIT[a] += b;
		a += (a&-a);
	}
}
int Sum(int a) {
	int r = 0;
	while (a) {
		r += BIT[a];
		a -= (a&-a);
	}
	return r;
}

long long count_rectangles(std::vector<std::vector<int> > a) {
	n = a.size();
	m = a[0].size();
	int i, j;
	for (i = 0; i < n; i++)for (j = 0; j < m; j++)w[i + 1][j + 1] = a[i][j];

	for (i = 1; i <= n; i++) {
		for (j = 1; j <= m; j++) {
			T[j] = w[i][j];
		}
		PreCalc(m);
		for (j = 1; j <= m; j++) {
			if (RR[j] && RR[j]>j+1)Right[i][j+1].push_back(RR[j]-1);
			if (LL[j] && LL[j]<j-1 && RR[LL[j]] != j)Right[i][LL[j] + 1].push_back(j - 1);
		}
	}
	for (i = 1; i <= m; i++) {
		for (j = 1; j <= n; j++) {
			T[j] = w[j][i];
		}
		PreCalc(n);
		for (j = 1; j <= n; j++) {
			if (RR[j] && RR[j] > j + 1)Down[j + 1][i].push_back(RR[j] - 1);
			if (LL[j] && LL[j] < j - 1 && RR[LL[j]] != j)Down[LL[j] + 1][i].push_back(j - 1);
		}
	}
	long long res = 0;
	for (i = n; i >= 1; i--) {
		for (j = 1; j <= n; j++)lastH[j] = CH[j] = 0;
		for (j = m; j >= 1; j--) {
			for (auto &t : Right[i][j]) {
				if (last[j][t] != i + 1)CC[j][t] = 0;
				CC[j][t]++;
				last[j][t] = i;
			}
			for (auto &t : Down[i][j]) {
				if (lastH[t] != j + 1)CH[t]=0;
				CH[t]++;
				lastH[t] = j;
			}
			int cnt = 0;
			for (auto &t : Right[i][j]) {
				U[cnt++] = { i,t,1 };
				U[cnt++] = { i + CC[j][t],t,-1 };
			}
			sort(U, U + cnt);
			sort(Down[i][j].begin(), Down[i][j].end());
			int pv = 0;
			for (auto &t : Down[i][j]) {
				while (pv < cnt && U[pv].x <= t) {
					Add(U[pv].y, U[pv].ck);
					pv++;
				}
				res += Sum(j + CH[t] - 1);
			}
			while (pv < cnt) {
				Add(U[pv].y, U[pv].ck);
				pv++;
			}
		}
	}

	return res;

}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 317952 KB Output is correct
2 Correct 305 ms 318212 KB Output is correct
3 Correct 295 ms 318400 KB Output is correct
4 Correct 305 ms 318320 KB Output is correct
5 Correct 299 ms 317948 KB Output is correct
6 Correct 345 ms 318328 KB Output is correct
7 Correct 304 ms 318072 KB Output is correct
8 Correct 353 ms 318200 KB Output is correct
9 Correct 294 ms 318204 KB Output is correct
10 Correct 288 ms 318200 KB Output is correct
11 Correct 298 ms 318236 KB Output is correct
12 Correct 293 ms 318200 KB Output is correct
13 Correct 288 ms 317940 KB Output is correct
14 Correct 288 ms 317944 KB Output is correct
15 Correct 288 ms 317944 KB Output is correct
16 Correct 290 ms 318004 KB Output is correct
17 Correct 288 ms 317820 KB Output is correct
18 Correct 289 ms 317816 KB Output is correct
19 Correct 290 ms 318332 KB Output is correct
20 Correct 289 ms 318072 KB Output is correct
21 Correct 288 ms 317944 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 317952 KB Output is correct
2 Correct 305 ms 318212 KB Output is correct
3 Correct 295 ms 318400 KB Output is correct
4 Correct 305 ms 318320 KB Output is correct
5 Correct 299 ms 317948 KB Output is correct
6 Correct 345 ms 318328 KB Output is correct
7 Correct 304 ms 318072 KB Output is correct
8 Correct 353 ms 318200 KB Output is correct
9 Correct 294 ms 318204 KB Output is correct
10 Correct 288 ms 318200 KB Output is correct
11 Correct 298 ms 318236 KB Output is correct
12 Correct 293 ms 318200 KB Output is correct
13 Correct 288 ms 317940 KB Output is correct
14 Correct 288 ms 317944 KB Output is correct
15 Correct 288 ms 317944 KB Output is correct
16 Correct 290 ms 318004 KB Output is correct
17 Correct 295 ms 319280 KB Output is correct
18 Correct 318 ms 319272 KB Output is correct
19 Correct 293 ms 319328 KB Output is correct
20 Correct 310 ms 319096 KB Output is correct
21 Correct 290 ms 319108 KB Output is correct
22 Correct 292 ms 319244 KB Output is correct
23 Correct 291 ms 319096 KB Output is correct
24 Correct 292 ms 318584 KB Output is correct
25 Correct 288 ms 317820 KB Output is correct
26 Correct 289 ms 317816 KB Output is correct
27 Correct 290 ms 318332 KB Output is correct
28 Correct 289 ms 318072 KB Output is correct
29 Correct 288 ms 317944 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 317952 KB Output is correct
2 Correct 305 ms 318212 KB Output is correct
3 Correct 295 ms 318400 KB Output is correct
4 Correct 305 ms 318320 KB Output is correct
5 Correct 299 ms 317948 KB Output is correct
6 Correct 345 ms 318328 KB Output is correct
7 Correct 304 ms 318072 KB Output is correct
8 Correct 353 ms 318200 KB Output is correct
9 Correct 294 ms 318204 KB Output is correct
10 Correct 288 ms 318200 KB Output is correct
11 Correct 298 ms 318236 KB Output is correct
12 Correct 293 ms 318200 KB Output is correct
13 Correct 288 ms 317940 KB Output is correct
14 Correct 288 ms 317944 KB Output is correct
15 Correct 288 ms 317944 KB Output is correct
16 Correct 290 ms 318004 KB Output is correct
17 Correct 295 ms 319280 KB Output is correct
18 Correct 318 ms 319272 KB Output is correct
19 Correct 293 ms 319328 KB Output is correct
20 Correct 310 ms 319096 KB Output is correct
21 Correct 290 ms 319108 KB Output is correct
22 Correct 292 ms 319244 KB Output is correct
23 Correct 291 ms 319096 KB Output is correct
24 Correct 292 ms 318584 KB Output is correct
25 Correct 303 ms 323212 KB Output is correct
26 Correct 305 ms 323320 KB Output is correct
27 Correct 305 ms 323228 KB Output is correct
28 Correct 316 ms 321500 KB Output is correct
29 Correct 308 ms 322040 KB Output is correct
30 Correct 309 ms 322096 KB Output is correct
31 Correct 304 ms 321912 KB Output is correct
32 Correct 315 ms 322040 KB Output is correct
33 Correct 288 ms 317820 KB Output is correct
34 Correct 289 ms 317816 KB Output is correct
35 Correct 290 ms 318332 KB Output is correct
36 Correct 289 ms 318072 KB Output is correct
37 Correct 288 ms 317944 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 317952 KB Output is correct
2 Correct 305 ms 318212 KB Output is correct
3 Correct 295 ms 318400 KB Output is correct
4 Correct 305 ms 318320 KB Output is correct
5 Correct 299 ms 317948 KB Output is correct
6 Correct 345 ms 318328 KB Output is correct
7 Correct 304 ms 318072 KB Output is correct
8 Correct 353 ms 318200 KB Output is correct
9 Correct 294 ms 318204 KB Output is correct
10 Correct 288 ms 318200 KB Output is correct
11 Correct 298 ms 318236 KB Output is correct
12 Correct 293 ms 318200 KB Output is correct
13 Correct 288 ms 317940 KB Output is correct
14 Correct 288 ms 317944 KB Output is correct
15 Correct 288 ms 317944 KB Output is correct
16 Correct 290 ms 318004 KB Output is correct
17 Correct 295 ms 319280 KB Output is correct
18 Correct 318 ms 319272 KB Output is correct
19 Correct 293 ms 319328 KB Output is correct
20 Correct 310 ms 319096 KB Output is correct
21 Correct 290 ms 319108 KB Output is correct
22 Correct 292 ms 319244 KB Output is correct
23 Correct 291 ms 319096 KB Output is correct
24 Correct 292 ms 318584 KB Output is correct
25 Correct 303 ms 323212 KB Output is correct
26 Correct 305 ms 323320 KB Output is correct
27 Correct 305 ms 323228 KB Output is correct
28 Correct 316 ms 321500 KB Output is correct
29 Correct 308 ms 322040 KB Output is correct
30 Correct 309 ms 322096 KB Output is correct
31 Correct 304 ms 321912 KB Output is correct
32 Correct 315 ms 322040 KB Output is correct
33 Correct 420 ms 349292 KB Output is correct
34 Correct 407 ms 343032 KB Output is correct
35 Correct 373 ms 343292 KB Output is correct
36 Correct 405 ms 337016 KB Output is correct
37 Correct 502 ms 362688 KB Output is correct
38 Correct 498 ms 362616 KB Output is correct
39 Correct 559 ms 362748 KB Output is correct
40 Correct 516 ms 360184 KB Output is correct
41 Correct 397 ms 339708 KB Output is correct
42 Correct 433 ms 342248 KB Output is correct
43 Correct 531 ms 349048 KB Output is correct
44 Correct 538 ms 349532 KB Output is correct
45 Correct 426 ms 334756 KB Output is correct
46 Correct 411 ms 336832 KB Output is correct
47 Correct 499 ms 346872 KB Output is correct
48 Correct 504 ms 347128 KB Output is correct
49 Correct 288 ms 317820 KB Output is correct
50 Correct 289 ms 317816 KB Output is correct
51 Correct 290 ms 318332 KB Output is correct
52 Correct 289 ms 318072 KB Output is correct
53 Correct 288 ms 317944 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 319 ms 338448 KB Output is correct
2 Correct 306 ms 335228 KB Output is correct
3 Correct 290 ms 318072 KB Output is correct
4 Correct 294 ms 317788 KB Output is correct
5 Correct 308 ms 336120 KB Output is correct
6 Correct 348 ms 335992 KB Output is correct
7 Correct 308 ms 335992 KB Output is correct
8 Correct 307 ms 334840 KB Output is correct
9 Correct 332 ms 334392 KB Output is correct
10 Correct 313 ms 328388 KB Output is correct
11 Correct 331 ms 333560 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 318032 KB Output is correct
2 Correct 967 ms 416644 KB Output is correct
3 Correct 1787 ms 509560 KB Output is correct
4 Correct 1833 ms 510484 KB Output is correct
5 Correct 1788 ms 510420 KB Output is correct
6 Correct 464 ms 354660 KB Output is correct
7 Correct 588 ms 389368 KB Output is correct
8 Correct 625 ms 392584 KB Output is correct
9 Correct 288 ms 317820 KB Output is correct
10 Correct 289 ms 317816 KB Output is correct
11 Correct 290 ms 318332 KB Output is correct
12 Correct 289 ms 318072 KB Output is correct
13 Correct 288 ms 317944 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 317952 KB Output is correct
2 Correct 305 ms 318212 KB Output is correct
3 Correct 295 ms 318400 KB Output is correct
4 Correct 305 ms 318320 KB Output is correct
5 Correct 299 ms 317948 KB Output is correct
6 Correct 345 ms 318328 KB Output is correct
7 Correct 304 ms 318072 KB Output is correct
8 Correct 353 ms 318200 KB Output is correct
9 Correct 294 ms 318204 KB Output is correct
10 Correct 288 ms 318200 KB Output is correct
11 Correct 298 ms 318236 KB Output is correct
12 Correct 293 ms 318200 KB Output is correct
13 Correct 288 ms 317940 KB Output is correct
14 Correct 288 ms 317944 KB Output is correct
15 Correct 288 ms 317944 KB Output is correct
16 Correct 290 ms 318004 KB Output is correct
17 Correct 295 ms 319280 KB Output is correct
18 Correct 318 ms 319272 KB Output is correct
19 Correct 293 ms 319328 KB Output is correct
20 Correct 310 ms 319096 KB Output is correct
21 Correct 290 ms 319108 KB Output is correct
22 Correct 292 ms 319244 KB Output is correct
23 Correct 291 ms 319096 KB Output is correct
24 Correct 292 ms 318584 KB Output is correct
25 Correct 303 ms 323212 KB Output is correct
26 Correct 305 ms 323320 KB Output is correct
27 Correct 305 ms 323228 KB Output is correct
28 Correct 316 ms 321500 KB Output is correct
29 Correct 308 ms 322040 KB Output is correct
30 Correct 309 ms 322096 KB Output is correct
31 Correct 304 ms 321912 KB Output is correct
32 Correct 315 ms 322040 KB Output is correct
33 Correct 420 ms 349292 KB Output is correct
34 Correct 407 ms 343032 KB Output is correct
35 Correct 373 ms 343292 KB Output is correct
36 Correct 405 ms 337016 KB Output is correct
37 Correct 502 ms 362688 KB Output is correct
38 Correct 498 ms 362616 KB Output is correct
39 Correct 559 ms 362748 KB Output is correct
40 Correct 516 ms 360184 KB Output is correct
41 Correct 397 ms 339708 KB Output is correct
42 Correct 433 ms 342248 KB Output is correct
43 Correct 531 ms 349048 KB Output is correct
44 Correct 538 ms 349532 KB Output is correct
45 Correct 426 ms 334756 KB Output is correct
46 Correct 411 ms 336832 KB Output is correct
47 Correct 499 ms 346872 KB Output is correct
48 Correct 504 ms 347128 KB Output is correct
49 Correct 319 ms 338448 KB Output is correct
50 Correct 306 ms 335228 KB Output is correct
51 Correct 290 ms 318072 KB Output is correct
52 Correct 294 ms 317788 KB Output is correct
53 Correct 308 ms 336120 KB Output is correct
54 Correct 348 ms 335992 KB Output is correct
55 Correct 308 ms 335992 KB Output is correct
56 Correct 307 ms 334840 KB Output is correct
57 Correct 332 ms 334392 KB Output is correct
58 Correct 313 ms 328388 KB Output is correct
59 Correct 331 ms 333560 KB Output is correct
60 Correct 350 ms 318032 KB Output is correct
61 Correct 967 ms 416644 KB Output is correct
62 Correct 1787 ms 509560 KB Output is correct
63 Correct 1833 ms 510484 KB Output is correct
64 Correct 1788 ms 510420 KB Output is correct
65 Correct 464 ms 354660 KB Output is correct
66 Correct 588 ms 389368 KB Output is correct
67 Correct 625 ms 392584 KB Output is correct
68 Correct 2214 ms 629228 KB Output is correct
69 Correct 2164 ms 548552 KB Output is correct
70 Correct 1368 ms 548216 KB Output is correct
71 Correct 1203 ms 467476 KB Output is correct
72 Correct 3511 ms 803476 KB Output is correct
73 Correct 2205 ms 514976 KB Output is correct
74 Correct 2387 ms 522812 KB Output is correct
75 Correct 3501 ms 627248 KB Output is correct
76 Correct 2227 ms 519504 KB Output is correct
77 Correct 2927 ms 572688 KB Output is correct
78 Correct 3590 ms 632264 KB Output is correct
79 Correct 2075 ms 496632 KB Output is correct
80 Correct 3427 ms 604396 KB Output is correct
81 Correct 3337 ms 595588 KB Output is correct
82 Correct 2195 ms 618800 KB Output is correct
83 Correct 3463 ms 803124 KB Output is correct
84 Correct 3467 ms 803572 KB Output is correct
85 Correct 3481 ms 803560 KB Output is correct
86 Correct 288 ms 317820 KB Output is correct
87 Correct 289 ms 317816 KB Output is correct
88 Correct 290 ms 318332 KB Output is correct
89 Correct 289 ms 318072 KB Output is correct
90 Correct 288 ms 317944 KB Output is correct