SRM468 Div1 250 TheMovieLevelOneDivOne

問題

• n*mの座席から並んだ2席を予約したい
• 最大47席が予約済みなので，予約の仕方は何通りあるかを答える
• nもmも最大10億

解法

• 数え上げるだけの簡単なお仕事
• 答えがlong longになる事にだけ注意する

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

class TheMoviesLevelOneDivOne{
public:
    long long find(int n, int m, vector<int> row, vector<int> seat){
        map<int, vector<int> > S;
        for(int i=0;i<row.size();i++){
            if(!S.count(row[i])) S[row[i]] = vector<int>();
            S[row[i]].push_back(seat[i]);
        }
        long long ans = 0;
        map<int, vector<int> >::iterator it = S.begin();
        while(it != S.end()){
            vector<int> vi = it->second;
            vi.push_back(m+1);
            sort(vi.begin(), vi.end());
            int cur = 0;
            for(int i=0;i<vi.size();i++){
                if(vi[i]-cur>2) ans += (vi[i]-cur-2);
                cur = vi[i];
            }
            it++;
        }
        ans += (n-S.size())*((long long)m-1);
        return ans;
    }
};