Submission #1232030

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232030		ksu2009en	Rectangles (IOI19_rect)	C++20	100 / 100	2089 ms	798228 KiB

rect

#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <bitset>
#include <cstring>
#include <unordered_map>

using namespace std;
typedef long long ll;

#include "rect.h"

ll n, m;

vector<int> f[2502][2502], d[2502][2502]; // f -- for [i][j], left, horizontal.
vector<pair<int, int>> can[2502][2502];

int h[2502];

ll t[2502];

vector<int> roll;

void add(int pos, int val){
    // roll.push_back(pos);
    
    pos++;
    
    for(int i = pos; i < 2502; i += (i & -i))
        t[i] += val;
}

int get(int pos){
    pos++;
    
    int ans = 0;
    
    for(int i = pos; i > 0; i -= (i & -i))
        ans += t[i];
    
    return ans;
}

long long count_rectangles(vector<vector<int>> a){
    n = a.size(), m = a[0].size();
    
    for(int j = 0; j < m; j++){
        vector<int> cur;
        
        for(int i = 1; i < n; i++){
            while(!cur.empty() && a[cur.back()][j] <= a[i - 1][j])
                cur.pop_back();
            
            cur.push_back(i - 1);
            
            for(int k = (ll)(cur.size()) - 1; k >= 0; k--){
                if(cur[k] != i - 1){
                    d[i][j].push_back(cur[k]);
                }
                
                if(a[cur[k]][j] >= a[i][j])
                    break;
            }
        }
    }
    
    for(int i = 0; i < n; i++){
        vector<pair<int, int>> cur; // {length from the left horizontal, index above }
        vector<pair<int, int>> temp; // {length from the left horizontal, index above }
        vector<int> cur2;

        for(int j = 1; j < m; j++){
            while(!cur2.empty() && a[i][cur2.back()] <= a[i][j - 1])
                cur2.pop_back();
            
            cur2.push_back(j - 1);
            
            for(int k = (ll)(cur2.size()) - 1; k >= 0; k--){
                if(cur2[k] != j - 1){
                    f[i][j].push_back(cur2[k]);
                }
                
                if(a[i][cur2[k]] >= a[i][j])
                    break;
            }
            
            for(auto k: cur)
                h[k.second] = -k.first;
            
            for(auto k: d[i][j - 1]){
                if(h[k] < 0)
                    h[k] = abs(h[k]) + 1;
                else
                    h[k] = 1;
            }
            
            temp.clear();
            
            for(auto k: d[i][j - 1]){
                if(h[k] == 1)
                    temp.push_back({1, k});
            }
            
            for(auto i: cur){
                if(h[i.second] > 1)
                    temp.push_back({h[i.second], i.second});
            }
            
            for(auto k: cur)
                h[k.second] = 0;
            
            can[i][j] = temp;
            cur = temp;
        }
        
        for(int j = 0; j <= n; j++)
            h[j] = 0;
    }
    
    ll ans = 0;
    
    for(int j = 2; j < m; j++){
        vector<pair<int, int>> cur; // {index to the left, length above }

        for(int i = 2; i < n; i++){
            for(auto k: cur)
                h[k.first] = -k.second;
            
            for(auto k: f[i - 1][j]){
                if(h[k] < 0)
                    h[k] = abs(h[k]) + 1;
                else
                    h[k] = 1;
            }
            
            for(auto k: cur)
                if(h[k.first] < 0)
                    h[k.first] = 0;
            
            cur.clear();
            reverse(f[i - 1][j].begin(), f[i - 1][j].end());
            
            for(auto k: f[i - 1][j]){
                cur.push_back({k, h[k]});
            }
            
            int ind = (ll)(can[i][j].size()) - 1;
            
            for(int k = 0; k < cur.size(); k++){
                while(ind >= 0){ // maybe we can add that
                    if(j - 1 - can[i][j][ind].first <= cur[k].first){
                        add(n - 1 - can[i][j][ind].second, 1);
                        ind--;
                    }
                    else
                        break;
                }
                                
                int cnt = get(n - 1 - (i - cur[k].second - 1));
                ans += cnt;
            }
            
            for(int k = (ll)(can[i][j].size()) - 1; k > ind; k--){
                add(n - 1 - can[i][j][k].second, -1);
            }
        }
        
        for(int j = 0; j <= m; j++)
            h[j] = 0;
    }
    
    
    return ans;
}

/*
 3 5
 4 8 7 20 6
 10 8 9 2 999
 9 7 20 14 2
 
 
 
 5 7
 1 1 1 1 1 0 1
 1 0 1 0 0 0 1
 1 1 1 0 1 1 0
 1 0 1 1 1 0 1
 1 1 0 0 0 1 0
 
 */

• 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