Submission #331880

#	Time	Username	Problem	Language	Result	Execution time	Memory
331880		couplefire	Rectangles (IOI19_rect)	C++17	59 / 100	5109 ms	936608 KiB

rect

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
#define INF 1000000009
#define HEIGHT 7000005

template<class T> struct Seg { 
	const T ID = -INF; // comb(ID,b) must equal b, and maximum is less than 1e9
	T comb(T a, T b) { return max(a, b); } 
	int n; vector<T> seg;
	void init(int _n) { n = _n; seg.assign(2*n, -INF); }
	void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
	void upd(int p, T value) {	// set value at position p
		seg[p += n] = value;
		for (p /= 2; p; p /= 2) pull(p);
	}
	T query(int l, int r) {	 // minimum on interval [l, r]
		T ra = ID, rb = ID; 
		for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
			if (l&1) ra = comb(ra,seg[l++]);
			if (r&1) rb = comb(seg[--r],rb);
		}
		return comb(ra,rb);
	}
};

struct FenwickTree {
    vector<int> bit;  // binary indexed tree
    int n;
    FenwickTree(int n) {
        this->n = n;
        bit.assign(n, 0);
    }
    FenwickTree(vector<int> a) : FenwickTree(a.size()) {
        for (size_t i = 0; i < a.size(); i++)
            add(i, a[i]);
    }
    int sum(int r) {
        int ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }
    int sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }
    void add(int idx, int delta) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
};

long long count_rectangles(vector<vector<int>> grid) {
    int n = grid.size(), m = grid[0].size();
    if(n <= 2 || m <= 2) return 0;
    vector<int> leftEnd[n][m];
    vector<int> topEnd[n][m];
    int leftGreater[n][m];
    int topGreater[n][m];
    Seg<int> leftTree;
    Seg<int> topTree;
    leftTree.init(HEIGHT);
    topTree.init(HEIGHT);
    for(int i = 0; i<n; i++){
        for(int j = 0; j<m; j++){
            if(j == 0) leftGreater[i][j] = -INF;
            else leftGreater[i][j] = leftTree.query(grid[i][j]+1, HEIGHT-1);
            leftTree.upd(grid[i][j], j);
        }
        for(int j = 0; j<m; j++){
            leftTree.upd(grid[i][j], -INF);
        }
    }
    for(int j = 0; j<m; j++){
        for(int i = 0; i<n; i++){
            if(i == 0) topGreater[i][j] = -INF;
            else topGreater[i][j] = topTree.query(grid[i][j]+1, HEIGHT-1);
            topTree.upd(grid[i][j], i);
        }
        for(int i = 0; i<n; i++){
            topTree.upd(grid[i][j], -INF);
        }
    }
    for(int i = 0; i<n; i++){
        for(int j = 1; j<m; j++){
            int cur = leftGreater[i][j-1];
            int prev = j-1;
            while(cur != -INF && grid[i][prev] < grid[i][j]){
                leftEnd[i][j].push_back(cur);
                prev = cur;
                cur = leftGreater[i][cur];
            }
            sort(leftEnd[i][j].begin(), leftEnd[i][j].end());
            reverse(leftEnd[i][j].begin(), leftEnd[i][j].end());
        }
    }
    for(int j = 0; j<m; j++){
        for(int i = 1; i<n; i++){
            int cur = topGreater[i-1][j];
            int prev = i-1;
            while(cur != -INF && grid[prev][j] < grid[i][j]){
                topEnd[i][j].push_back(cur);
                prev = cur;
                cur = topGreater[cur][j];
            }
        }
    }
    long long ans = 0;
    map<pair<int, pair<int, int>>, int> leftMP;
    map<pair<int, pair<int, int>>, int> topMP;
    for(int i = 0; i<n; i++){
        for(int j = 0; j<m; j++){
            for(auto x : leftEnd[i][j]) leftMP[{i, {x, j}}] = leftMP[{i-1, {x, j}}]+1;
        }
    }
    for(int j = 0; j<m; j++){
        for(int i = 0; i<n; i++){
            for(auto x : topEnd[i][j]) topMP[{j, {x, i}}] = topMP[{j-1, {x, i}}]+1;
        }
    }
    FenwickTree tree(n);
    for(int i = 1; i<n-1; i++){
        for(int j = 2; j<m; j++){
            // if(i != 4 || j != 4) continue;
            if(leftEnd[i][j].empty()) continue;
            if(topEnd[i+1][j-1].empty()) continue;
            vector<pair<int, int>> tmp;
            for(auto x : topEnd[i+1][j-1]) tmp.push_back({j-topMP[{j-1, {x, i+1}}], x});
            sort(tmp.begin(), tmp.end());
            int ind = tmp.size()-1;
            for(auto x : tmp) tree.add(x.second, 1);
            for(auto x : leftEnd[i][j]){
                while(ind >= 0 && tmp[ind].first > x+1){
                    tree.add(tmp[ind].second, -1);
                    ind--;
                }
                if(ind < 0) break;
                ans += tree.sum(i-leftMP[{i, {x, j}}], i+1);
            }
            while(ind >= 0){
                tree.add(tmp[ind].second, -1);
                ind--;
            }
        }
    }
	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