結果

問題 No.709 優勝可能性
ユーザー Arumakan1727Arumakan1727
提出日時 2018-12-02 01:10:51
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 133 ms / 3,500 ms
コード長 3,173 bytes
コンパイル時間 1,631 ms
コンパイル使用メモリ 172,236 KB
実行使用メモリ 12,392 KB
最終ジャッジ日時 2024-06-27 05:07:48
合計ジャッジ時間 4,146 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
7,552 KB
testcase_01 AC 5 ms
7,552 KB
testcase_02 AC 5 ms
7,424 KB
testcase_03 AC 5 ms
7,424 KB
testcase_04 AC 5 ms
7,424 KB
testcase_05 AC 5 ms
7,552 KB
testcase_06 AC 5 ms
7,552 KB
testcase_07 AC 5 ms
7,552 KB
testcase_08 AC 5 ms
7,552 KB
testcase_09 AC 5 ms
7,552 KB
testcase_10 AC 50 ms
12,252 KB
testcase_11 AC 25 ms
12,136 KB
testcase_12 AC 97 ms
12,080 KB
testcase_13 AC 96 ms
12,256 KB
testcase_14 AC 86 ms
12,180 KB
testcase_15 AC 80 ms
12,188 KB
testcase_16 AC 76 ms
12,392 KB
testcase_17 AC 75 ms
12,208 KB
testcase_18 AC 6 ms
7,424 KB
testcase_19 AC 5 ms
7,680 KB
testcase_20 AC 131 ms
12,044 KB
testcase_21 AC 133 ms
11,976 KB
testcase_22 AC 5 ms
7,552 KB
testcase_23 AC 5 ms
7,552 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h" // {{{
using namespace std; typedef long long ll; typedef pair<int,int> pii;
#define val         const auto
#define eb          emplace_back
#define emp         emplace
#define fi          first
#define se          second
#define outl(x)     cout << (x) << '\n'
#define reps(i,s,n) for(int i=(s); i < (int)(n); ++i)
#define rep(i,n)    reps(i,0,n)
#define repr(i,h,l) for(int i=(h); i >= (int)(l); --i)
#define ALL(x)      begin(x), end(x)
#define TMPLT(T,U)  template<class T, class U>
#define ten(p)      ((long long)(1e##p))
#define FILL(a,v)   memset((a), (v), sizeof(a))
#ifdef  DEBUG
#define debug(...)  fprintf(stderr, __VA_ARGS__)
#define show(x)     clog << #x << " \t\t= " << (x) << '\n'
#define show2(x,y)  clog << '(' << #x << ',' << #y << ")\t\t= " << '(' << (x) << "\t, " << (y) << ")\n"
#define LN()        fputs("\n--------------------------------\n", stderr)
#else
#define debug(...)
#define show(x)
#define show2(x,y)
#define LN()
#endif
#define def(op) inline bool operator op (const T &that) const { return comp(that) op 0; }
template<class T> struct Ordered
{ virtual int comp(const T &that) const = 0; def(==); def(!=); def(<); def(<=); def(>); def(>=); };
#undef def
namespace {
  TMPLT(T,U) inline constexpr common_type_t<T,U> gcd(T x, U y)
  { return (x<y)? gcd(y,x) : (y <= 0)? x : gcd(y, x % y); }
  TMPLT(T,U) inline bool chmax(T &a, const U &b){return b>a ? a=b,1 : 0;}
  TMPLT(T,U) inline bool chmin(T &a, const U &b){return b<a ? a=b,1 : 0;}
  TMPLT(T,U) inline constexpr ll lcm(T x, U y) { return (ll)x/gcd(x,y) * y; }
  template<class Itr> string mkString(Itr begin, Itr end, const char *sp = " ") {
    static ostringstream oss; oss.str("");
    for(Itr i=begin; i != end; ++i) { if(i != begin)oss << sp; oss << *i; }
    return oss.str();
  }
  constexpr int INF = 0x3f3f3f3f; constexpr ll LINF = 0x3f3f3f3f3f3f3f3fLL;
  // }}}

constexpr int MX = ten(5) + 10;

struct Stack
{
  int idx = 0;
  vector<int> buf;
  Stack(): buf(MX) {}

  void push(int x){ buf[idx++] = x; }
  int  pop()      { return buf[--idx]; }
  int  top()      { return buf[idx-1]; }
  bool empty()    { return idx <= 0; }
};

void _main(const vector<char*> &args)
{
  int N, M;
  static int r[MX][11];
  static int cnt[MX] = {};

  cin >> N >> M;
  reps(i, 1, N+1) rep(j, M) cin >> r[i][j];

  Stack tops[11];
  rep(i, M) {
    r[0][i] = -1;
    tops[i].push(0);
  }
  cnt[0] = M;

  int ans = 1;
  for (int i = 1; i <= N; ++i) {
    rep(j, M) {

      val R = r[i][j];
      Stack &top = tops[j];

      if (R > r[top.top()][j]) {
        while( !top.empty() )
        {
          val idx = top.pop();
          --cnt[idx];
          if (cnt[idx] <= 0) {
            cnt[idx] = 0;
            --ans;
          }
        }
        top.push(i);
        ++cnt[i];
      }
      else if (R == r[top.top()][j]) {
        top.push(i);
        ++cnt[i];
      }

    }
    if (cnt[i] > 0) {
      ++ans;
    }
    outl(ans);
  }

}

} // {{{
signed main(signed argc, char *argv[]) {
#ifndef DEBUG
  ios::sync_with_stdio(false); cin.tie(nullptr);
#endif
  cout << fixed << setprecision(9); _main(vector<char*>(argv, argv+argc)); return 0;
} // }}}
0