oj.uz

Submission #298389

# Submission time Handle Problem Language Result Execution time Memory
298389 2020-09-12T18:57:32 Z Abelyan Rectangles (IOI19_rect) C++17
100 / 100
 4061 ms 589548 KB 
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

//#pragma GCC target("avx2")
//#pragma GCC optimization("unroll-loops")
//#pragma GCC optimize("O2")
//#pragma GCC optimize("O3")

#define FOR(i,a) for (int i=0;i<(a);++i)
#define FORD(i,a) for (int i=(a)-1;i>=0;i--)
#define FORT(i,a,b) for (int i=(a);i<=(b);++i)
#define FORTD(i,b,a) for (int i=(b);i>=(a);--i)
#define trav(i,v) for (auto i : v)
#define all(v) v.begin(),v.end()
#define ad push_back
#define fr first
#define sc second
#define mpr(a,b) make_pair(a,b)
#define pir pair<int,int>
#define make_unique(v) v.erase(unique(all(v)),v.end())


const int N=2506;
vector<int> ver[N][N],bn[N][N];
int en[N][N], sk[N][N];

long long count_rectangles(vector<vector<int> > a) {

	int n=a.size();
	int m=a[0].size();
	FORT(j,1,m-2){
		stack<pir> s;
		s.push({INT_MAX,-1});
		int qan=0;
		FOR(i,n){
			while(s.top().fr<=a[i][j]){
				if (s.top().sc==i-1){
					s.pop();
					continue;
				}
				ver[i-1][j].ad(s.top().sc+1);
				bn[i-1][s.top().sc+1].ad(j);
				qan++;
				
				s.pop();
			}
			s.push({a[i][j],i});
		}
		while(s.size()!=1)s.pop();
		//assert(s.top().fr==INT_MAX);
		FORD(i,n){
			while(s.top().fr<=a[i][j]){
				if (s.top().sc==i+1 || s.top().fr==a[i][j]){
					s.pop();
					continue;
				}
				ver[s.top().sc-1][j].ad(i+1);
				bn[s.top().sc-1][i+1].ad(j);
				qan++;
				//assert(s.top().sc==2 && i==0 && a[0][j]>a[2][j] && s.top().fr==a[2][j]);
				s.pop();

			}
			s.push({a[i][j],i});

		}
		/*
		if (a[0][j]>a[1][j] && a[2][j]>a[1][j]);
		else assert(qan==0);*/
	}
	ll ans=0;
	FORT(i,1,n-2){
		stack<pir> s;
		s.push({INT_MAX,-1});
		FOR(j,m){
			while(s.top().fr<=a[i][j]){
				
				//cout<<i<<" hey "<<s.top().fr<<" "<<s.top().sc<<" "<<a[i][j]<<endl;
				if (s.top().sc==j-1){
					s.pop();
					continue;
				}
				int l=s.top().sc+1,r=j-1;
				
				//cout<<i<<" "<<l<<" "<<r<<" "<<sk[l][r]<<" "<<en[l][r]<<endl;
				if (en[l][r]!=i-1){
					sk[l][r]=i;
				}
				en[l][r]=i;
				trav(to,ver[i][l]){
					if (to<sk[l][r])continue;
					if (upper_bound(all(bn[i][to]),r)-lower_bound(all(bn[i][to]),l)==r-l+1)ans++;
				}
				s.pop();
			}
			s.push({a[i][j],j});
		}
		while(s.size()!=1)s.pop();
		FORD(j,m){
			while(s.top().fr<=a[i][j]){
				//cout<<i<<" "<<s.top().fr<<" "<<s.top().sc<<" "<<a[i][j]<<endl;
				if (s.top().sc==j+1 || s.top().fr==a[i][j]){
					s.pop();
					continue;
				}
				int l=j+1,r=s.top().sc-1;
				
				//cout<<"hey "<<i<<" "<<l<<" "<<r<<" "<<sk[l][r]<<" "<<en[l][r]<<endl;
				if (en[l][r]!=i-1){
					sk[l][r]=i;
				}
				en[l][r]=i;
				trav(to,ver[i][r]){
					if (to<sk[l][r])continue;
					if (upper_bound(all(bn[i][to]),r)-lower_bound(all(bn[i][to]),l)==r-l+1)ans++;
				}
				s.pop();
			}
			s.push({a[i][j],j});
		}
	}
	return ans;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 295288 KB Output is correct
2 Correct 200 ms 295416 KB Output is correct
3 Correct 199 ms 295416 KB Output is correct
4 Correct 198 ms 295416 KB Output is correct
5 Correct 199 ms 295268 KB Output is correct
6 Correct 203 ms 295544 KB Output is correct
7 Correct 201 ms 295416 KB Output is correct
8 Correct 199 ms 295544 KB Output is correct
9 Correct 197 ms 295460 KB Output is correct
10 Correct 198 ms 295544 KB Output is correct
11 Correct 217 ms 295544 KB Output is correct
12 Correct 204 ms 295544 KB Output is correct
13 Correct 198 ms 295288 KB Output is correct
14 Correct 199 ms 295288 KB Output is correct
15 Correct 199 ms 295288 KB Output is correct
16 Correct 208 ms 295288 KB Output is correct
17 Correct 196 ms 295288 KB Output is correct
18 Correct 204 ms 295288 KB Output is correct
19 Correct 200 ms 295544 KB Output is correct
20 Correct 200 ms 295288 KB Output is correct
21 Correct 203 ms 295208 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 295288 KB Output is correct
2 Correct 200 ms 295416 KB Output is correct
3 Correct 199 ms 295416 KB Output is correct
4 Correct 198 ms 295416 KB Output is correct
5 Correct 199 ms 295268 KB Output is correct
6 Correct 203 ms 295544 KB Output is correct
7 Correct 201 ms 295416 KB Output is correct
8 Correct 199 ms 295544 KB Output is correct
9 Correct 197 ms 295460 KB Output is correct
10 Correct 198 ms 295544 KB Output is correct
11 Correct 217 ms 295544 KB Output is correct
12 Correct 204 ms 295544 KB Output is correct
13 Correct 198 ms 295288 KB Output is correct
14 Correct 199 ms 295288 KB Output is correct
15 Correct 199 ms 295288 KB Output is correct
16 Correct 208 ms 295288 KB Output is correct
17 Correct 202 ms 295756 KB Output is correct
18 Correct 199 ms 295800 KB Output is correct
19 Correct 202 ms 295928 KB Output is correct
20 Correct 201 ms 296056 KB Output is correct
21 Correct 201 ms 296184 KB Output is correct
22 Correct 209 ms 296184 KB Output is correct
23 Correct 207 ms 296184 KB Output is correct
24 Correct 202 ms 295800 KB Output is correct
25 Correct 196 ms 295288 KB Output is correct
26 Correct 204 ms 295288 KB Output is correct
27 Correct 200 ms 295544 KB Output is correct
28 Correct 200 ms 295288 KB Output is correct
29 Correct 203 ms 295208 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 295288 KB Output is correct
2 Correct 200 ms 295416 KB Output is correct
3 Correct 199 ms 295416 KB Output is correct
4 Correct 198 ms 295416 KB Output is correct
5 Correct 199 ms 295268 KB Output is correct
6 Correct 203 ms 295544 KB Output is correct
7 Correct 201 ms 295416 KB Output is correct
8 Correct 199 ms 295544 KB Output is correct
9 Correct 197 ms 295460 KB Output is correct
10 Correct 198 ms 295544 KB Output is correct
11 Correct 217 ms 295544 KB Output is correct
12 Correct 204 ms 295544 KB Output is correct
13 Correct 198 ms 295288 KB Output is correct
14 Correct 199 ms 295288 KB Output is correct
15 Correct 199 ms 295288 KB Output is correct
16 Correct 208 ms 295288 KB Output is correct
17 Correct 202 ms 295756 KB Output is correct
18 Correct 199 ms 295800 KB Output is correct
19 Correct 202 ms 295928 KB Output is correct
20 Correct 201 ms 296056 KB Output is correct
21 Correct 201 ms 296184 KB Output is correct
22 Correct 209 ms 296184 KB Output is correct
23 Correct 207 ms 296184 KB Output is correct
24 Correct 202 ms 295800 KB Output is correct
25 Correct 208 ms 297132 KB Output is correct
26 Correct 207 ms 297080 KB Output is correct
27 Correct 208 ms 297080 KB Output is correct
28 Correct 210 ms 297824 KB Output is correct
29 Correct 213 ms 298360 KB Output is correct
30 Correct 214 ms 298616 KB Output is correct
31 Correct 214 ms 298360 KB Output is correct
32 Correct 216 ms 298360 KB Output is correct
33 Correct 196 ms 295288 KB Output is correct
34 Correct 204 ms 295288 KB Output is correct
35 Correct 200 ms 295544 KB Output is correct
36 Correct 200 ms 295288 KB Output is correct
37 Correct 203 ms 295208 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 295288 KB Output is correct
2 Correct 200 ms 295416 KB Output is correct
3 Correct 199 ms 295416 KB Output is correct
4 Correct 198 ms 295416 KB Output is correct
5 Correct 199 ms 295268 KB Output is correct
6 Correct 203 ms 295544 KB Output is correct
7 Correct 201 ms 295416 KB Output is correct
8 Correct 199 ms 295544 KB Output is correct
9 Correct 197 ms 295460 KB Output is correct
10 Correct 198 ms 295544 KB Output is correct
11 Correct 217 ms 295544 KB Output is correct
12 Correct 204 ms 295544 KB Output is correct
13 Correct 198 ms 295288 KB Output is correct
14 Correct 199 ms 295288 KB Output is correct
15 Correct 199 ms 295288 KB Output is correct
16 Correct 208 ms 295288 KB Output is correct
17 Correct 202 ms 295756 KB Output is correct
18 Correct 199 ms 295800 KB Output is correct
19 Correct 202 ms 295928 KB Output is correct
20 Correct 201 ms 296056 KB Output is correct
21 Correct 201 ms 296184 KB Output is correct
22 Correct 209 ms 296184 KB Output is correct
23 Correct 207 ms 296184 KB Output is correct
24 Correct 202 ms 295800 KB Output is correct
25 Correct 208 ms 297132 KB Output is correct
26 Correct 207 ms 297080 KB Output is correct
27 Correct 208 ms 297080 KB Output is correct
28 Correct 210 ms 297824 KB Output is correct
29 Correct 213 ms 298360 KB Output is correct
30 Correct 214 ms 298616 KB Output is correct
31 Correct 214 ms 298360 KB Output is correct
32 Correct 216 ms 298360 KB Output is correct
33 Correct 274 ms 318944 KB Output is correct
34 Correct 274 ms 318968 KB Output is correct
35 Correct 315 ms 325240 KB Output is correct
36 Correct 306 ms 325112 KB Output is correct
37 Correct 283 ms 310904 KB Output is correct
38 Correct 288 ms 311072 KB Output is correct
39 Correct 290 ms 311416 KB Output is correct
40 Correct 284 ms 310776 KB Output is correct
41 Correct 286 ms 310392 KB Output is correct
42 Correct 322 ms 312188 KB Output is correct
43 Correct 429 ms 318952 KB Output is correct
44 Correct 433 ms 321044 KB Output is correct
45 Correct 308 ms 307960 KB Output is correct
46 Correct 315 ms 311416 KB Output is correct
47 Correct 407 ms 317692 KB Output is correct
48 Correct 405 ms 318840 KB Output is correct
49 Correct 196 ms 295288 KB Output is correct
50 Correct 204 ms 295288 KB Output is correct
51 Correct 200 ms 295544 KB Output is correct
52 Correct 200 ms 295288 KB Output is correct
53 Correct 203 ms 295208 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 305528 KB Output is correct
2 Correct 212 ms 303992 KB Output is correct
3 Correct 203 ms 295288 KB Output is correct
4 Correct 201 ms 295288 KB Output is correct
5 Correct 207 ms 300536 KB Output is correct
6 Correct 209 ms 300536 KB Output is correct
7 Correct 209 ms 300408 KB Output is correct
8 Correct 209 ms 300152 KB Output is correct
9 Correct 207 ms 299896 KB Output is correct
10 Correct 203 ms 295288 KB Output is correct
11 Correct 202 ms 295288 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 295356 KB Output is correct
2 Correct 847 ms 369784 KB Output is correct
3 Correct 1661 ms 434936 KB Output is correct
4 Correct 1687 ms 430648 KB Output is correct
5 Correct 1682 ms 430712 KB Output is correct
6 Correct 445 ms 325496 KB Output is correct
7 Correct 693 ms 347768 KB Output is correct
8 Correct 728 ms 351064 KB Output is correct
9 Correct 196 ms 295288 KB Output is correct
10 Correct 204 ms 295288 KB Output is correct
11 Correct 200 ms 295544 KB Output is correct
12 Correct 200 ms 295288 KB Output is correct
13 Correct 203 ms 295208 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 211 ms 295288 KB Output is correct
2 Correct 200 ms 295416 KB Output is correct
3 Correct 199 ms 295416 KB Output is correct
4 Correct 198 ms 295416 KB Output is correct
5 Correct 199 ms 295268 KB Output is correct
6 Correct 203 ms 295544 KB Output is correct
7 Correct 201 ms 295416 KB Output is correct
8 Correct 199 ms 295544 KB Output is correct
9 Correct 197 ms 295460 KB Output is correct
10 Correct 198 ms 295544 KB Output is correct
11 Correct 217 ms 295544 KB Output is correct
12 Correct 204 ms 295544 KB Output is correct
13 Correct 198 ms 295288 KB Output is correct
14 Correct 199 ms 295288 KB Output is correct
15 Correct 199 ms 295288 KB Output is correct
16 Correct 208 ms 295288 KB Output is correct
17 Correct 202 ms 295756 KB Output is correct
18 Correct 199 ms 295800 KB Output is correct
19 Correct 202 ms 295928 KB Output is correct
20 Correct 201 ms 296056 KB Output is correct
21 Correct 201 ms 296184 KB Output is correct
22 Correct 209 ms 296184 KB Output is correct
23 Correct 207 ms 296184 KB Output is correct
24 Correct 202 ms 295800 KB Output is correct
25 Correct 208 ms 297132 KB Output is correct
26 Correct 207 ms 297080 KB Output is correct
27 Correct 208 ms 297080 KB Output is correct
28 Correct 210 ms 297824 KB Output is correct
29 Correct 213 ms 298360 KB Output is correct
30 Correct 214 ms 298616 KB Output is correct
31 Correct 214 ms 298360 KB Output is correct
32 Correct 216 ms 298360 KB Output is correct
33 Correct 274 ms 318944 KB Output is correct
34 Correct 274 ms 318968 KB Output is correct
35 Correct 315 ms 325240 KB Output is correct
36 Correct 306 ms 325112 KB Output is correct
37 Correct 283 ms 310904 KB Output is correct
38 Correct 288 ms 311072 KB Output is correct
39 Correct 290 ms 311416 KB Output is correct
40 Correct 284 ms 310776 KB Output is correct
41 Correct 286 ms 310392 KB Output is correct
42 Correct 322 ms 312188 KB Output is correct
43 Correct 429 ms 318952 KB Output is correct
44 Correct 433 ms 321044 KB Output is correct
45 Correct 308 ms 307960 KB Output is correct
46 Correct 315 ms 311416 KB Output is correct
47 Correct 407 ms 317692 KB Output is correct
48 Correct 405 ms 318840 KB Output is correct
49 Correct 207 ms 305528 KB Output is correct
50 Correct 212 ms 303992 KB Output is correct
51 Correct 203 ms 295288 KB Output is correct
52 Correct 201 ms 295288 KB Output is correct
53 Correct 207 ms 300536 KB Output is correct
54 Correct 209 ms 300536 KB Output is correct
55 Correct 209 ms 300408 KB Output is correct
56 Correct 209 ms 300152 KB Output is correct
57 Correct 207 ms 299896 KB Output is correct
58 Correct 203 ms 295288 KB Output is correct
59 Correct 202 ms 295288 KB Output is correct
60 Correct 203 ms 295356 KB Output is correct
61 Correct 847 ms 369784 KB Output is correct
62 Correct 1661 ms 434936 KB Output is correct
63 Correct 1687 ms 430648 KB Output is correct
64 Correct 1682 ms 430712 KB Output is correct
65 Correct 445 ms 325496 KB Output is correct
66 Correct 693 ms 347768 KB Output is correct
67 Correct 728 ms 351064 KB Output is correct
68 Correct 1260 ms 508548 KB Output is correct
69 Correct 1221 ms 508792 KB Output is correct
70 Correct 2445 ms 589432 KB Output is correct
71 Correct 2374 ms 589548 KB Output is correct
72 Correct 1931 ms 435132 KB Output is correct
73 Correct 2315 ms 452472 KB Output is correct
74 Correct 2456 ms 461820 KB Output is correct
75 Correct 3901 ms 519032 KB Output is correct
76 Correct 2378 ms 454384 KB Output is correct
77 Correct 3101 ms 492280 KB Output is correct
78 Correct 4061 ms 543892 KB Output is correct
79 Correct 2107 ms 426040 KB Output is correct
80 Correct 3694 ms 503244 KB Output is correct
81 Correct 3552 ms 507748 KB Output is correct
82 Correct 1053 ms 382644 KB Output is correct
83 Correct 1864 ms 437580 KB Output is correct
84 Correct 1881 ms 433836 KB Output is correct
85 Correct 1948 ms 433628 KB Output is correct
86 Correct 196 ms 295288 KB Output is correct
87 Correct 204 ms 295288 KB Output is correct
88 Correct 200 ms 295544 KB Output is correct
89 Correct 200 ms 295288 KB Output is correct
90 Correct 203 ms 295208 KB Output is correct