제출 #293290

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
293290		rqi	Rectangles (IOI19_rect)	C++14	59 / 100	5118 ms	441892 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

template<class K,class V> using ht = gp_hash_table<
    K,
    null_type,
    hash<K>,
    equal_to<K>,
    direct_mask_range_hashing<>,
    linear_probe_fn<>,
    hash_standard_resize_policy<
      hash_exponential_size_policy<>,
      hash_load_check_resize_trigger<>,
      true
    >
>;

 
typedef long long ll;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef vector<pi> vpi;
 
const int MOD = 1000000007;
 
#define ins insert
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define all(x) begin(x), end(x)
 
const int mx = 2505;
int n, m;
 
ht<int, null_type> ints2[mx];
 
vpi queries[mx][mx];
vpi updates[mx][mx];
 
set<pair<pi, pi>> rang; //l, r, leftval, rightval (outside range)
 
vpi getInts(vi a){
	// cout << "Q: ";
	// for(auto u: a) cout << u << " ";
	// cout << "\n";
 
	vpi res;
	
	rang.clear();
	rang.ins(mp(mp(0, sz(a)-1), mp(MOD, MOD)));
	vpi vals;
	for(int i = 0; i < sz(a); i++){
		vals.pb(mp(a[i], i));
	}
	sort(vals.rbegin(), vals.rend());
	for(int i = 0; i < sz(vals); i++){
		pair<pi, pi> b = *(prev(rang.lb(mp(mp(vals[i].s, MOD), mp(0, 0)))));
		//cout << i << "\n";
		assert(b.f.f <= vals[i].s && vals[i].s <= b.f.s);
		rang.erase(b);
		//if vals[i] is the max in range & if not on boundary
		if(vals[i].f < min(b.s.f, b.s.s) && 1 <= b.f.f && b.f.s <= sz(a)-2){
			res.pb(b.f);
		}
		//only divide if range added
		if(b.f.f <= vals[i].s-1){
			rang.ins(mp(mp(b.f.f, vals[i].s-1), mp(b.s.f, vals[i].f)));
		}
		if(vals[i].s+1 <= b.f.s){
			rang.ins(mp(mp(vals[i].s+1, b.f.s), mp(vals[i].f, b.s.s)));
		}
	}
 
	// cout << "R: ";
	// for(auto u: res) cout << "(" << u.f << " " << u.s << "), ";
	// cout << "\n";
	return res;
}
 
int val[mx];
vi curin;
 
void upd(int a, int v){
	if(v == 1) curin.pb(a);
	for(; a < mx; a+=a&-a) val[a]+=v;
}
 
int sum(int a){
	int res = 0;
	for(; a > 0; a-=a&-a) res+=val[a];
	return res;
}
 
int query(int a, int b){
	return sum(b)-sum(a-1);
}
 
void clearBIT(){
	for(auto u: curin){
		upd(u, -1);
	}
	curin.clear();
}
 
ll count_rectangles(vector<vi> a){
	n = sz(a);
	m = sz(a[0]);
	for(int i = 1; i+1 < n; i++){
		vi nums;
		for(int j = 0; j < m; j++){
			nums.pb(a[i][j]);
		}
		vpi a = getInts(nums);
		for(auto u: a){
			ints2[i].ins(mx*u.f+u.s);
		}
	}
 
	ht<int, null_type> vals;
 
	for(int i = 1; i+1 < n; i++){
		vals = ints2[i];
		for(auto x: vals){
			int j = x/mx;
			int u = x % mx;
			for(int K = i; K+1 < n; K++){
				if(ints2[K+1].find(mx*j+u) == ints2[K+1].end()){
					for(int k = i; k <= K; k++){
						queries[k][j].pb(mp(K, u));
						//cout << "Q: " << k << " " << j << " " << K << " " << u << "\n";
						ints2[k].erase(mx*j+u);
					}
					break;
				}
			}
		}
	}
 
	for(int i = 0; i < mx; i++){
		ints2[i].clear();
	}
 
	for(int j = 1; j+1 < m; j++){
		//cout << "j: " << j << "\n";
		vi nums;
		for(int i = 0; i < n; i++){
			nums.pb(a[i][j]);
		}
		vpi a = getInts(nums);
		// cout << "a: " << "\n";
		// for(auto u: a){
		// 	cout << u.f << " " << u.s << "\n";
		// }
		for(auto u: a){
			ints2[j].ins(mx*u.f+u.s);
			//ints[u.f][j].ins(u.s);
		}
	}
 
	
	for(int j = 1; j+1 < m; j++){
		vals = ints2[j];
		for(auto x: vals){
			int i = x/mx;
			int u = x % mx;
			for(int K = j; K+1 < m; K++){
				if(ints2[K+1].find(mx*i+u) == ints2[K+1].end()){
					for(int k = j; k <= K; k++){
						updates[i][k].pb(mp(u, K));
						//cout << "U: " << i << " " << k << " " << u << " " << K << "\n";
						//cout << i << " " << j << " " << k << "\n";
						ints2[k].erase(mx*i+u);
					}
					break;
				}
			}
		}
	}
 
	ll ans = 0;
 
	for(int i = 1; i+1 < n; i++){
		for(int j = 1; j+1 < m; j++){
			sort(all(queries[i][j]));
			sort(all(updates[i][j]));
			int updind = 0;
			for(auto u: queries[i][j]){
				while(updind < sz(updates[i][j])){
					if(updates[i][j][updind].f <= u.f){
						upd(updates[i][j][updind].s, 1);
						updind++;
					}
					else break;
				}
				//if(query(u.s, 2504) > 0) cout << i << " " << j << "\n";
				ans+=query(u.s, 2504); //number of things >=
			}
			clearBIT();
		}
	}
 
	return ans;
}

• Subtask 1: 8 / 8
• Subtask 2: 7 / 7
• Subtask 3: 12 / 12
• Subtask 4: 22 / 22
• Subtask 5: 10 / 10
• Subtask 6: 0 / 13
• Subtask 7: 0 / 28