oj.uz

Submission #859941

# Submission time Handle Problem Language Result Execution time Memory
859941 2023-10-11T08:35:58 Z sunwukong123 Rectangles (IOI19_rect) C++14
10 / 100
 1690 ms 882024 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];
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});
				//debug(i,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;
		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;
				//debug(i,L,R);
				vxi[L][R].push_back(i);
			}
			lazy.push_back(x.second);
			pre=x.first;
		}
	}
	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++){

		set<pi> vy;
		for(auto x:vy1[i+1]){
			vy.insert(x);
		}
		for(int j=i+2;j<=n;j++){
			//debug(i,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){
				//debug(e[0],e[2],e[1]);
				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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 786256 KB Output is correct
2 Correct 187 ms 786256 KB Output is correct
3 Correct 187 ms 786388 KB Output is correct
4 Correct 182 ms 786308 KB Output is correct
5 Correct 179 ms 786256 KB Output is correct
6 Correct 177 ms 786304 KB Output is correct
7 Correct 175 ms 786388 KB Output is correct
8 Correct 181 ms 786312 KB Output is correct
9 Incorrect 168 ms 786260 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 786256 KB Output is correct
2 Correct 187 ms 786256 KB Output is correct
3 Correct 187 ms 786388 KB Output is correct
4 Correct 182 ms 786308 KB Output is correct
5 Correct 179 ms 786256 KB Output is correct
6 Correct 177 ms 786304 KB Output is correct
7 Correct 175 ms 786388 KB Output is correct
8 Correct 181 ms 786312 KB Output is correct
9 Incorrect 168 ms 786260 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 786256 KB Output is correct
2 Correct 187 ms 786256 KB Output is correct
3 Correct 187 ms 786388 KB Output is correct
4 Correct 182 ms 786308 KB Output is correct
5 Correct 179 ms 786256 KB Output is correct
6 Correct 177 ms 786304 KB Output is correct
7 Correct 175 ms 786388 KB Output is correct
8 Correct 181 ms 786312 KB Output is correct
9 Incorrect 168 ms 786260 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 786256 KB Output is correct
2 Correct 187 ms 786256 KB Output is correct
3 Correct 187 ms 786388 KB Output is correct
4 Correct 182 ms 786308 KB Output is correct
5 Correct 179 ms 786256 KB Output is correct
6 Correct 177 ms 786304 KB Output is correct
7 Correct 175 ms 786388 KB Output is correct
8 Correct 181 ms 786312 KB Output is correct
9 Incorrect 168 ms 786260 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 787280 KB Output is correct
2 Correct 177 ms 787028 KB Output is correct
3 Correct 168 ms 786512 KB Output is correct
4 Correct 172 ms 786328 KB Output is correct
5 Correct 184 ms 787584 KB Output is correct
6 Correct 178 ms 787792 KB Output is correct
7 Correct 185 ms 787604 KB Output is correct
8 Correct 178 ms 787620 KB Output is correct
9 Correct 175 ms 787536 KB Output is correct
10 Correct 177 ms 786932 KB Output is correct
11 Correct 173 ms 787280 KB Output is correct

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 178 ms 786196 KB Output is correct
2 Incorrect 1690 ms 882024 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 193 ms 786256 KB Output is correct
2 Correct 187 ms 786256 KB Output is correct
3 Correct 187 ms 786388 KB Output is correct
4 Correct 182 ms 786308 KB Output is correct
5 Correct 179 ms 786256 KB Output is correct
6 Correct 177 ms 786304 KB Output is correct
7 Correct 175 ms 786388 KB Output is correct
8 Correct 181 ms 786312 KB Output is correct
9 Incorrect 168 ms 786260 KB Output isn't correct
10 Halted 0 ms 0 KB -