oj.uz

Submission #597693

# Submission time Handle Problem Language Result Execution time Memory
597693 2022-07-16T14:52:29 Z FatihSolak Rectangles (IOI19_rect) C++17
72 / 100
 5000 ms 614984 KB 
#include "rect.h"
#include <bits/stdc++.h>
#define N 2505
using namespace std;
struct BIT{
	vector<int> bit;
	int n;
	int tot = 0;
	BIT(int size){
		n = size + 5;
		bit.assign(n+5,0);
	}
	void upd(int pos,int val){
		tot += val;
		for(++pos;pos<n;pos += pos & -pos){
			bit[pos] += val;
		}
	}
	int get(int pos){
		int ret = 0;
		for(++pos;pos > 0;pos -= pos & -pos){
			ret += bit[pos];
		}
		return ret;
	}
	int get(int l,int r){
		return tot - get(l-1);
	}
};
struct SegTree{
	vector<BIT> t;
	int n;
	SegTree(int size){
		n = size + 5;
		t.assign(4*n,BIT(n));
	}
	void upd(int v,int tl,int tr,int l,int r,int val){
		//cout << val << endl;
		t[v].upd(r,val);
		if(tl == tr)return;
		int tm = (tl + tr)/2;
		if(l <= tm){
			upd(v*2,tl,tm,l,r,val);
		}
		else upd(v*2+1,tm+1,tr,l,r,val);
	}
	int get(int v,int tl,int tr,int l,int r){
		if(tr <= l){
			return t[v].get(r,n-1);
		}
		if(tl > l){
			return 0;
		}
		int tm = (tl + tr)/2;
		return get(v*2,tl,tm,l,r) + get(v*2+1,tm+1,tr,l,r);
	}
	void upd(int l,int r,int val){
		upd(1,0,n-1,l,r,val);
	}
	int get(int l,int r){
		return get(1,0,n-1,l,r);
	}
};
int mp[N][N];
int st[N];
vector<int> pos[N];
vector<int> prepos[N];
vector<pair<int,int>> ranges[N][N];
vector<pair<int,int>> queries[N][N];
long long count_rectangles(vector<vector<int>> a){
	auto beg = clock();
	int n = a.size();
	int m = a[0].size();
	//cout << n << " " << m << endl;
	if(n < 3 || m < 3){
		return 0;
	}
	int stsz = 0;
	for(int i = m-1;i>=0;i--){
		stsz = 0;
		for(int j = 0;j<n;j++){
			while(stsz && a[j][i] > a[st[stsz-1]][i])
				stsz--;
			if(stsz && st[stsz-1] != j-1 && a[st[stsz-1]][i] != a[j][i]){
				pos[st[stsz-1]].push_back(j);
			}
			st[stsz++] = j;
		}
		stsz = 0;
		for(int j = n-1;j>=0;j--){
			while(stsz && a[j][i] > a[st[stsz-1]][i])
				stsz--;
			if(stsz && st[stsz-1] != j+1){
				pos[j].push_back(st[stsz-1]);
			}
			st[stsz++] = j;
		}
		for(int j = 0;j<n;j++){
			for(auto u:prepos[j]){
				mp[j][u] = -mp[j][u];
			}
		}
		for(int j = 0;j<n;j++){
			for(auto u:pos[j]){
				mp[j][u] = 1 - mp[j][u];
				if(i)
					queries[i-1][mp[j][u]+1].push_back({j+1,u-1});
				//cout << i << " " << mp[j][u] << " " << j << " " << u << endl;
			}
		}
		for(int j = 0;j<n;j++){
			for(auto u:prepos[j]){
				if(mp[j][u] < 0)
					mp[j][u] = 0;
			}
			swap(prepos[j],pos[j]);
			pos[j].clear();
		}
	}
	for(int i = 0;i<N;i++){
		pos[i].clear();
		prepos[i].clear();
		for(int j = 0;j<N;j++){
			mp[i][j] = 0;
		}
	}
	for(int i = n-1;i>=0;i--){
		stsz = 0;
		for(int j = 0;j<m;j++){
			while(stsz && a[i][j] > a[i][st[stsz-1]])
				stsz--;
			if(stsz && st[stsz-1] != j-1 && a[i][j] != a[i][st[stsz-1]]){
				pos[st[stsz-1]].push_back(j);
			}
			st[stsz++] = j;
		}
		stsz = 0;
		for(int j = m-1;j>=0;j--){
			while(stsz && a[i][j] > a[i][st[stsz-1]])
				stsz--;
			if(stsz && st[stsz-1] != j+1){
				pos[j].push_back(st[stsz-1]);
			}
			st[stsz++] = j;
		}
		for(int j = 0;j<m;j++){
			for(auto u:prepos[j]){
				mp[j][u] = -mp[j][u];
			}
		}
		for(int j = 0;j<m;j++){
			for(auto u:pos[j]){
				mp[j][u] = 1 - mp[j][u];
			}
		}
		for(int j = 0;j<m;j++){
			for(auto u:prepos[j]){
				if(mp[j][u] < 0){
					//cout << j << " " << u << " " << i + 1 << " " << i - mp[j][u] << endl;
					ranges[j][u-j].push_back({i+1,i - mp[j][u]});
					mp[j][u] = 0;
				}
			}
			swap(prepos[j],pos[j]);
			pos[j].clear();
		}
	}
	for(int j = 0;j<m;j++){
		for(auto u:prepos[j]){
			if(mp[j][u] > 0){
				//cout << j << " " << u << " " << -1 + 1 << " " << -1 + mp[j][u] << endl;
				ranges[j][u-j].push_back({-1+1,-1 + mp[j][u]});
				mp[j][u] = 0;
			}
		}
	}
	SegTree tree(n);
	long long ans = 0;
	for(int i = 0;i<m;i++){
		for(int j = 0;j<=m+1;j++){
			for(auto u:ranges[i][j])
				tree.upd(u.first,u.second,1);
			
			for(auto u:queries[i][j])
				ans += tree.get(u.first,u.second);
			
		}
		for(int j = 0;j<=m+1;j++)
			for(auto u:ranges[i][j])
				tree.upd(u.first,u.second,-1);
	}
	return ans;
}

Compilation message

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:71:7: warning: unused variable 'beg' [-Wunused-variable]
   71 |  auto beg = clock();
      |       ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 319564 KB Output is correct
2 Correct 140 ms 319660 KB Output is correct
3 Correct 138 ms 319856 KB Output is correct
4 Correct 142 ms 319616 KB Output is correct
5 Correct 137 ms 319644 KB Output is correct
6 Correct 144 ms 319684 KB Output is correct
7 Correct 155 ms 319652 KB Output is correct
8 Correct 154 ms 319640 KB Output is correct
9 Correct 140 ms 319668 KB Output is correct
10 Correct 148 ms 319672 KB Output is correct
11 Correct 143 ms 319704 KB Output is correct
12 Correct 162 ms 319676 KB Output is correct
13 Correct 133 ms 295116 KB Output is correct
14 Correct 131 ms 295016 KB Output is correct
15 Correct 145 ms 319652 KB Output is correct
16 Correct 146 ms 319712 KB Output is correct
17 Correct 133 ms 295184 KB Output is correct
18 Correct 138 ms 295120 KB Output is correct
19 Correct 156 ms 319724 KB Output is correct
20 Correct 142 ms 319628 KB Output is correct
21 Correct 131 ms 295040 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 319564 KB Output is correct
2 Correct 140 ms 319660 KB Output is correct
3 Correct 138 ms 319856 KB Output is correct
4 Correct 142 ms 319616 KB Output is correct
5 Correct 137 ms 319644 KB Output is correct
6 Correct 144 ms 319684 KB Output is correct
7 Correct 155 ms 319652 KB Output is correct
8 Correct 154 ms 319640 KB Output is correct
9 Correct 140 ms 319668 KB Output is correct
10 Correct 148 ms 319672 KB Output is correct
11 Correct 143 ms 319704 KB Output is correct
12 Correct 162 ms 319676 KB Output is correct
13 Correct 133 ms 295116 KB Output is correct
14 Correct 131 ms 295016 KB Output is correct
15 Correct 145 ms 319652 KB Output is correct
16 Correct 146 ms 319712 KB Output is correct
17 Correct 133 ms 295184 KB Output is correct
18 Correct 138 ms 295120 KB Output is correct
19 Correct 156 ms 319724 KB Output is correct
20 Correct 142 ms 319628 KB Output is correct
21 Correct 131 ms 295040 KB Output is correct
22 Correct 151 ms 319972 KB Output is correct
23 Correct 143 ms 320000 KB Output is correct
24 Correct 141 ms 319956 KB Output is correct
25 Correct 140 ms 319860 KB Output is correct
26 Correct 159 ms 319912 KB Output is correct
27 Correct 145 ms 319948 KB Output is correct
28 Correct 144 ms 319968 KB Output is correct
29 Correct 141 ms 319864 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 319564 KB Output is correct
2 Correct 140 ms 319660 KB Output is correct
3 Correct 138 ms 319856 KB Output is correct
4 Correct 142 ms 319616 KB Output is correct
5 Correct 137 ms 319644 KB Output is correct
6 Correct 144 ms 319684 KB Output is correct
7 Correct 155 ms 319652 KB Output is correct
8 Correct 154 ms 319640 KB Output is correct
9 Correct 140 ms 319668 KB Output is correct
10 Correct 148 ms 319672 KB Output is correct
11 Correct 143 ms 319704 KB Output is correct
12 Correct 162 ms 319676 KB Output is correct
13 Correct 133 ms 295116 KB Output is correct
14 Correct 131 ms 295016 KB Output is correct
15 Correct 145 ms 319652 KB Output is correct
16 Correct 146 ms 319712 KB Output is correct
17 Correct 151 ms 319972 KB Output is correct
18 Correct 143 ms 320000 KB Output is correct
19 Correct 141 ms 319956 KB Output is correct
20 Correct 140 ms 319860 KB Output is correct
21 Correct 159 ms 319912 KB Output is correct
22 Correct 145 ms 319948 KB Output is correct
23 Correct 144 ms 319968 KB Output is correct
24 Correct 141 ms 319864 KB Output is correct
25 Correct 133 ms 295184 KB Output is correct
26 Correct 138 ms 295120 KB Output is correct
27 Correct 156 ms 319724 KB Output is correct
28 Correct 142 ms 319628 KB Output is correct
29 Correct 131 ms 295040 KB Output is correct
30 Correct 154 ms 321192 KB Output is correct
31 Correct 169 ms 321228 KB Output is correct
32 Correct 145 ms 321240 KB Output is correct
33 Correct 149 ms 321140 KB Output is correct
34 Correct 157 ms 321696 KB Output is correct
35 Correct 159 ms 321736 KB Output is correct
36 Correct 190 ms 321624 KB Output is correct
37 Correct 163 ms 321588 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 319564 KB Output is correct
2 Correct 140 ms 319660 KB Output is correct
3 Correct 138 ms 319856 KB Output is correct
4 Correct 142 ms 319616 KB Output is correct
5 Correct 137 ms 319644 KB Output is correct
6 Correct 144 ms 319684 KB Output is correct
7 Correct 155 ms 319652 KB Output is correct
8 Correct 154 ms 319640 KB Output is correct
9 Correct 140 ms 319668 KB Output is correct
10 Correct 148 ms 319672 KB Output is correct
11 Correct 143 ms 319704 KB Output is correct
12 Correct 162 ms 319676 KB Output is correct
13 Correct 133 ms 295116 KB Output is correct
14 Correct 131 ms 295016 KB Output is correct
15 Correct 145 ms 319652 KB Output is correct
16 Correct 146 ms 319712 KB Output is correct
17 Correct 151 ms 319972 KB Output is correct
18 Correct 143 ms 320000 KB Output is correct
19 Correct 141 ms 319956 KB Output is correct
20 Correct 140 ms 319860 KB Output is correct
21 Correct 159 ms 319912 KB Output is correct
22 Correct 145 ms 319948 KB Output is correct
23 Correct 144 ms 319968 KB Output is correct
24 Correct 141 ms 319864 KB Output is correct
25 Correct 154 ms 321192 KB Output is correct
26 Correct 169 ms 321228 KB Output is correct
27 Correct 145 ms 321240 KB Output is correct
28 Correct 149 ms 321140 KB Output is correct
29 Correct 157 ms 321696 KB Output is correct
30 Correct 159 ms 321736 KB Output is correct
31 Correct 190 ms 321624 KB Output is correct
32 Correct 163 ms 321588 KB Output is correct
33 Correct 133 ms 295184 KB Output is correct
34 Correct 138 ms 295120 KB Output is correct
35 Correct 156 ms 319724 KB Output is correct
36 Correct 142 ms 319628 KB Output is correct
37 Correct 131 ms 295040 KB Output is correct
38 Correct 296 ms 342520 KB Output is correct
39 Correct 243 ms 343924 KB Output is correct
40 Correct 282 ms 343828 KB Output is correct
41 Correct 241 ms 343760 KB Output is correct
42 Correct 231 ms 337456 KB Output is correct
43 Correct 217 ms 337484 KB Output is correct
44 Correct 227 ms 337460 KB Output is correct
45 Correct 228 ms 336176 KB Output is correct
46 Correct 239 ms 334892 KB Output is correct
47 Correct 289 ms 335468 KB Output is correct
48 Correct 417 ms 343592 KB Output is correct
49 Correct 413 ms 343804 KB Output is correct
50 Correct 280 ms 335816 KB Output is correct
51 Correct 267 ms 330112 KB Output is correct
52 Correct 364 ms 340456 KB Output is correct
53 Correct 401 ms 340524 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 167 ms 320000 KB Output is correct
2 Correct 158 ms 319984 KB Output is correct
3 Correct 168 ms 319720 KB Output is correct
4 Correct 131 ms 295120 KB Output is correct
5 Correct 174 ms 320128 KB Output is correct
6 Correct 170 ms 320128 KB Output is correct
7 Correct 171 ms 320024 KB Output is correct
8 Correct 165 ms 320184 KB Output is correct
9 Correct 168 ms 320060 KB Output is correct
10 Correct 138 ms 295108 KB Output is correct
11 Correct 153 ms 295140 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 295184 KB Output is correct
2 Correct 138 ms 295120 KB Output is correct
3 Correct 156 ms 319724 KB Output is correct
4 Correct 142 ms 319628 KB Output is correct
5 Correct 131 ms 295040 KB Output is correct
6 Correct 141 ms 319564 KB Output is correct
7 Correct 815 ms 386840 KB Output is correct
8 Correct 1970 ms 509868 KB Output is correct
9 Correct 1778 ms 511404 KB Output is correct
10 Correct 2104 ms 511424 KB Output is correct
11 Correct 296 ms 369084 KB Output is correct
12 Correct 445 ms 465416 KB Output is correct
13 Correct 497 ms 468404 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 165 ms 319564 KB Output is correct
2 Correct 140 ms 319660 KB Output is correct
3 Correct 138 ms 319856 KB Output is correct
4 Correct 142 ms 319616 KB Output is correct
5 Correct 137 ms 319644 KB Output is correct
6 Correct 144 ms 319684 KB Output is correct
7 Correct 155 ms 319652 KB Output is correct
8 Correct 154 ms 319640 KB Output is correct
9 Correct 140 ms 319668 KB Output is correct
10 Correct 148 ms 319672 KB Output is correct
11 Correct 143 ms 319704 KB Output is correct
12 Correct 162 ms 319676 KB Output is correct
13 Correct 133 ms 295116 KB Output is correct
14 Correct 131 ms 295016 KB Output is correct
15 Correct 145 ms 319652 KB Output is correct
16 Correct 146 ms 319712 KB Output is correct
17 Correct 151 ms 319972 KB Output is correct
18 Correct 143 ms 320000 KB Output is correct
19 Correct 141 ms 319956 KB Output is correct
20 Correct 140 ms 319860 KB Output is correct
21 Correct 159 ms 319912 KB Output is correct
22 Correct 145 ms 319948 KB Output is correct
23 Correct 144 ms 319968 KB Output is correct
24 Correct 141 ms 319864 KB Output is correct
25 Correct 154 ms 321192 KB Output is correct
26 Correct 169 ms 321228 KB Output is correct
27 Correct 145 ms 321240 KB Output is correct
28 Correct 149 ms 321140 KB Output is correct
29 Correct 157 ms 321696 KB Output is correct
30 Correct 159 ms 321736 KB Output is correct
31 Correct 190 ms 321624 KB Output is correct
32 Correct 163 ms 321588 KB Output is correct
33 Correct 296 ms 342520 KB Output is correct
34 Correct 243 ms 343924 KB Output is correct
35 Correct 282 ms 343828 KB Output is correct
36 Correct 241 ms 343760 KB Output is correct
37 Correct 231 ms 337456 KB Output is correct
38 Correct 217 ms 337484 KB Output is correct
39 Correct 227 ms 337460 KB Output is correct
40 Correct 228 ms 336176 KB Output is correct
41 Correct 239 ms 334892 KB Output is correct
42 Correct 289 ms 335468 KB Output is correct
43 Correct 417 ms 343592 KB Output is correct
44 Correct 413 ms 343804 KB Output is correct
45 Correct 280 ms 335816 KB Output is correct
46 Correct 267 ms 330112 KB Output is correct
47 Correct 364 ms 340456 KB Output is correct
48 Correct 401 ms 340524 KB Output is correct
49 Correct 167 ms 320000 KB Output is correct
50 Correct 158 ms 319984 KB Output is correct
51 Correct 168 ms 319720 KB Output is correct
52 Correct 131 ms 295120 KB Output is correct
53 Correct 174 ms 320128 KB Output is correct
54 Correct 170 ms 320128 KB Output is correct
55 Correct 171 ms 320024 KB Output is correct
56 Correct 165 ms 320184 KB Output is correct
57 Correct 168 ms 320060 KB Output is correct
58 Correct 138 ms 295108 KB Output is correct
59 Correct 153 ms 295140 KB Output is correct
60 Correct 141 ms 319564 KB Output is correct
61 Correct 815 ms 386840 KB Output is correct
62 Correct 1970 ms 509868 KB Output is correct
63 Correct 1778 ms 511404 KB Output is correct
64 Correct 2104 ms 511424 KB Output is correct
65 Correct 296 ms 369084 KB Output is correct
66 Correct 445 ms 465416 KB Output is correct
67 Correct 497 ms 468404 KB Output is correct
68 Correct 133 ms 295184 KB Output is correct
69 Correct 138 ms 295120 KB Output is correct
70 Correct 156 ms 319724 KB Output is correct
71 Correct 142 ms 319628 KB Output is correct
72 Correct 131 ms 295040 KB Output is correct
73 Correct 2742 ms 596808 KB Output is correct
74 Correct 1791 ms 613576 KB Output is correct
75 Correct 2937 ms 614984 KB Output is correct
76 Correct 1680 ms 614904 KB Output is correct
77 Correct 1667 ms 527344 KB Output is correct
78 Correct 2701 ms 465052 KB Output is correct
79 Correct 3285 ms 533196 KB Output is correct
80 Execution timed out 5092 ms 594620 KB Time limit exceeded
81 Halted 0 ms 0 KB -