oj.uz

Submission #848029

# Submission time Handle Problem Language Result Execution time Memory
848029 2023-09-11T05:41:02 Z damwuan Rectangles (IOI19_rect) C++17
100 / 100
 2334 ms 979688 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 443728 KB Output is correct
2 Correct 93 ms 443744 KB Output is correct
3 Correct 94 ms 443728 KB Output is correct
4 Correct 93 ms 443728 KB Output is correct
5 Correct 95 ms 443664 KB Output is correct
6 Correct 93 ms 443800 KB Output is correct
7 Correct 93 ms 443692 KB Output is correct
8 Correct 92 ms 443728 KB Output is correct
9 Correct 94 ms 443704 KB Output is correct
10 Correct 93 ms 443732 KB Output is correct
11 Correct 93 ms 443732 KB Output is correct
12 Correct 95 ms 443632 KB Output is correct
13 Correct 94 ms 443728 KB Output is correct
14 Correct 93 ms 443724 KB Output is correct
15 Correct 92 ms 443708 KB Output is correct
16 Correct 99 ms 443728 KB Output is correct
17 Correct 93 ms 443604 KB Output is correct
18 Correct 92 ms 443728 KB Output is correct
19 Correct 95 ms 443632 KB Output is correct
20 Correct 93 ms 443732 KB Output is correct
21 Correct 95 ms 443728 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 443728 KB Output is correct
2 Correct 93 ms 443744 KB Output is correct
3 Correct 94 ms 443728 KB Output is correct
4 Correct 93 ms 443728 KB Output is correct
5 Correct 95 ms 443664 KB Output is correct
6 Correct 93 ms 443800 KB Output is correct
7 Correct 93 ms 443692 KB Output is correct
8 Correct 92 ms 443728 KB Output is correct
9 Correct 94 ms 443704 KB Output is correct
10 Correct 93 ms 443732 KB Output is correct
11 Correct 93 ms 443732 KB Output is correct
12 Correct 95 ms 443632 KB Output is correct
13 Correct 94 ms 443728 KB Output is correct
14 Correct 93 ms 443724 KB Output is correct
15 Correct 92 ms 443708 KB Output is correct
16 Correct 99 ms 443728 KB Output is correct
17 Correct 93 ms 443604 KB Output is correct
18 Correct 92 ms 443728 KB Output is correct
19 Correct 95 ms 443632 KB Output is correct
20 Correct 93 ms 443732 KB Output is correct
21 Correct 95 ms 443728 KB Output is correct
22 Correct 94 ms 446288 KB Output is correct
23 Correct 94 ms 446244 KB Output is correct
24 Correct 96 ms 446288 KB Output is correct
25 Correct 93 ms 445892 KB Output is correct
26 Correct 95 ms 446072 KB Output is correct
27 Correct 95 ms 446032 KB Output is correct
28 Correct 95 ms 446032 KB Output is correct
29 Correct 93 ms 445768 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 443728 KB Output is correct
2 Correct 93 ms 443744 KB Output is correct
3 Correct 94 ms 443728 KB Output is correct
4 Correct 93 ms 443728 KB Output is correct
5 Correct 95 ms 443664 KB Output is correct
6 Correct 93 ms 443800 KB Output is correct
7 Correct 93 ms 443692 KB Output is correct
8 Correct 92 ms 443728 KB Output is correct
9 Correct 94 ms 443704 KB Output is correct
10 Correct 93 ms 443732 KB Output is correct
11 Correct 93 ms 443732 KB Output is correct
12 Correct 95 ms 443632 KB Output is correct
13 Correct 94 ms 443728 KB Output is correct
14 Correct 93 ms 443724 KB Output is correct
15 Correct 92 ms 443708 KB Output is correct
16 Correct 99 ms 443728 KB Output is correct
17 Correct 94 ms 446288 KB Output is correct
18 Correct 94 ms 446244 KB Output is correct
19 Correct 96 ms 446288 KB Output is correct
20 Correct 93 ms 445892 KB Output is correct
21 Correct 95 ms 446072 KB Output is correct
22 Correct 95 ms 446032 KB Output is correct
23 Correct 95 ms 446032 KB Output is correct
24 Correct 93 ms 445768 KB Output is correct
25 Correct 93 ms 443604 KB Output is correct
26 Correct 92 ms 443728 KB Output is correct
27 Correct 95 ms 443632 KB Output is correct
28 Correct 93 ms 443732 KB Output is correct
29 Correct 95 ms 443728 KB Output is correct
30 Correct 101 ms 450736 KB Output is correct
31 Correct 101 ms 450860 KB Output is correct
32 Correct 100 ms 450896 KB Output is correct
33 Correct 99 ms 448900 KB Output is correct
34 Correct 106 ms 449920 KB Output is correct
35 Correct 104 ms 449788 KB Output is correct
36 Correct 105 ms 449616 KB Output is correct
37 Correct 107 ms 449872 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 443728 KB Output is correct
2 Correct 93 ms 443744 KB Output is correct
3 Correct 94 ms 443728 KB Output is correct
4 Correct 93 ms 443728 KB Output is correct
5 Correct 95 ms 443664 KB Output is correct
6 Correct 93 ms 443800 KB Output is correct
7 Correct 93 ms 443692 KB Output is correct
8 Correct 92 ms 443728 KB Output is correct
9 Correct 94 ms 443704 KB Output is correct
10 Correct 93 ms 443732 KB Output is correct
11 Correct 93 ms 443732 KB Output is correct
12 Correct 95 ms 443632 KB Output is correct
13 Correct 94 ms 443728 KB Output is correct
14 Correct 93 ms 443724 KB Output is correct
15 Correct 92 ms 443708 KB Output is correct
16 Correct 99 ms 443728 KB Output is correct
17 Correct 94 ms 446288 KB Output is correct
18 Correct 94 ms 446244 KB Output is correct
19 Correct 96 ms 446288 KB Output is correct
20 Correct 93 ms 445892 KB Output is correct
21 Correct 95 ms 446072 KB Output is correct
22 Correct 95 ms 446032 KB Output is correct
23 Correct 95 ms 446032 KB Output is correct
24 Correct 93 ms 445768 KB Output is correct
25 Correct 101 ms 450736 KB Output is correct
26 Correct 101 ms 450860 KB Output is correct
27 Correct 100 ms 450896 KB Output is correct
28 Correct 99 ms 448900 KB Output is correct
29 Correct 106 ms 449920 KB Output is correct
30 Correct 104 ms 449788 KB Output is correct
31 Correct 105 ms 449616 KB Output is correct
32 Correct 107 ms 449872 KB Output is correct
33 Correct 93 ms 443604 KB Output is correct
34 Correct 92 ms 443728 KB Output is correct
35 Correct 95 ms 443632 KB Output is correct
36 Correct 93 ms 443732 KB Output is correct
37 Correct 95 ms 443728 KB Output is correct
38 Correct 151 ms 480336 KB Output is correct
39 Correct 155 ms 475472 KB Output is correct
40 Correct 139 ms 475472 KB Output is correct
41 Correct 142 ms 470868 KB Output is correct
42 Correct 185 ms 495696 KB Output is correct
43 Correct 190 ms 495852 KB Output is correct
44 Correct 188 ms 496100 KB Output is correct
45 Correct 180 ms 491808 KB Output is correct
46 Correct 152 ms 470556 KB Output is correct
47 Correct 178 ms 472992 KB Output is correct
48 Correct 263 ms 481616 KB Output is correct
49 Correct 254 ms 483664 KB Output is correct
50 Correct 172 ms 470872 KB Output is correct
51 Correct 169 ms 462680 KB Output is correct
52 Correct 249 ms 481360 KB Output is correct
53 Correct 250 ms 482384 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 444240 KB Output is correct
2 Correct 94 ms 444200 KB Output is correct
3 Correct 93 ms 443672 KB Output is correct
4 Correct 93 ms 443728 KB Output is correct
5 Correct 95 ms 443984 KB Output is correct
6 Correct 94 ms 443988 KB Output is correct
7 Correct 94 ms 443984 KB Output is correct
8 Correct 100 ms 443984 KB Output is correct
9 Correct 97 ms 443984 KB Output is correct
10 Correct 93 ms 443760 KB Output is correct
11 Correct 93 ms 443728 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 443604 KB Output is correct
2 Correct 92 ms 443728 KB Output is correct
3 Correct 95 ms 443632 KB Output is correct
4 Correct 93 ms 443732 KB Output is correct
5 Correct 95 ms 443728 KB Output is correct
6 Correct 98 ms 443728 KB Output is correct
7 Correct 459 ms 535628 KB Output is correct
8 Correct 898 ms 649236 KB Output is correct
9 Correct 904 ms 650320 KB Output is correct
10 Correct 901 ms 650616 KB Output is correct
11 Correct 210 ms 498948 KB Output is correct
12 Correct 325 ms 548944 KB Output is correct
13 Correct 352 ms 552952 KB Output is correct

Subtask #7
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 443728 KB Output is correct
2 Correct 93 ms 443744 KB Output is correct
3 Correct 94 ms 443728 KB Output is correct
4 Correct 93 ms 443728 KB Output is correct
5 Correct 95 ms 443664 KB Output is correct
6 Correct 93 ms 443800 KB Output is correct
7 Correct 93 ms 443692 KB Output is correct
8 Correct 92 ms 443728 KB Output is correct
9 Correct 94 ms 443704 KB Output is correct
10 Correct 93 ms 443732 KB Output is correct
11 Correct 93 ms 443732 KB Output is correct
12 Correct 95 ms 443632 KB Output is correct
13 Correct 94 ms 443728 KB Output is correct
14 Correct 93 ms 443724 KB Output is correct
15 Correct 92 ms 443708 KB Output is correct
16 Correct 99 ms 443728 KB Output is correct
17 Correct 94 ms 446288 KB Output is correct
18 Correct 94 ms 446244 KB Output is correct
19 Correct 96 ms 446288 KB Output is correct
20 Correct 93 ms 445892 KB Output is correct
21 Correct 95 ms 446072 KB Output is correct
22 Correct 95 ms 446032 KB Output is correct
23 Correct 95 ms 446032 KB Output is correct
24 Correct 93 ms 445768 KB Output is correct
25 Correct 101 ms 450736 KB Output is correct
26 Correct 101 ms 450860 KB Output is correct
27 Correct 100 ms 450896 KB Output is correct
28 Correct 99 ms 448900 KB Output is correct
29 Correct 106 ms 449920 KB Output is correct
30 Correct 104 ms 449788 KB Output is correct
31 Correct 105 ms 449616 KB Output is correct
32 Correct 107 ms 449872 KB Output is correct
33 Correct 151 ms 480336 KB Output is correct
34 Correct 155 ms 475472 KB Output is correct
35 Correct 139 ms 475472 KB Output is correct
36 Correct 142 ms 470868 KB Output is correct
37 Correct 185 ms 495696 KB Output is correct
38 Correct 190 ms 495852 KB Output is correct
39 Correct 188 ms 496100 KB Output is correct
40 Correct 180 ms 491808 KB Output is correct
41 Correct 152 ms 470556 KB Output is correct
42 Correct 178 ms 472992 KB Output is correct
43 Correct 263 ms 481616 KB Output is correct
44 Correct 254 ms 483664 KB Output is correct
45 Correct 172 ms 470872 KB Output is correct
46 Correct 169 ms 462680 KB Output is correct
47 Correct 249 ms 481360 KB Output is correct
48 Correct 250 ms 482384 KB Output is correct
49 Correct 93 ms 444240 KB Output is correct
50 Correct 94 ms 444200 KB Output is correct
51 Correct 93 ms 443672 KB Output is correct
52 Correct 93 ms 443728 KB Output is correct
53 Correct 95 ms 443984 KB Output is correct
54 Correct 94 ms 443988 KB Output is correct
55 Correct 94 ms 443984 KB Output is correct
56 Correct 100 ms 443984 KB Output is correct
57 Correct 97 ms 443984 KB Output is correct
58 Correct 93 ms 443760 KB Output is correct
59 Correct 93 ms 443728 KB Output is correct
60 Correct 98 ms 443728 KB Output is correct
61 Correct 459 ms 535628 KB Output is correct
62 Correct 898 ms 649236 KB Output is correct
63 Correct 904 ms 650320 KB Output is correct
64 Correct 901 ms 650616 KB Output is correct
65 Correct 210 ms 498948 KB Output is correct
66 Correct 325 ms 548944 KB Output is correct
67 Correct 352 ms 552952 KB Output is correct
68 Correct 93 ms 443604 KB Output is correct
69 Correct 92 ms 443728 KB Output is correct
70 Correct 95 ms 443632 KB Output is correct
71 Correct 93 ms 443732 KB Output is correct
72 Correct 95 ms 443728 KB Output is correct
73 Correct 893 ms 782880 KB Output is correct
74 Correct 1131 ms 715896 KB Output is correct
75 Correct 676 ms 715640 KB Output is correct
76 Correct 659 ms 648568 KB Output is correct
77 Correct 1858 ms 979656 KB Output is correct
78 Correct 1346 ms 653960 KB Output is correct
79 Correct 1468 ms 691476 KB Output is correct
80 Correct 2286 ms 794356 KB Output is correct
81 Correct 1391 ms 670380 KB Output is correct
82 Correct 1837 ms 755544 KB Output is correct
83 Correct 2334 ms 821352 KB Output is correct
84 Correct 1325 ms 652544 KB Output is correct
85 Correct 2202 ms 805368 KB Output is correct
86 Correct 2104 ms 795416 KB Output is correct
87 Correct 931 ms 784360 KB Output is correct
88 Correct 1947 ms 978984 KB Output is correct
89 Correct 1824 ms 979604 KB Output is correct
90 Correct 1735 ms 979688 KB Output is correct