Submission #817630

#	Time	Username	Problem	Language	Result	Execution time	Memory
817630		DJeniUp	Rectangles (IOI19_rect)	C++17	100 / 100	1331 ms	140308 KiB

rect

#include "bits/stdc++.h"
#include "rect.h"

#pragma GCC optimize("O3")

using namespace std;

typedef  int ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pairll;
typedef pair<ll,ull>pairull;
typedef pair<ll,pairll>pair3l;
typedef long double ld;
typedef pair<ld,ld>pairld;

typedef pair<string,ll>pairsl;

#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define N 100007
#define MOD 1000000007
#define INF 10000000000007
#define eps 0.00000000001
#define A 50
#define PI 3.14159265359

ll n,m,d[2500][2500],t[2500][2500],l[2500][2500],p[2501];

stack<ll>s;

vector<ll>k1;

//vector<ll>h;

vector<ll>v[12][2500];

bitset<2500>o[2500];

void S(vector<ll>&a1,vector<ll>&b1,ll z,vector<ll>&res){
    res.clear();
    ll x=0;
    ll y=0;
    while(x<a1.size() && y<b1.size() && a1[x]<=z && b1[y]<=z){
        //cout<<x<<" "<<y<<" "<<a1[x]<<" "<<b1[y]<<endl;
        if(a1[x]==b1[y]){
            res.pb(a1[x]);
            x++;
            y++;
        }else if(a1[x]<b1[y])x++;
        else y++;
    }
    return ;
}

long long count_rectangles(std::vector<std::vector<int> > a){
    n=a.size();
    m=a[0].size();
    //cout<<n<<" "<<m<<endl;
    for(int i=2;i<=m;i++){
        if((1<<(p[i-1]+1))==i){
            p[i]=p[i-1]+1;
        }else p[i]=p[i-1];
    }
    for(int i=1;i<n-1;i++){
        while(s.size()>0)s.pop();
        s.push(m-1);
        for(int j=m-2;j>0;j--){
            while(s.size()>0 && a[i][s.top()]<=a[i][j])s.pop();
            if(s.size()>0){
                d[i][j]=s.top();
            }
            s.push(j);
        }
    }
    //cout<<1<<endl;
    for(int j=1;j<m-1;j++){
        while(s.size()>0)s.pop();
        s.push(n-1);
        for(int i=n-2;i>0;i--){
            while(s.size()>0 && a[s.top()][j]<=a[i][j])s.pop();
            if(s.size()>0){
                t[i][j]=s.top();
            }
            s.push(i);
        }
    }
    //cout<<2<<endl;

    //cout<<3<<endl;
    ll res=0;
    for(int i=n-2;i>0;i--){
        for(int j=1;j<m-1;j++){
            v[0][j].clear();
            //cout<<i<<" "<<j<<endl;
            ll x=a[i][j];
            ll y=t[i][j];
            while(y!=0 && x<a[i-1][j]){
                v[0][j].pb(y-1);
                //cout<<i<<" "<<j<<" "<<y-1<<endl;
                x=a[y][j];
                y=t[y][j];
            }
        }
        for(int k=1;k<=11;k++){
            for(int j=1;j<m-1;j++){
                if(j+(1<<(k-1))<=m){
                    S(v[k-1][j],v[k-1][j+(1<<(k-1))],n,v[k][j]);
                }
            }
        }
        for(int j=1;j<m-1;j++){
            ll x=a[i][j];
            ll y=d[i][j];
            while(y!=0 && x<a[i][j-1]){
                if(o[j][y-1]==0){
                    l[j][y-1]=i;
                }
                x=a[i][y];
                y=d[i][y];
            }
        //cout<<1<<endl;
            o[j]=0;
            x=a[i][j];
            y=d[i][j];
            while(y!=0 && x<a[i][j-1]){
                o[j][y-1]=1;
                ll ln=y-j;
                //cout<<y<<" "<<2<<" "<<p[ln]<<endl;
                //cout<<y<<" "<<2<<" "<<p[ln]<<endl;

                //cout<<l1<<endl;
                S(v[p[ln]][j],v[p[ln]][y-(1<<p[ln])],l[j][y-1],k1);
                res+=k1.size();
                x=a[i][y];
                y=d[i][y];
            }
        }
    }
    return res;
}

Compilation message (stderr)

rect.cpp: In function 'void S(std::vector<int>&, std::vector<int>&, ll, std::vector<int>&)':
rect.cpp:45:12: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     while(x<a1.size() && y<b1.size() && a1[x]<=z && b1[y]<=z){
      |           ~^~~~~~~~~~
rect.cpp:45:27: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     while(x<a1.size() && y<b1.size() && a1[x]<=z && b1[y]<=z){
      |                          ~^~~~~~~~~~

• 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