| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 848008 | damwuan | Rectangles (IOI19_rect) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
int a[maxn][maxn];
vector<pii> R[maxn][maxn],D[maxn][maxn],qr[maxn][maxn];
ll ans;
ll st[maxn];
void Update(int u,int v)
{
for(;u<=2500;u+=(u&-u))
{
st[u]+=v;
}
}
ll Get1(int u)
{
ll r=0;
for(;u>0;u-=(u&-u))
{
r+=st[u];
}
return r;
}
ll Get(int l,int r=2500)
{
return Get1(r)-Get1(l-1);
}
class InputReader {
private:
static const int SIZE = 4096;
int inputFileDescriptor;
char buf[SIZE];
int curChar;
int numChars;
public:
inline InputReader(int _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 int readInt() {
int c = eatWhite();
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int 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(int x,int y)
{
int 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,R[x][y][j].fi);
j++;
}
ans+=((ll)k.se)*Get(k.se);
}
for1(i,0,j-1)
{
Update(R[x][y][i].se,-R[x][y][i].fi);
}
}
ll count_rectangles(vector<vector<int>> b)
{
int n=b.size();
int m=b[0].size();
for1(i,1,n)
{
for1(j,1,m)
{
a[i][j]=b[i-1][j-1];
}
}
vector<int> 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});
}
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(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(j,1,m)
{
for(pii& x: R[i][j])
{
swap(x.fi,x.se);
}
sort(all(R[i][j]));
}
}
for1(i,1,n)
{
for1(j,1,m)
{
solve(i,j);
}
}
// for(auto v: D[2][2]) cout << v.fi<<' '<<v.se<<'\n';
// solve(2,2);
return ans;
}
//int32_t main() {
// InputReader inputReader(STDIN_FILENO);
// int 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;
//}
/*
3 1
12345678
?11
*/