oj.uz

Submission #859968

# Submission time Handle Problem Language Result Execution time Memory
859968 2023-10-11T09:00:39 Z sunwukong123 Rectangles (IOI19_rect) C++14
50 / 100
 5000 ms 964804 KB 
#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = 2505;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi; 
vector<int> vxi[MAXN][MAXN];
vector<pi> vx[MAXN][MAXN];
vector<pi>vy1[MAXN];
vector<pi> vy[MAXN][MAXN];

unordered_set<int> us[MAXN][MAXN];
struct hash_pair {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(pair<uint64_t,uint64_t> x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x.first + FIXED_RANDOM)^(splitmix64(x.second + FIXED_RANDOM) >> 1);
    }
};
int n,m;
long long ans;
struct fenw {
	int fw[MAXN];
	void update(int x, int nval){
		for(;x<MAXN;x+=x&-x)fw[x]+=nval;
	}
	int point(int x){
		int res=0;
		for(;x;x-=x&-x)res+=fw[x];
		return res;
	}
	int query(int x, int y){
		return point(y)-point(x-1);
	}
}fw;

long long count_rectangles(std::vector<std::vector<int> > A) {
	n=A.size();
	m=A[0].size();
	for(int i=1;i<=n;i++){
		vector<pi> E;
		for(int j=1;j<=m;j++){
			E.push_back({A[i-1][j-1],j});
		}
		sort(E.begin(),E.end(),greater<pi>());
		
		set<int> s;
		vector<int> lazy;
		int pre=-1;
		set<pi> st;
		for(auto x:E){
			if(x.first!=pre){
				for(auto y:lazy){
					s.insert(y);
				}
				lazy.clear();
			}
			//debug(x.first,x.second);
			auto it=s.lower_bound(x.second);
			if(it == s.begin() || it==s.end());
			else {
				int L=*prev(it);
				int R=*it;
				st.insert({L,R});
				
			}
			lazy.push_back(x.second);
			pre=x.first;
		}
		for(auto x:st){
			int L=x.first;
			int R=x.second;
			vy1[i].push_back({L,R});
			us[L][R].insert(i);
		}
	}

	for(int i=1;i<=n;i++){
		vy1[i].resize(unique(vy1[i].begin(),vy1[i].end())-vy1[i].begin());
	}
	for(int i=1;i<=m;i++){
		vector<pi> E;
		for(int j=1;j<=n;j++){
			E.push_back({A[j-1][i-1],j});
		}
		sort(E.begin(),E.end(),greater<pi>());
		set<int> s;
		vector<int> lazy;
		int pre=-1;
		set<pi> st;
		for(auto x:E){
			if(x.first!=pre){
				for(auto y:lazy){
					s.insert(y);
				}
				lazy.clear();
			}
			//debug(x.first,x.second);
			auto it=s.lower_bound(x.second);
			if(it == s.begin() || it==s.end());
			else {
				int L=*prev(it);
				int R=*it;
				//vxi[L][R].push_back(i);
				st.insert({L,R});
			}
			lazy.push_back(x.second);
			pre=x.first;
		}
		for(auto x:st){
			vxi[x.first][x.second].push_back(i);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=i;j<=n;j++){
			int st=0;
			for(int k=0;k<(int)vxi[i][j].size();k++){
				if(k==((int)vxi[i][j].size()-1) || vxi[i][j][k]+1!=vxi[i][j][k+1]){
					vx[i][j].push_back({vxi[i][j][st],vxi[i][j][k]});
					st=k+1;
				}
			}
		}
	}
	for(int i=1;i<=n;i++){

		unordered_set<pi,hash_pair> vy;
		for(auto x:vy1[i+1]){
			vy.insert(x);
		}
		for(int j=i+2;j<=n;j++){
			//sort(vx[i][j].begin(),vx[i][j].end());
			vector<array<int,3>> events;
			for(auto x:vx[i][j]){
				events.push_back({x.second,1,x.first});
			}
			for(auto x:vy){
				events.push_back({x.second-1,-1,x.first+1});
			}
			sort(events.begin(),events.end());
			vector<pi> reset;
			for(auto e:events){
				if(e[1] == -1){
					fw.update(e[2],1);
					reset.push_back({e[2],-1});
				} else{
					ans+=fw.query(e[2],e[0]);
				}
			}
			for(auto x:reset)fw.update(x.first,x.second);
			vector<pi> toerase;
			for(auto x:vy){
				if(us[x.first][x.second].find(j) == us[x.first][x.second].end())toerase.push_back(x);
			}
			for(auto x:toerase){
				vy.erase(x);
			
			}
			
		}

	}

	return ans;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 786256 KB Output is correct
2 Correct 183 ms 786484 KB Output is correct
3 Correct 193 ms 786260 KB Output is correct
4 Correct 173 ms 786348 KB Output is correct
5 Correct 172 ms 786592 KB Output is correct
6 Correct 175 ms 786448 KB Output is correct
7 Correct 171 ms 786468 KB Output is correct
8 Correct 172 ms 786684 KB Output is correct
9 Correct 171 ms 786452 KB Output is correct
10 Correct 167 ms 786252 KB Output is correct
11 Correct 173 ms 786256 KB Output is correct
12 Correct 166 ms 786380 KB Output is correct
13 Correct 166 ms 786260 KB Output is correct
14 Correct 169 ms 786360 KB Output is correct
15 Correct 167 ms 786352 KB Output is correct
16 Correct 170 ms 786260 KB Output is correct
17 Correct 178 ms 786352 KB Output is correct
18 Correct 173 ms 786380 KB Output is correct
19 Correct 170 ms 786260 KB Output is correct
20 Correct 185 ms 786312 KB Output is correct
21 Correct 174 ms 786280 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 786256 KB Output is correct
2 Correct 183 ms 786484 KB Output is correct
3 Correct 193 ms 786260 KB Output is correct
4 Correct 173 ms 786348 KB Output is correct
5 Correct 172 ms 786592 KB Output is correct
6 Correct 175 ms 786448 KB Output is correct
7 Correct 171 ms 786468 KB Output is correct
8 Correct 172 ms 786684 KB Output is correct
9 Correct 171 ms 786452 KB Output is correct
10 Correct 167 ms 786252 KB Output is correct
11 Correct 173 ms 786256 KB Output is correct
12 Correct 166 ms 786380 KB Output is correct
13 Correct 166 ms 786260 KB Output is correct
14 Correct 169 ms 786360 KB Output is correct
15 Correct 167 ms 786352 KB Output is correct
16 Correct 170 ms 786260 KB Output is correct
17 Correct 178 ms 786352 KB Output is correct
18 Correct 173 ms 786380 KB Output is correct
19 Correct 170 ms 786260 KB Output is correct
20 Correct 185 ms 786312 KB Output is correct
21 Correct 174 ms 786280 KB Output is correct
22 Correct 184 ms 786768 KB Output is correct
23 Correct 186 ms 786916 KB Output is correct
24 Correct 186 ms 786708 KB Output is correct
25 Correct 181 ms 786548 KB Output is correct
26 Correct 177 ms 786768 KB Output is correct
27 Correct 181 ms 786968 KB Output is correct
28 Correct 176 ms 786772 KB Output is correct
29 Correct 173 ms 786404 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 786256 KB Output is correct
2 Correct 183 ms 786484 KB Output is correct
3 Correct 193 ms 786260 KB Output is correct
4 Correct 173 ms 786348 KB Output is correct
5 Correct 172 ms 786592 KB Output is correct
6 Correct 175 ms 786448 KB Output is correct
7 Correct 171 ms 786468 KB Output is correct
8 Correct 172 ms 786684 KB Output is correct
9 Correct 171 ms 786452 KB Output is correct
10 Correct 167 ms 786252 KB Output is correct
11 Correct 173 ms 786256 KB Output is correct
12 Correct 166 ms 786380 KB Output is correct
13 Correct 166 ms 786260 KB Output is correct
14 Correct 169 ms 786360 KB Output is correct
15 Correct 167 ms 786352 KB Output is correct
16 Correct 170 ms 786260 KB Output is correct
17 Correct 184 ms 786768 KB Output is correct
18 Correct 186 ms 786916 KB Output is correct
19 Correct 186 ms 786708 KB Output is correct
20 Correct 181 ms 786548 KB Output is correct
21 Correct 177 ms 786768 KB Output is correct
22 Correct 181 ms 786968 KB Output is correct
23 Correct 176 ms 786772 KB Output is correct
24 Correct 173 ms 786404 KB Output is correct
25 Correct 178 ms 786352 KB Output is correct
26 Correct 173 ms 786380 KB Output is correct
27 Correct 170 ms 786260 KB Output is correct
28 Correct 185 ms 786312 KB Output is correct
29 Correct 174 ms 786280 KB Output is correct
30 Correct 454 ms 789328 KB Output is correct
31 Correct 462 ms 789076 KB Output is correct
32 Correct 448 ms 789332 KB Output is correct
33 Correct 190 ms 788052 KB Output is correct
34 Correct 220 ms 790180 KB Output is correct
35 Correct 213 ms 790100 KB Output is correct
36 Correct 218 ms 789712 KB Output is correct
37 Correct 228 ms 789776 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 786256 KB Output is correct
2 Correct 183 ms 786484 KB Output is correct
3 Correct 193 ms 786260 KB Output is correct
4 Correct 173 ms 786348 KB Output is correct
5 Correct 172 ms 786592 KB Output is correct
6 Correct 175 ms 786448 KB Output is correct
7 Correct 171 ms 786468 KB Output is correct
8 Correct 172 ms 786684 KB Output is correct
9 Correct 171 ms 786452 KB Output is correct
10 Correct 167 ms 786252 KB Output is correct
11 Correct 173 ms 786256 KB Output is correct
12 Correct 166 ms 786380 KB Output is correct
13 Correct 166 ms 786260 KB Output is correct
14 Correct 169 ms 786360 KB Output is correct
15 Correct 167 ms 786352 KB Output is correct
16 Correct 170 ms 786260 KB Output is correct
17 Correct 184 ms 786768 KB Output is correct
18 Correct 186 ms 786916 KB Output is correct
19 Correct 186 ms 786708 KB Output is correct
20 Correct 181 ms 786548 KB Output is correct
21 Correct 177 ms 786768 KB Output is correct
22 Correct 181 ms 786968 KB Output is correct
23 Correct 176 ms 786772 KB Output is correct
24 Correct 173 ms 786404 KB Output is correct
25 Correct 454 ms 789328 KB Output is correct
26 Correct 462 ms 789076 KB Output is correct
27 Correct 448 ms 789332 KB Output is correct
28 Correct 190 ms 788052 KB Output is correct
29 Correct 220 ms 790180 KB Output is correct
30 Correct 213 ms 790100 KB Output is correct
31 Correct 218 ms 789712 KB Output is correct
32 Correct 228 ms 789776 KB Output is correct
33 Correct 178 ms 786352 KB Output is correct
34 Correct 173 ms 786380 KB Output is correct
35 Correct 170 ms 786260 KB Output is correct
36 Correct 185 ms 786312 KB Output is correct
37 Correct 174 ms 786280 KB Output is correct
38 Correct 525 ms 845828 KB Output is correct
39 Correct 498 ms 846052 KB Output is correct
40 Correct 522 ms 845908 KB Output is correct
41 Correct 484 ms 845904 KB Output is correct
42 Execution timed out 5089 ms 823352 KB Time limit exceeded
43 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 176 ms 787280 KB Output is correct
2 Correct 175 ms 787140 KB Output is correct
3 Correct 174 ms 786512 KB Output is correct
4 Correct 178 ms 786260 KB Output is correct
5 Correct 176 ms 787796 KB Output is correct
6 Correct 172 ms 787792 KB Output is correct
7 Correct 191 ms 787820 KB Output is correct
8 Correct 174 ms 787484 KB Output is correct
9 Correct 178 ms 787536 KB Output is correct
10 Correct 170 ms 787028 KB Output is correct
11 Correct 175 ms 787424 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 786352 KB Output is correct
2 Correct 173 ms 786380 KB Output is correct
3 Correct 170 ms 786260 KB Output is correct
4 Correct 185 ms 786312 KB Output is correct
5 Correct 174 ms 786280 KB Output is correct
6 Correct 174 ms 786168 KB Output is correct
7 Correct 1670 ms 869488 KB Output is correct
8 Correct 4022 ms 961500 KB Output is correct
9 Correct 3978 ms 964804 KB Output is correct
10 Correct 4054 ms 961048 KB Output is correct
11 Correct 356 ms 816860 KB Output is correct
12 Correct 565 ms 843964 KB Output is correct
13 Correct 534 ms 847588 KB Output is correct

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 186 ms 786256 KB Output is correct
2 Correct 183 ms 786484 KB Output is correct
3 Correct 193 ms 786260 KB Output is correct
4 Correct 173 ms 786348 KB Output is correct
5 Correct 172 ms 786592 KB Output is correct
6 Correct 175 ms 786448 KB Output is correct
7 Correct 171 ms 786468 KB Output is correct
8 Correct 172 ms 786684 KB Output is correct
9 Correct 171 ms 786452 KB Output is correct
10 Correct 167 ms 786252 KB Output is correct
11 Correct 173 ms 786256 KB Output is correct
12 Correct 166 ms 786380 KB Output is correct
13 Correct 166 ms 786260 KB Output is correct
14 Correct 169 ms 786360 KB Output is correct
15 Correct 167 ms 786352 KB Output is correct
16 Correct 170 ms 786260 KB Output is correct
17 Correct 184 ms 786768 KB Output is correct
18 Correct 186 ms 786916 KB Output is correct
19 Correct 186 ms 786708 KB Output is correct
20 Correct 181 ms 786548 KB Output is correct
21 Correct 177 ms 786768 KB Output is correct
22 Correct 181 ms 786968 KB Output is correct
23 Correct 176 ms 786772 KB Output is correct
24 Correct 173 ms 786404 KB Output is correct
25 Correct 454 ms 789328 KB Output is correct
26 Correct 462 ms 789076 KB Output is correct
27 Correct 448 ms 789332 KB Output is correct
28 Correct 190 ms 788052 KB Output is correct
29 Correct 220 ms 790180 KB Output is correct
30 Correct 213 ms 790100 KB Output is correct
31 Correct 218 ms 789712 KB Output is correct
32 Correct 228 ms 789776 KB Output is correct
33 Correct 525 ms 845828 KB Output is correct
34 Correct 498 ms 846052 KB Output is correct
35 Correct 522 ms 845908 KB Output is correct
36 Correct 484 ms 845904 KB Output is correct
37 Execution timed out 5089 ms 823352 KB Time limit exceeded
38 Halted 0 ms 0 KB -