Submission #154394

#	Time	Username	Problem	Language	Result	Execution time	Memory
154394		bruce_test	Rectangles (IOI19_rect)	C++14	100 / 100	4105 ms	807804 KiB

rect

#pragma GCC optimize "Ofast"
#pragma GCC optimize "unroll-loops"
#pragma GCC target "sse,sse2,sse3,sse4,abm,avx,mmx,popcnt,tune=native"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
typedef long long ll;
#define f first
#define s second
const int MM = 2505;
int N, M, a[MM][MM], st[MM], top, l[MM], r[MM], u[MM], d[MM], toclear[MM], cnt; ll bit[MM], ans;
vector<pi> h[MM][MM], v[MM][MM];
bool cmp(pi x, pi y){ return x.s < y.s; }
void upd(int x, int val){
    for(int i=x; i<MM; i+=i&-i) bit[i] += val;
}
ll qry(int x){
    ll sum = 0;
    for(int i=x; i; i-=i&-i) sum += bit[i];
    return sum;
}
long long count_rectangles(std::vector<std::vector<int>> x){
    N = x.size(); M = x[0].size();
    for(int i=1; i<=N; i++){
        top = 0;
        for(int j=1; j<=M; j++){
            a[i][j] = x[i-1][j-1];
            while(top > 0 && a[i][st[top]] < a[i][j]) top--;
            l[j] = st[top]; st[++top] = j;
        }
        top = 0;
        for(int j=M; j>=1; j--){
            while(top > 0 && a[i][st[top]] <= a[i][j]) top--;
            r[j] = st[top]; st[++top] = j;
            if(l[j] && r[j] && a[i][l[j]] > a[i][j]) h[i][l[j]+1].push_back({r[j]-l[j]-1, 1});
        }
    }
    for(int j=1; j<=M; j++){
        top = 0;
        for(int i=1; i<=N; i++){
            while(top > 0 && a[st[top]][j] < a[i][j]) top--;
            u[i] = st[top]; st[++top] = i;
        }
        top = 0 ;
        for(int i=N; i>=1; i--){
            while(top > 0 && a[st[top]][j] <= a[i][j]) top--;
            d[i] = st[top]; st[++top] = i;
            if(u[i] && d[i] && a[u[i]][j] > a[i][j]) v[u[i]+1][j].push_back({d[i]-u[i]-1, 1});
        }
    }
    for(int i=N; i>=1; i--){
        for(int j=M; j>=1; j--){
            if(!h[i][j].empty()){
                sort(h[i][j].begin(), h[i][j].end());
                for(int p=0, q=0; p<h[i][j].size(); p++){
                    while(q < h[i+1][j].size() && h[i+1][j][q].f < h[i][j][p].f) q++;
                    if(q < h[i+1][j].size() && h[i+1][j][q].f == h[i][j][p].f) h[i][j][p].s = h[i+1][j][q].s+1;
                }
            }
            if(!v[i][j].empty()){
                sort(v[i][j].begin(), v[i][j].end());
                for(int p=0, q=0; p<v[i][j].size(); p++){
                    while(q<v[i][j+1].size() && v[i][j+1][q].f < v[i][j][p].f) q++;
                    if(q<v[i][j+1].size() && v[i][j+1][q].f == v[i][j][p].f) v[i][j][p].s = v[i][j+1][q].s+1;
                }
            }
        }
    }
    for(int i=1; i<=N; i++){
        for(int j=1; j<=M; j++){
            if(h[i][j].empty() || v[i][j].empty()) continue;
            cnt = 0;
            sort(v[i][j].begin(), v[i][j].end(), cmp);
            for(int p=(int)h[i][j].size()-1, q=(int)v[i][j].size()-1; p>=0; p--){
                for( ;q>=0 && v[i][j][q].s >= h[i][j][p].f; q--) {
                    upd(v[i][j][q].f, 1); toclear[cnt++] = v[i][j][q].f;
                }
                ans += qry(h[i][j][p].s);
            }
            for(int p=0; p<cnt; p++) upd(toclear[p], -1);
        }
    }
    return ans;
}

Compilation message (stderr)

rect.cpp: In function 'long long int count_rectangles(std::vector<std::vector<int> >)':
rect.cpp:55:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int p=0, q=0; p<h[i][j].size(); p++){
                                   ~^~~~~~~~~~~~~~~
rect.cpp:56:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     while(q < h[i+1][j].size() && h[i+1][j][q].f < h[i][j][p].f) q++;
                           ~~^~~~~~~~~~~~~~~~~~
rect.cpp:57:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     if(q < h[i+1][j].size() && h[i+1][j][q].f == h[i][j][p].f) h[i][j][p].s = h[i+1][j][q].s+1;
                        ~~^~~~~~~~~~~~~~~~~~
rect.cpp:62:36: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int p=0, q=0; p<v[i][j].size(); p++){
                                   ~^~~~~~~~~~~~~~~
rect.cpp:63:28: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     while(q<v[i][j+1].size() && v[i][j+1][q].f < v[i][j][p].f) q++;
                           ~^~~~~~~~~~~~~~~~~
rect.cpp:64:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     if(q<v[i][j+1].size() && v[i][j+1][q].f == v[i][j][p].f) v[i][j][p].s = v[i][j+1][q].s+1;
                        ~^~~~~~~~~~~~~~~~~

• 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