Submission #848029

#	Time	Username	Problem	Language	Result	Execution time	Memory
848029		damwuan	Rectangles (IOI19_rect)	C++17	100 / 100	2334 ms	979688 KiB

rect

#include "rect.h"
#include<bits/stdc++.h>
#include <cstdio>
#include <unistd.h>
#include <cassert>
#include <string>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define for1(i,j,k) for(int i=j;i<=k;i++)
#define for2(i,j,k) for(int i=j;i>=k;i--)
#define for3(i,j,k,l) for(int i=j;i<=k;i+=l)
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
//#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=2500+5;
const ll offset=1e18;
const ll block_sz=317;
const ll inf=1e18;
const ll mod=1e9+7;
ll a[maxn][maxn];
vector<pii> R[maxn][maxn],D[maxn][maxn],qr[maxn][maxn];
ll ans;
ll st[maxn];

void Update(ll u,ll v)
{
    for(;u<=2500;u+=(u&-u))
    {
        st[u]+=v;
    }
}
ll Get1(ll u)
{
    ll r=0;
    for(;u>0;u-=(u&-u))
    {
        r+=st[u];
    }
    return r;
}
ll Get(ll l,ll r=2500)
{
    return Get1(r)-Get1(l-1);
}


class InputReader {
private:
	static const ll SIZE = 4096;

	ll inputFileDescriptor;
	char buf[SIZE];
	ll curChar;
	ll numChars;

public:

	inline InputReader(ll _inputFileDescriptor):
		inputFileDescriptor(_inputFileDescriptor),
		curChar(0),
		numChars(0) {
	}

	inline void close() {
		::close(inputFileDescriptor);
	}

	inline char read() {
		assert(numChars != -1);
		if (curChar >= numChars) {
			curChar = 0;
			numChars = ::read(inputFileDescriptor, buf, SIZE);
			if (numChars == -1)
				return -1;
		}
		return buf[curChar++];
	}

	inline ll readInt() {
		ll c = eatWhite();
		ll sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		ll res = 0;
		do {
			assert(c >= '0' && c <= '9');
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}

	inline string readString() {
		char c = eatWhite();
		string res;
		do {
			res += c;
			c = read();
		} while (!isSpaceChar(c));
		return res;
	}

	inline string readLine() {
		string res;
		while (true) {
			char c = read();
			if (c == '\n' || c == '\r' || c == -1)
				break;
			res += c;
		}
		return res;
	}

	inline char eatWhite() {
		char c = read();
		while (isSpaceChar(c))
			c = read();
		return c;
	}

	static inline bool isSpaceChar(char c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}
};


inline void solve(ll x,ll y)
{
    ll j=0;
    for(pii k:D[x][y])
    {
        while(j<R[x][y].size() && R[x][y][j].fi>=k.fi)
        {
            Update(R[x][y][j].se,1);
            j++;
        }
        ans+=Get1(k.se);
    }
    for1(i,0,j-1)
    {
        Update(R[x][y][i].se,-1);
    }
}

ll count_rectangles(vector<vector<int>> b)
{
    ll n=b.size();
    ll m=b[0].size();
    for1(i,1,n)
    {
        for1(j,1,m)
        {
            a[i][j]=b[i-1][j-1];
        }
    }
    vector<ll> stk;
    for1(i,1,n)
    {
        stk.clear();
        for1(j,1,m)
        {
            while (!stk.empty() && a[i][stk.back()]<a[i][j]) stk.pop_back();
            if(!stk.empty() && stk.back()!=j-1)
            {
                R[i][stk.back()+1].pb({j-1-stk.back(),1});
                //if (i==6) cerr<<"wtf "<< j<<'\n';
            }
            stk.pb(j);
        }
        stk.clear();
        for2(j,m,1)
        {
            while (!stk.empty() && a[i][stk.back()]<a[i][j]) stk.pop_back();
            if(!stk.empty() && stk.back()!=j+1 && a[i][j]!=a[i][stk.back()])
            {
                R[i][j+1].pb({stk.back()-j-1,1});
            }
            stk.pb(j);
        }
    }

    for1(j,1,m)
    {
        stk.clear();
        for1(i,1,n)
        {
            while (!stk.empty() && a[stk.back()][j]<a[i][j]) stk.pop_back();
            if(!stk.empty() && stk.back()!=i-1)
            {
                D[stk.back()+1][j].pb({i-1-stk.back(),1});
            }
            stk.pb(i);
        }
        stk.clear();
        for2(i,n,1)
        {
            while (!stk.empty() && a[stk.back()][j]<a[i][j]) stk.pop_back();
            if(!stk.empty() && stk.back()!=i+1 && a[i][j] != a[stk.back()][j])
            {
                D[i+1][j].pb({stk.back()-1-i,1});
            }
            stk.pb(i);
        }
    }

    for1(i,1,n)
    {
        for1(j,1,m)
        {
            sort(all(R[i][j]));
            sort(all(D[i][j]));
        }
    }
    for2(i,n,1)
    {
        for2(j,m,1)
        {
            if(i<n)
            {
                for(pii& x: R[i][j])
                {
                    auto y=lower_bound(all(R[i+1][j]),x);
                    if (y!=R[i+1][j].end() && y->fi==x.fi) x.se=y->se+1;
//                    if (i==5 && j==2)
//                    {
//                        cerr<<x.fi<<' '<<x.se<<' '<<y->fi<<' '<<y->se<<'\n';
//                    }
                }
            }
            if(j<m)
            {
                for(pii& x: D[i][j])
                {
                    auto y=lower_bound(all(D[i][j+1]),x);
                    if (y!=D[i][j+1].end() && y->fi==x.fi) x.se=y->se+1;
                }
            }
        }

    }
    for1(i,1,n)
    {
        for1(j,1,m)
        {
            for(pii& x: R[i][j])
            {
                swap(x.fi,x.se);
            }
            sort(all(R[i][j]),greater<pii>());
            reverse(all(D[i][j]));
        }
    }
    for1(i,0,n-1)
    {
        for1(j,0,m-1)
        {
            solve(i,j);
            //cerr<< i<< ' '<<j<<' '<<ans<<'\n';
        }
    }
//    for(auto v: D[2][6]) cerr << v.fi<<' '<<v.se<<'\n';
//    solve(2,2);
    return ans;
}
//
//int32_t main() {
//    freopen("IOI19_rect.inp","r",stdin);
//    freopen("IOI19_rect.out","w",stdout);
//	InputReader inputReader(STDIN_FILENO);
//	ll n, m;
//	n = inputReader.readInt();
//	m = inputReader.readInt();
//	vector<vector<int>> a(n, vector<int>(m));
//	for (int i = 0; i < n; i++)	{
//		for (int j = 0; j < m; j++) {
//			a[i][j] = inputReader.readInt();
//		}
//	}
//	inputReader.close();
//
//	long long result = count_rectangles(a);
//
//	printf("%lld\n", result);
//	fclose(stdout);
//	return 0;
//}
/*

10 6
0 1 0 0 1 1
1 0 0 1 1 0
0 1 1 0 0 1
1 0 1 1 0 0
0 1 1 1 1 1
1 0 0 1 1 1
0 0 0 0 0 0
1 1 1 1 1 1
1 0 0 1 1 0
1 0 1 0 0 1

*/

Compilation message (stderr)

rect.cpp: In function 'void solve(ll, ll)':
rect.cpp:144:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |         while(j<R[x][y].size() && R[x][y][j].fi>=k.fi)
      |               ~^~~~~~~~~~~~~~~

• 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