Submission #725136

#	Time	Username	Problem	Language	Result	Execution time	Memory
725136		QwertyPi	Rectangles (IOI19_rect)	C++14	0 / 100	199 ms	297308 KiB

rect

#include "rect.h"
#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#define fi first
#define se second
#define pii pair<int, int>
using namespace std;
const int N = 2500 + 11;
 
struct DSU{
	int dsu[N], l[N], r[N];
	void init(int n){
		for(int i = 0; i <= n + 2; i++) dsu[i] = l[i] = r[i] = i;
	}
	int root(int x){
		if(x == dsu[x]) return x;
		return dsu[x] = root(dsu[x]);
	}
	void join(int x, int y){
		x = root(x), y = root(y);
		if(x == y) return;
		dsu[y] = x;
		l[x] = min(l[x], l[y]);
		r[x] = max(r[x], r[y]);
	}
} dsu;
 
int at(const vector<int>& v, int idx){
	if(idx < 0 || idx >= (int) v.size()) return -(1 << 30);
	return v[idx];
}
 
vector<pii> build(const vector<int>& v){
	vector<pii> res;
	vector<pii> vp; int n = v.size();
	for(int i = 0; i < n; i++){
		vp.push_back({v[i], i});
	}
	sort(vp.begin(), vp.end());
	dsu.init(n);
	for(auto i : vp){
		dsu.join(i.se, i.se + 1);
		int rt = dsu.root(i.se);
		int b_l = dsu.l[rt], b_r = dsu.r[rt] - 1;
		if(at(v, b_l - 1) > i.fi && at(v, b_r + 1) > i.fi){
			res.push_back({b_l, b_r});
		}
	}
	return res;
}
 
 
struct Rect{
	int16_t x1, x2, y1, y2, id;
	void pr() { printf("%d %d %d %d\n", x1, x2, y1, y2); }
	friend Rect operator+ (const Rect& a, const Rect& b){
		return {max(a.x1, b.x1), min(a.x2, b.x2), max(a.y1, b.y1), min(a.y2, b.y2)};
	}
};
 
void split(const vector<Rect>& a, vector<Rect>& al, vector<Rect>& ar, int xm){
    for(auto r : a) {
        if(r.x1 <= xm) al.push_back(r);
        else ar.push_back(r);
    }
}
 
long long ans = 0;
 
struct BIT2D{
    int bit[N][N];
    void add(int x, int y, int v){
        x++; y++;
        for(int i = x; i < N; i += i & -i){
            for(int j = y; j < N; j += j & -j){
                bit[i][j] += v;
            }
        }
    }
    int qry(int x, int y){
        x++; y++; int res = 0;
        for(int i = x; i; i -= i & -i){
            for(int j = y; j; j -= j & -j){
                res += bit[i][j];
            }
        }
		return res;
    }
} bit2;
 
vector<int> xs[N * N], ys[N * N];
vector<Rect> xr, yr;
vector<pii> x[N], y[N];
 
long long count_rectangles(std::vector<std::vector<int>> a) {
	int n = a.size(), m = a[0].size(), mx = 0;
	for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) mx = max(mx, a[i][j]);
	for(int i = 0; i < n; i++){
		vector<int> v; for(int j = 0; j < m; j++) v.push_back(a[i][j]);
		x[i] = build(v);
		for(pii p : x[i]){
			xs[p.fi * m + p.se].push_back(i);
		}
	}
	for(int i = 0; i < m * m; i++){
		int x1 = i / m, x2 = i % m; if(x1 > x2) continue;
		int y1 = -2, y2 = -2;
		for(auto j : xs[i]){
			if(j == y2 + 1){
				y2++;
			}else{
				if(y1 != -2) xr.push_back({x1, x2, y1, y2});
				y1 = y2 = j;
			}
		}
		if(y1 != -2) xr.push_back({x1, x2, y1, y2});
	}
	for(int j = 0; j < m; j++){
		vector<int> v; for(int i = 0; i < n; i++) v.push_back(a[i][j]);
		y[j] = build(v);
		for(pii p : y[j]){
			ys[p.fi * n + p.se].push_back(j);
		}
	}
	for(int i = 0; i < n * n; i++){
		int y1 = i / n, y2 = i % n; if(y1 > y2) continue;
		int x1 = -2, x2 = -2;
		for(auto j : ys[i]){
			if(j == x2 + 1){
				x2++;
			}else{
				if(x1 != -2) yr.push_back({x1, x2, y1, y2});
				x1 = x2 = j;
			}
		}
		if(x1 != -2) yr.push_back({x1, x2, y1, y2});
	}
	for(auto& r1 : xr) r1.x1 = m - 1 - r1.x1, r1.y2 = n - 1 - r1.y2, r1.id = 0;
	for(auto& r2 : yr) r2.x1 = m - 1 - r2.x1, r2.y2 = n - 1 - r2.y2, r2.id = 1;
	vector<Rect> r_all;
	for(auto& r : xr) r_all.push_back(r);
	for(auto& r : yr) r_all.push_back(r);
	long long P1 = 0, P2 = 0, Q = 0;

	// P1
	sort(r_all.begin(), r_all.end(), [](const Rect& a, const Rect& b){
		return a.x1 < b.x1 || a.x1 == b.x1 && a.x2 < b.x2 || a.x2 == b.x2 && a.x1 == b.x1 && a.id < b.id;
	});
	for(auto& r : r_all){
		if(r.id == 0) bit2.add(r.y1, r.y2, 1);
		else P1 += bit2.qry(r.y1, r.y2);
	}
	for(auto& r : r_all){
		if(r.id == 0) bit2.add(r.y1, r.y2, -1);
	}

	// P2
	sort(r_all.begin(), r_all.end(), [](const Rect& a, const Rect& b){
		return a.x2 < b.x2 || a.x2 == b.x2 && a.x1 < b.x1 || a.x2 == b.x2 && a.x1 == b.x1 && a.id < b.id;
	});
	for(auto& r : r_all){
		if(r.id == 0) bit2.add(r.y1, r.y2, 1);
		else P2 += bit2.qry(r.y1, r.y2);
	}
	for(auto& r : r_all){
		if(r.id == 0) bit2.add(r.y1, r.y2, -1);
	}

	// Q
	for(auto& i : xr) bit2.add(i.y1, i.y2, 1);
	for(auto& i : yr) Q += bit2.qry(i.y1, i.y2);
	for(auto& i : xr) bit2.add(i.y1, i.y2, -1);

	return P1 + P2 - Q;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:113:32: warning: narrowing conversion of 'x1' from 'int' to 'int16_t' {aka 'short int'} [-Wnarrowing]
  113 |     if(y1 != -2) xr.push_back({x1, x2, y1, y2});
      |                                ^~
rect.cpp:113:36: warning: narrowing conversion of 'x2' from 'int' to 'int16_t' {aka 'short int'} [-Wnarrowing]
  113 |     if(y1 != -2) xr.push_back({x1, x2, y1, y2});
      |                                    ^~
rect.cpp:113:40: warning: narrowing conversion of 'y1' from 'int' to 'int16_t' {aka 'short int'} [-Wnarrowing]
  113 |     if(y1 != -2) xr.push_back({x1, x2, y1, y2});
      |                                        ^~
rect.cpp:113:44: warning: narrowing conversion of 'y2' from 'int' to 'int16_t' {aka 'short int'} [-Wnarrowing]
  113 |     if(y1 != -2) xr.push_back({x1, x2, y1, y2});
      |                                            ^~
rect.cpp:117:30: warning: narrowing conversion of 'x1' from 'int' to 'int16_t' {aka 'short int'} [-Wnarrowing]
  117 |   if(y1 != -2) xr.push_back({x1, x2, y1, y2});
      |                              ^~
rect.cpp:117:34: warning: narrowing conversion of 'x2' from 'int' to 'int16_t' {aka 'short int'} [-Wnarrowing]
  117 |   if(y1 != -2) xr.push_back({x1, x2, y1, y2});
      |                                  ^~
rect.cpp:117:38: warning: narrowing conversion of 'y1' from 'int' to 'int16_t' {aka 'short int'} [-Wnarrowing]
  117 |   if(y1 != -2) xr.push_back({x1, x2, y1, y2});
      |                                      ^~
rect.cpp:117:42: warning: narrowing conversion of 'y2' from 'int' to 'int16_t' {aka 'short int'} [-Wnarrowing]
  117 |   if(y1 != -2) xr.push_back({x1, x2, y1, y2});
      |                                          ^~
rect.cpp:133:32: warning: narrowing conversion of 'x1' from 'int' to 'int16_t' {aka 'short int'} [-Wnarrowing]
  133 |     if(x1 != -2) yr.push_back({x1, x2, y1, y2});
      |                                ^~
rect.cpp:133:36: warning: narrowing conversion of 'x2' from 'int' to 'int16_t' {aka 'short int'} [-Wnarrowing]
  133 |     if(x1 != -2) yr.push_back({x1, x2, y1, y2});
      |                                    ^~
rect.cpp:133:40: warning: narrowing conversion of 'y1' from 'int' to 'int16_t' {aka 'short int'} [-Wnarrowing]
  133 |     if(x1 != -2) yr.push_back({x1, x2, y1, y2});
      |                                        ^~
rect.cpp:133:44: warning: narrowing conversion of 'y2' from 'int' to 'int16_t' {aka 'short int'} [-Wnarrowing]
  133 |     if(x1 != -2) yr.push_back({x1, x2, y1, y2});
      |                                            ^~
rect.cpp:137:30: warning: narrowing conversion of 'x1' from 'int' to 'int16_t' {aka 'short int'} [-Wnarrowing]
  137 |   if(x1 != -2) yr.push_back({x1, x2, y1, y2});
      |                              ^~
rect.cpp:137:34: warning: narrowing conversion of 'x2' from 'int' to 'int16_t' {aka 'short int'} [-Wnarrowing]
  137 |   if(x1 != -2) yr.push_back({x1, x2, y1, y2});
      |                                  ^~
rect.cpp:137:38: warning: narrowing conversion of 'y1' from 'int' to 'int16_t' {aka 'short int'} [-Wnarrowing]
  137 |   if(x1 != -2) yr.push_back({x1, x2, y1, y2});
      |                                      ^~
rect.cpp:137:42: warning: narrowing conversion of 'y2' from 'int' to 'int16_t' {aka 'short int'} [-Wnarrowing]
  137 |   if(x1 != -2) yr.push_back({x1, x2, y1, y2});
      |                                          ^~
rect.cpp: In lambda function:
rect.cpp:148:38: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  148 |   return a.x1 < b.x1 || a.x1 == b.x1 && a.x2 < b.x2 || a.x2 == b.x2 && a.x1 == b.x1 && a.id < b.id;
      |                         ~~~~~~~~~~~~~^~~~~~~~~~~~~~
rect.cpp:148:85: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  148 |   return a.x1 < b.x1 || a.x1 == b.x1 && a.x2 < b.x2 || a.x2 == b.x2 && a.x1 == b.x1 && a.id < b.id;
      |                                                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
rect.cpp: In lambda function:
rect.cpp:160:38: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  160 |   return a.x2 < b.x2 || a.x2 == b.x2 && a.x1 < b.x1 || a.x2 == b.x2 && a.x1 == b.x1 && a.id < b.id;
      |                         ~~~~~~~~~~~~~^~~~~~~~~~~~~~
rect.cpp:160:85: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  160 |   return a.x2 < b.x2 || a.x2 == b.x2 && a.x1 < b.x1 || a.x2 == b.x2 && a.x1 == b.x1 && a.id < b.id;
      |                                                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

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