Submission #331917

#	Time	Username	Problem	Language	Result	Execution time	Memory
331917		couplefire	Rectangles (IOI19_rect)	C++17	100 / 100	3818 ms	666200 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

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;
    }
};

struct Point{
    int ind, num;
    Point(){}
    Point(int ii, int nn){
        ind = ii, num = nn;
    }
};

long long count_rectangles(vector<vector<int>> grid) {
    int n = grid.size(), m = grid[0].size();
    if(n <= 2 || m <= 2) return 0;
    vector<Point> leftEnd[n][m];
    vector<Point> topEnd[n][m];
    int leftGreater[n][m];
    int topGreater[n][m];
    stack<pair<int, int>> leftST;
    stack<pair<int, int>> topST;
    for(int i = 0; i<n; i++){
        for(int j = 0; j<m; j++){
            while(!leftST.empty() && grid[i][j] >= leftST.top().first) leftST.pop();
            if(leftST.empty()) leftGreater[i][j] = -INF;
            else leftGreater[i][j] = leftST.top().second;
            leftST.push({grid[i][j], j});
        }
        while(!leftST.empty()) leftST.pop();
    }
    for(int j = 0; j<m; j++){
        for(int i = 0; i<n; i++){
            while(!topST.empty() && grid[i][j] >= topST.top().first) topST.pop();
            if(topST.empty()) topGreater[i][j] = -INF;
            else topGreater[i][j] = topST.top().second;
            topST.push({grid[i][j], i});
        }
        while(!topST.empty()) topST.pop();
    }
    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(Point(cur, 0));
                prev = cur;
                cur = leftGreater[i][cur];
            }
        }
    }
    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(Point(cur, 0));
                prev = cur;
                cur = topGreater[cur][j];
            }
        }
    }
    long long ans = 0;
    for(int j = 0; j<m; j++){
        int occur[m];
        int poccur[m];
        fill(occur, occur+m, 0);
        fill(poccur, poccur+m, 0);
        for(int i = 0; i<n; i++){
            if(i != 0){
                for(auto x : leftEnd[i-1][j]) poccur[x.ind] = occur[x.ind];
            }
            for(auto &x : leftEnd[i][j]){
                x.num = occur[x.ind]+1;
                occur[x.ind]++;
            }
            if(i != 0){
                for(auto x : leftEnd[i-1][j]) if(occur[x.ind] == poccur[x.ind]) occur[x.ind] = poccur[x.ind] = 0;
            }
        }
    }
    for(int i = 0; i<n; i++){
        int occur[n];
        int poccur[n];
        fill(occur, occur+n, 0);
        fill(poccur, poccur+n, 0);
        for(int j = 0; j<m; j++){
            if(j != 0){
                for(auto x : topEnd[i][j-1]) poccur[x.ind] = occur[x.ind];
            }
            for(auto &x : topEnd[i][j]){
                x.num = occur[x.ind]+1;
                occur[x.ind]++;
            }
            if(j != 0){
                for(auto x : topEnd[i][j-1]) if(occur[x.ind] == poccur[x.ind]) occur[x.ind] = poccur[x.ind] = 0;
            }
        }
    }
    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-x.num, x.ind});
            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.ind+1){
                    tree.add(tmp[ind].second, -1);
                    ind--;
                }
                if(ind < 0) break;
                ans += tree.sum(i-x.num, 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: 13 / 13
• Subtask 7: 28 / 28