Submission #1236364

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236364		altern23	Bob (COCI14_bob)	C++20	120 / 120	171 ms	48264 KiB

bob

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define pii pair<ll, ll>
#define fi first
#define sec second

const int MAXN = 1e3;
const ll INF = 2e18;

ll A[MAXN + 5][MAXN + 5], lst[MAXN + 5][MAXN + 5];

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int tc = 1;
	// cin >> tc;
	for(;tc--;){
		ll N, M; cin >> N >> M;
		vector<ll> v;
		for(int i = 1; i <= N; i++){
			for(int j = 1; j <= M; j++){
				cin >> A[i][j];
				v.push_back(A[i][j]);
			}
		}
		
		sort(v.begin(), v.end());
		v.erase(unique(v.begin(), v.end()), v.end());
		
		ll K = v.size();
		vector<pii> pos[K + 5];
		
		for(int i = 1; i <= N; i++){
			for(int j = 1; j <= M; j++){
				A[i][j] = lower_bound(v.begin(), v.end(), A[i][j]) - v.begin() + 1;
				pos[A[i][j]].push_back({i, j});
			}
		}
		
		for(int i = 1; i <= M; i++){
			for(int j = 1; j <= N; j++){
				if(A[j][i] != A[j - 1][i]) lst[j][i] = j - 1;
				else lst[j][i] = lst[j - 1][i];
			}
		}
		
		ll ans = 0;
		for(int color = 1; color <= K; color++){
			stack<pii> stk;
			ll lst_i = 0, lst_j = 0;
			ll cur = 0;
			for(auto [i, j] : pos[color]){
				if(i != lst_i || j - 1 != lst_j){
					cur = 0;
					while(!stk.empty()) stk.pop();
				}
				ll size = 1;
				while(!stk.empty() && stk.top().fi < lst[i][j]){
					size += stk.top().sec;
					cur -= (i - stk.top().fi) * stk.top().sec;
					stk.pop();
				}
				cur += (i - lst[i][j]) * size;
				stk.push({lst[i][j], size});
				ans += cur;
				
				lst_i = i, lst_j = j;
			}
		} 
		
		cout << ans << "\n";
	}
}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 12 / 12
• Subtask 6: 12 / 12
• Subtask 7: 12 / 12
• Subtask 8: 12 / 12
• Subtask 9: 12 / 12
• Subtask 10: 12 / 12