제출 #1062819

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1062819		jcelin	Rectangles (IOI19_rect)	C++14	100 / 100	1976 ms	705972 KiB

rect

#include <bits/stdc++.h>
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
 
using namespace std;
//using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
 
typedef pair<int,int> ii;
#define pll pair<ll,ll>
#define vi vector<int>
#define vii vector<ii>
#define vll vector<ll>
#define vpll vector<pll>
#define matrix vector<vi>
#define matrixLL vector<vll>
#define vs vector<string>
#define vui vector<ui>
#define msi multiset<int>
#define mss multiset<string>
#define si set<int>
#define ss set<string>
#define PB push_back
#define PF push_front
#define PPB pop_back
#define PPF pop_front
#define X first
#define Y second
#define MP make_pair
#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
 
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
const int dxx[] = {-1, 1, 0, 0, 1, 1, -1, -1};
const int dyy[] = {0, 0, -1, 1, -1, 1, -1, 1};
const string abc="abcdefghijklmnopqrstuvwxyz";
const string ABC="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ld pi = 3.14159265;
const int mod = 1e9 + 7;
const int MOD = 1e9 + 7;
const int MAXN = 2510;
const int inf = mod;
const ll INF = 1e18;
const ll zero = ll(0);
const int logo = 13;
const int off = 1 << logo;
const int trsz = off << 1;

struct rmq{
	vector<int> v;
	int n;
	static const int b = 30; // block size
	int type;
	vector<int> mask, t; // mask and sparse table

	int op(int x, int y){
		if(type == 0){
			if(v[x] > v[y]) return x;
			return y;
		}
		if(v[x] < v[y]) return x;
		return y;
	}
	// least significant set bit
	int lsb(int x) {
		return x & -x;
	}
	// index of the most significant set bit
	int msb_index(int x) {
		return __builtin_clz(1)-__builtin_clz(x);
	}
	// answer query of v[r-size+1..r] using the masks, given size <= b
	int small(int r, int size = b) {
		// get only 'size' least significant bits of the mask
		// and then get the index of the msb of that
		int dist_from_r = msb_index(mask[r] & ((1<<size)-1));

		return r - dist_from_r;
	}
	
	rmq(){
		v = {};
		n = 0;
		type = 0;
		mask = {};
		t = {};
	}
	
	rmq(const vector<int> &v_, int _type){
		v = v_;
		n = v.size();
		type = _type;
		mask.clear();
		mask.resize(n);
		t.clear();
		t.resize(n);
		
		int curr_mask = 0;
		for (int i = 0; i < n; i++) {

			// shift mask by 1, keeping only the 'b' least significant bits
			curr_mask = (curr_mask<<1) & ((1<<b)-1);

			while (curr_mask > 0 and op(i, i - msb_index(lsb(curr_mask))) == i) {
				// current value is smaller than the value represented by the
				// last 1 in curr_mask, so we need to turn off that bit
				curr_mask ^= lsb(curr_mask);
			}
			// append extra 1 to the mask
			curr_mask |= 1;

			mask[i] = curr_mask;
		}

		// build sparse table over the n/b blocks
		// the sparse table is linearized, so what would be at
		// table[j][i] is stored in table[(n/b)*j + i]
		for (int i = 0; i < n/b; i++) t[i] = small(b*i+b-1);
		for (int j = 1; (1<<j) <= n/b; j++) for (int i = 0; i+(1<<j) <= n/b; i++)
			t[n/b*j+i] = op(t[n/b*(j-1)+i], t[n/b*(j-1)+i+(1<<(j-1))]);
	}
	// query(l, r) returns the actual minimum of v[l..r]
	// to get the index, just change the first and last lines of the function
	int query(int l, int r) {
		// query too small
		if (r-l+1 <= b) return v[small(r, r-l+1)];

		// get the minimum of the endpoints
		// (there is no problem if the ranges overlap with the sparse table query)
		int ans = op(small(l+b-1), small(r));

		// 'x' and 'y' are the blocks we need to query over
		int x = l/b+1, y = r/b-1;

		if (x <= y) {
			int j = msb_index(y-x+1);
			ans = op(ans, op(t[n/b*j+x], t[n/b*j+y-(1<<j)+1]));
		}

		return v[ans];
	}
}h1[MAXN], h2[MAXN], h3[MAXN], h4[MAXN];

ii st[MAXN];
int bg[MAXN][MAXN][4];
vi veci[MAXN][2], vecj[MAXN][2];

ll count_rectangles(matrix mat){
	int n = mat.size();
	int m = mat[0].size();
	
	int ind = 0;
	REP(i, n){
		st[0] = {inf, -1};
		ind = 0;
		REP(j, m){
			while(st[ind].X < mat[i][j]) ind--;
			bg[i][j][0] = st[ind].Y;
			vecj[j][0].PB(bg[i][j][0]);
			while(st[ind].X <= mat[i][j]) ind--;
			bg[i][j][0] = st[ind].Y;
			ind++;
			st[ind] = {mat[i][j], j};
		}
		
		st[0] = {inf, m + 1};
		ind = 0;
		for(int j = m - 1; j >= 0; j--){
			while(st[ind].X < mat[i][j]) ind--;
			bg[i][j][1] = st[ind].Y;
			vecj[j][1].PB(bg[i][j][1]);
			while(st[ind].X <= mat[i][j]) ind--;
			bg[i][j][1] = st[ind].Y;
			ind++;
			st[ind] = {mat[i][j], j};
		}
	}
	
	
	REP(j, m){
		st[0] = {inf, -1};
		ind = 0;
		REP(i, n){
			while(st[ind].X < mat[i][j]) ind--;
			bg[i][j][2] = st[ind].Y;
			veci[i][0].PB(bg[i][j][2]);
			while(st[ind].X <= mat[i][j]) ind--;
			
			ind++;
			st[ind] = {mat[i][j], i};
		}
		
		st[0] = {inf, n + 1};
		ind = 0;
		for(int i = n - 1; i >= 0; i--){
			while(st[ind].X < mat[i][j]) ind--;
			bg[i][j][3] = st[ind].Y;
			veci[i][1].PB(bg[i][j][3]);
			while(st[ind].X <= mat[i][j]) ind--;
			bg[i][j][3] = st[ind].Y;
			ind++;
			st[ind] = {mat[i][j], i};
		}
	}
	
	REP(j, m){
		h1[j] = rmq(vecj[j][0], 0);
		h2[j] = rmq(vecj[j][1], 1);
	}
	
	REP(i, n){
		h3[i] = rmq(veci[i][0], 0);
		h4[i] = rmq(veci[i][1], 1);
	}
	
	vll good;
	REP(i, n){
		REP(j, m){
			if(i == 0 or j == 0 or i == n - 1 or j == m - 1) continue;
			if(bg[i][j][0] == -1 or bg[i][j][1] == m + 1) continue;
			if(bg[i][j][2] == -1 or bg[i][j][3] == n + 1) continue;
			ll hash = 0;
			REP(k, 4) hash *= MAXN, hash += bg[i][j][k];
			
		
			if(bg[i][j][0] < h1[bg[i][j][1]].query(bg[i][j][2] + 1, (bg[i][j][3] - 1))) continue;
			if(bg[i][j][1] > h2[bg[i][j][0]].query(bg[i][j][2] + 1, (bg[i][j][3] - 1))) continue;
			if(bg[i][j][2] < h3[bg[i][j][3]].query(bg[i][j][0] + 1, (bg[i][j][1] - 1))) continue;
			if(bg[i][j][3] > h4[bg[i][j][2]].query(bg[i][j][0] + 1, (bg[i][j][1] - 1))) continue;
			good.PB(hash);
		}
	}
	if(good.empty()) return 0;
	sort(all(good));
	ll pre = good[0];
	int ret = 1;
	for(auto &x : good) ret += (x != pre), pre = x;
	return ret;
}

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