Hatena::Grouptopcoder

shnyaの参戦記録

2011-05-29練習

SRM 469 Div1 Easy 02:48  [http://www.topcoder.com/stat?c=problem_statement&pm=10898&rd=14152:title=SRM 469 Div1 Easy] - shnyaの参戦記録 を含むブックマーク はてなブックマーク -  [http://www.topcoder.com/stat?c=problem_statement&pm=10898&rd=14152:title=SRM 469 Div1 Easy] - shnyaの参戦記録

10億x10億も座席があるという映画館なんてねーよとか思いながら解く。

#define SORT(c) sort((c).begin(),(c).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define SZ(a) int((a).size())

class TheMoviesLevelOneDivOne {
public:
  long long find( int n, int m, vector <int> row, vector <int> seat ) {
    multimap<LLI,LLI> s;
    REP(i,SZ(row)){
      s.insert(make_pair(row[i],seat[i]));
    }
    SORT(row);
    row.erase(unique(ALL(row)),row.end());
    if(m < 2) return 0;
    LLI res = 0;
    REP(i,SZ(row)){
      vector<LLI> v;
      for(multimap<LLI,LLI>::iterator itr = s.lower_bound(row[i]);
          itr != s.upper_bound(row[i]); itr++){
        v.push_back(itr->second);
      }
      SORT(v);
      LLI k = 1;
      REP(i,SZ(v)){
        if(v[i] - k > 1){
          res += v[i] - k - 1;
        }
        k = v[i] + 1;
      }
      if(m - v.back() > 1){
        res += m - v.back() - 1;
      }
    }
    res += (n - (LLI)SZ(row)) * (m - 1);
    return res;
  }
};