結果

問題 No.709 優勝可能性
ユーザー jupiro
提出日時 2020-01-15 13:01:33
言語 C++14
(gcc 9.2.0)
結果
AC  
実行時間 160 ms
コード長 1,718 Byte
コンパイル時間 1,308 ms
使用メモリ 24,092 KB
最終ジャッジ日時 2020-01-15 13:01:39

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
01.in AC 4 ms
3,336 KB
02.in AC 0 ms
3,364 KB
03.in AC 0 ms
3,404 KB
04.in AC 4 ms
3,384 KB
05.in AC 0 ms
3,364 KB
06.in AC 4 ms
3,496 KB
07.in AC 0 ms
3,360 KB
08.in AC 4 ms
3,376 KB
09.in AC 4 ms
3,268 KB
10.in AC 0 ms
3,528 KB
11.in AC 60 ms
9,372 KB
12.in AC 44 ms
9,204 KB
13.in AC 120 ms
12,648 KB
14.in AC 128 ms
15,472 KB
15.in AC 116 ms
15,256 KB
16.in AC 108 ms
15,672 KB
17.in AC 112 ms
16,724 KB
18.in AC 128 ms
24,092 KB
19.in AC 0 ms
3,448 KB
20.in AC 4 ms
3,388 KB
max_1.txt AC 160 ms
15,256 KB
max_2.txt AC 152 ms
15,288 KB
sample01.in AC 4 ms
3,356 KB
sample02.in AC 0 ms
3,304 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <cstdio>
#include <iostream>
#include <string>
#include <sstream>
#include <stack>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <cstdlib>
#include <bitset>
#include <tuple>
#include <assert.h>
#include <deque>
#include <bitset>
#include <iomanip>
#include <limits>
#include <chrono>
#include <random>
#include <array>
#include <unordered_map>
#include <functional>
#include <complex>

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const long long MAX = 5100000;
const long long INF = 1LL << 60;
const long long mod = 1000000007LL;
//const long long mod = 998244353LL;

using namespace std;
typedef unsigned long long ull;
typedef long long ll;


int main()
{
	/*
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	*/

	ll N, M; scanf("%lld %lld", &N, &M);
	vector<vector<ll>> R(N, vector<ll>(M));
	for (ll i = 0; i < N; i++) for (ll j = 0; j < M; j++) scanf("%lld", &R[i][j]);
	vector<map<ll, ll>> vm(M);
	vector<ll> deg(N);
	vector<stack<pair<ll, ll>>> vs(M);
	ll res = 0;
	for (ll i = 0; i < N; i++) {
		for (ll j = 0; j < M; j++) {
			if (vs[j].empty()) {
				vs[j].emplace(R[i][j], i);
				deg[i]++;
			}
			else {
				if (vs[j].top().first == R[i][j]) {
					vs[j].emplace(R[i][j], i);
					deg[i]++;
				}
				else if (vs[j].top().first < R[i][j]) {
					while (!vs[j].empty()) {
						deg[vs[j].top().second]--;
						if (deg[vs[j].top().second] == 0) res--;
						vs[j].pop();
					}
					vs[j].emplace(R[i][j], i);
					deg[i]++;
				}
			}
		}
		if (deg[i] > 0) res++;
		printf("%lld\n", res);

	}
	return 0;
}
0