Submission #143599

#	Time	Username	Problem	Language	Result	Execution time	Memory
143599		icypiggy	Rectangles (IOI19_rect)	C++14	100 / 100	4476 ms	796796 KiB

rect

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <stack>
#include <assert.h>
using namespace std;
const int n_max = 2550; // make it not lag
vector<pair<int,int>> h_map[n_max][n_max];
vector<pair<int,int>> v_map[n_max][n_max];
//vector<pair<int,int>> v_map2[n_max];
pair<int,int> tmp[n_max][n_max]; // start and end
void update_val(int left, int right, int row) {
    if(tmp[left][right].second != row-1) {
        if(tmp[left][right].second!=-2) {
            for(int i=tmp[left][right].first; i<=tmp[left][right].second; i++) {
                h_map[i][left].push_back(make_pair(tmp[left][right].second, right));
            }
        }
        tmp[left][right] = make_pair(row, row);
    } else {
        tmp[left][right].second++;
    }
}
void update_val2(int left, int right, int row) {
    if(tmp[left][right].second != row-1) {
        if(tmp[left][right].second!=-2) {
            for(int i=tmp[left][right].first; i<=tmp[left][right].second; i++) {

                v_map[left][i].push_back(make_pair(right, tmp[left][right].second));
            }
        }
        tmp[left][right] = make_pair(row, row);
    } else {
        tmp[left][right].second++;
    }
}
stack<int> s;
void gen_h_seg(vector<int> &x, int r) {
    s.push(0);
    for(int i=1; i<x.size(); i++) {
        while(!s.empty() && x[s.top()]<x[i]) {
            if(s.top()!=i-1) {
                update_val(s.top()+1, i-1, r);

            }
            int t = x[s.top()];
            while(!s.empty() && x[s.top()]==t) {
                s.pop();
            }
        }
        if(!s.empty() && s.top()!=i-1) {
            update_val(s.top()+1, i-1, r);
        }
        s.push(i);
    }
    while(!s.empty()) s.pop();
}
int fwbit[n_max][n_max];
int fwa[n_max][n_max];
int fw_pt = 0;
struct fenwick {
    int *BIT;
    int *a;
    int n;
    fenwick(): n(n_max) {}
    void reset() {
        BIT = fwbit[fw_pt];
        a = fwa[fw_pt];
        fw_pt++;
    }
    void update(int x, int delta)
    {
          for(; x <= n; x += x&-x)
            BIT[x] += delta;
    }
    int query(int x) {
         int sum = 0;
         for(; x > 0; x -= x&-x)
            sum += BIT[x];
         return sum;
    }

};
void gen_v_seg(vector<int> &x, int r) {
    s.push(0);
    for(int i=1; i<x.size(); i++) {
        while(!s.empty() && x[s.top()]<x[i]) {
            if(s.top()!=i-1) {
                update_val2(s.top()+1, i-1, r);
            }
            int t = x[s.top()];
            while(!s.empty() && x[s.top()]==t) {
                s.pop();
            }
        }
        if(!s.empty() && s.top()!=i-1) {
            update_val2(s.top()+1, i-1, r);
        }
        s.push(i);
    }
    while(!s.empty()) s.pop();
}

long long count_rectangles(vector<vector<int>> a) {
    for(int i=0; i<n_max; i++) {
        for(int j=0; j<n_max; j++) {
            tmp[i][j] = make_pair(-2,-2);
        }
    }
    for(int i=0; i<a.size(); i++) {
        gen_h_seg(a[i],i);
    }
    for(int i=0; i<n_max; i++) {
        for(int j=0; j<=i; j++) {
            update_val(j,i,1e5);
        }
    }
    for(int i=0; i<n_max; i++) {
        for(int j=0; j<n_max; j++) {
            tmp[i][j] = make_pair(-2,-2);
        }
    }
    //cout << "\n";
    for(int i=0; i<a[0].size(); i++) {
        vector<int> tmp;
        for(int j=0; j<a.size(); j++) {
            tmp.push_back(a[j][i]);
        }
        gen_v_seg(tmp, i);
    }
    for(int i=0; i<n_max; i++) {
        for(int j=0; j<=i; j++) {
            update_val2(j,i,1e5);
        }
    }
    fenwick f;
    f.reset();
    long long ans = 0;
    for(int i=0; i<a.size(); i++) {
        for(int j=0; j<a[0].size(); j++) {
            if(v_map[i][j].size()<7	 || h_map[i][j].size()<7) {
                for(auto &p: h_map[i][j]) {
                    for(auto &q: v_map[i][j]) {
                        if(p.first>=q.first && p.second<=q.second) {
                            ans++;
                            //cout << i << " " << j << " " << q.first << " " << p.second << "\n";
                        }
                    }
                }
            } else {
                auto it = v_map[i][j].begin();
                sort(h_map[i][j].begin(), h_map[i][j].end());
                for(auto &p: h_map[i][j]) {
                    f.update(p.second, 1);
                }
                sort(v_map[i][j].begin(), v_map[i][j].end());
                for(auto &p: h_map[i][j]) {
                    while(it!=v_map[i][j].end() && it->first<=p.first) {
                        ans+=f.query(it->second);
                        it++;
                    }
                    f.update(p.second, -1);
                }
            }
        }
    }
    return ans;
}

Compilation message (stderr)

rect.cpp: In function 'void gen_h_seg(std::vector<int>&, int)':
rect.cpp:41:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1; i<x.size(); i++) {
                  ~^~~~~~~~~
rect.cpp: In function 'void gen_v_seg(std::vector<int>&, int)':
rect.cpp:87:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1; i<x.size(); i++) {
                  ~^~~~~~~~~
rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:111:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<a.size(); i++) {
                  ~^~~~~~~~~
rect.cpp:125:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<a[0].size(); i++) {
                  ~^~~~~~~~~~~~
rect.cpp:127:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<a.size(); j++) {
                      ~^~~~~~~~~
rect.cpp:140:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0; i<a.size(); i++) {
                  ~^~~~~~~~~
rect.cpp:141:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0; j<a[0].size(); j++) {
                      ~^~~~~~~~~~~~

• 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