oj.uz

Submission #145555

# Submission time Handle Problem Language Result Execution time Memory
145555 2019-08-20T11:41:05 Z peijar Bob (COCI14_bob) C++14
120 / 120
 190 ms 33500 KB 
#include <bits/stdc++.h>
using namespace std;

#define FOR(i, j, n) for (int i(j); i < n; ++i)
#define FORR(v, c) for (auto &v : c)
#define F first
#define S second
#define SQ(x) (x)*(x)
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define rall(c) (c).rbegin(), (c).rend()
#define dbg(x) cerr<<#x<<" = " << (x) << endl
#define pnl(x) cout << x << '\n'
#define pns(x) cout << x << ' '
#define read(x) cin >> x
#define read2(x,y) cin >> x >> y
#define read3(x, y, z) cin >> x >> y >> z
#define read4(a, b, c, d) cin >> a >> b >> c >> d
#define readv(v) FORR(c,v) read(c)

struct Arrete { int v, c;};
struct Point {int x, y; double distance(Point other) const {return sqrt(SQ(x-other.x)+SQ(y-other.y));}};

typedef	vector<int>	vi;
typedef pair<int,int>	ii;
typedef vector<string>	vs;
typedef vector<ii>	vii;
typedef vector<Arrete>	vg;
typedef vector<long long>	vl;
typedef	long long ll;

const int MAXN = 1e3;

ll height[MAXN][MAXN];
ll lowest[MAXN][MAXN];
ll largest[MAXN][MAXN];
int N,M;

struct Situation
{
	ll wid, low;
};

int		main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	read2(N,M);
	FOR(i,0,N) FOR(j,0,M)
		read(height[i][j]);
	
	for (int col(0); col < M; ++col)
	{
		lowest[N-1][col] = 1;
		for (int line(N-2); line >= 0; --line)
		{
			if (height[line][col] == height[line+1][col])
				lowest[line][col] = lowest[line+1][col]+1;
			else
				lowest[line][col] = 1;
		}
	}

	for (int line(0); line < N; ++line)
	{
		largest[line][0] = 1;
		for (int col(1); col < M; ++col)
		{
			if (height[line][col-1] == height[line][col] && lowest[line][col] == lowest[line][col-1])
				largest[line][col] = 1 + largest[line][col-1];
			else
				largest[line][col] = 1;
		}
	}

	ll ans(0);

	for (int line(0); line < N; ++line)
	{
		stack<Situation> S;
		int prev_h = -1;
		ll to_add = 0;
		int col = M-1;
		while (col >= 0)
		{
			ans += lowest[line][col] * ((largest[line][col] * (largest[line][col] + 1)) / 2);
			Situation cur = {largest[line][col], lowest[line][col]};
			if (prev_h != height[line][col])
			{
				while (!S.empty())
					S.pop();
				to_add = 0;
				prev_h = height[line][col];
			}
			else
			{
				while (!S.empty() && S.top().low >= cur.low)
				{
					Situation node = S.top();
					S.pop();
					cur.wid += node.wid;
					to_add -= node.wid * node.low;
				}
				ans += largest[line][col] * to_add + largest[line][col] * (cur.wid - largest[line][col]) * cur.low;
			}
			S.push(cur);
			to_add += cur.wid * cur.low;
			col -= largest[line][col];
		}
	}

	pnl(ans);
}

Subtask #1
12.0 / 12.0

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

Subtask #2
12.0 / 12.0

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

Subtask #3
12.0 / 12.0

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

Subtask #4
12.0 / 12.0

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

Subtask #5
12.0 / 12.0

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

Subtask #6
12.0 / 12.0

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

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 172 ms 30548 KB Output is correct
2 Correct 103 ms 25720 KB Output is correct
3 Correct 99 ms 25820 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 33500 KB Output is correct
2 Correct 105 ms 25848 KB Output is correct
3 Correct 98 ms 25748 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 33396 KB Output is correct
2 Correct 105 ms 25700 KB Output is correct
3 Correct 111 ms 25860 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 33472 KB Output is correct
2 Correct 99 ms 25824 KB Output is correct
3 Correct 96 ms 25724 KB Output is correct