oj.uz

Submission #874707

# Submission time Handle Problem Language Result Execution time Memory
874707 2023-11-17T16:32:30 Z aaron_dcoder Bob (COCI14_bob) C++17
120 / 120
 168 ms 18080 KB 
#define NDEBUG

#ifdef NDEBUG
#define dbg(TXTMSG) if constexpr (false) cerr << "lol"
#define dbgv(VARN) ((void)0)
#define dbgfor(COND) if constexpr (false) for (COND)

#else
#define _GLIBCXX_DEBUG 1
#define _GLIBCXX_DEBUG_PEDANTIC 1
#pragma GCC optimize("trapv")
#define dbg(TXTMSG) cerr << "\n" << TXTMSG
#define dbgv(VARN) cerr << "\n" << #VARN << " = "<< VARN << ", line: " << __LINE__ << "\n"
#define dbgfor(COND) for (COND)

#endif

#include <bits/stdc++.h>
using namespace std;
using ll = long long; 
using pll = pair<ll,ll>;
#define e0 first
#define e1 second
constexpr ll INFTY = 2e18;

ll numrects(ll b, ll e, const vector<ll>& data) {
	ll s = e-b+1;

	vector<array<pll,12>> stable(s);
	
	
	for (ll i = 0; i < s; ++i)
	{
		stable[i][0] = {data[b+i], i+1};
	}
	for (ll p = 1; p < 12; ++p)
	{
		for (ll i = 0; i+(1<<(p-1)) < s; ++i)
		{
			stable[i][p] = min(stable[i][p-1], stable[i+(1<<(p-1))][p-1]);
		}
	}

	ll o=0;

	for (ll i = 0; i < s; ++i)
	{
		ll currr = i+1;
		for (ll p = 11; p >= 0; --p)
		{
			//dbg(p << " " << stable[currr][p].e0);
			if (currr<s && stable[currr][p] >= pll{data[b+i], i+1}) 
			{
				currr += (1<<p);
			}
		}

		ll currl = i-1;
		for (ll p = 11; p >= 0; --p)
		{

			if (( currl-(1<<p)+1>=0)&& stable[currl-(1<<p)+1][p] >= pll{data[b+i], i+1}) 
			{
				currl -= (1<<p);
			}
		}
		dbg(i << ":" << currl << " " << currr);
		o += data[b+i]*(i-currl)*(currr-i);
	}
	return o;
}


int main() {
	cin.tie(nullptr);
	ios_base::sync_with_stdio(false);
	dbgv(numrects(0,3,{1,2,3,4}));

	ll N,M;
	cin >> N >> M;

	vector<vector<ll>> H(N,vector<ll>(M,-1));

	set<ll> posheights;

	for (ll y = 0; y < N; ++y)
	{
		for (ll x = 0; x < M; ++x)
		{
			cin >> H[y][x];
		}
	}

	ll outp=0;

	vector<ll> uprun(M,1);
	for (ll y = 0; y < N; ++y)
	{
		if (y!=0) {
			for (ll x = 0; x < M; ++x)
			{
				if (H[y][x]==H[y-1][x]) {
					uprun[x]++;
				}
				else {
					uprun[x]=1;
				}
			}
		}

		ll runstart=0;
		for (ll x = 1; x < M; ++x)
		{
			if (H[y][x]!=H[y][x-1]) {
				outp+=numrects(runstart,x-1, uprun);
				runstart=x;
			}
		}
		outp+=numrects(runstart,M-1,uprun);
	}

	cout << outp;


	

}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 2924 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3420 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 3564 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3420 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 14960 KB Output is correct
2 Correct 131 ms 10456 KB Output is correct
3 Correct 117 ms 10284 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 18080 KB Output is correct
2 Correct 116 ms 10396 KB Output is correct
3 Correct 127 ms 10656 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 17912 KB Output is correct
2 Correct 119 ms 10400 KB Output is correct
3 Correct 123 ms 10440 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 17892 KB Output is correct
2 Correct 117 ms 10392 KB Output is correct
3 Correct 126 ms 10388 KB Output is correct