C++11(clang++ 3.9) 解法, 执行用时: 47ms, 内存消耗: 616K, 提交时间: 2018-03-29 11:27:57

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <cassert>
#include <string.h>
#include <unordered_set>
#include <unordered_map>

using namespace std;

typedef long long int64;
typedef unsigned long long uint64;
#define two(X) (1<<(X))
#define twoL(X) (((int64)(1))<<(X))
#define contain(S,X) (((S)&two(X))!=0)
#define containL(S,X) (((S)&twoL(X))!=0)
const double pi = acos(-1.0);
const double eps = 1e-11;
template<class T> inline void ckmin(T &a, T b) { if (b<a) a = b; }
template<class T> inline void ckmax(T &a, T b) { if (b>a) a = b; }
template<class T> inline T sqr(T x) { return x * x; }
typedef pair<int, int> ipair;
#define SIZE(A) ((int)A.size())
#define LENGTH(A) ((int)A.length())
#define MP(A,B) make_pair(A,B)
#define PB(X) push_back(X)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,a) for(int i=0;i<(a);++i)
#define ALL(A) A.begin(),A.end()

int64 w(int64 q, int64 a, int64 b)
{
	return (q + 1)*a + b;
}
int64 f(int64 a, int64 b)
{
	if (a + b <= 1) return 0;
	int64 q = 1;
	while (w(q, a, b)>(1LL << q)) ++q;
	if (a % 2 == 0) return q;
	int64 c = (a + 1) / 2, d = max(0LL, (b - q + 2) / 2);
	return (w(q - 1, c, d + a - c) <= (1LL << (q - 1)) && w(q - 1, a - c, b - d + c) <= (1LL << (q - 1))) ? q : (q + 1);
}

int main()
{
	std::ios::sync_with_stdio(false);
	int64 n;
	int m;
	while (cin >> n >> m)
	{
		assert(n >= 1 && n <= 100000000LL * 100000000LL);
		assert(m >= 0 && m <= 10);
		int ed = 0;
		map<int64, int> d;
		d[0] = d[n] = 0;
		REP(k, m)
		{
			int c;
			cin >> c;
			assert(c >= 1 && c <= 100);
			vector<pair<int64, int64>> a;
			REP(i, c)
			{
				int64 s, t;
				cin >> s >> t;
				assert(s >= 1 && s <= t && t <= n);
				--s;
				s = max(0LL, s);
				t = min(n, t);
				if (s<t) a.emplace_back(s, t);
			}
			sort(ALL(a));
			vector<pair<int64, int64>> b;
			for (auto w : a)
				if (b.empty() || w.first>b.back().second)
					b.push_back(w);
				else
					ckmax(b.back().second, w.second);
			string str;
			cin >> str;
			assert(str == "yes" || str == "no");
			int delta;
			if (str == "yes")
				++ed, delta = 1;
			else
				delta = -1;
			for (auto w : b) d[w.first] += delta, d[w.second] -= delta;
		}
		int64 n0 = 0, n1 = 0;
		vector<pair<int64, int>> p(ALL(d));
		int sd = 0;
		REP(i, SIZE(p) - 1)
		{
			sd += p[i].second;
			if (sd == ed) n0 += p[i + 1].first - p[i].first;
			else if (sd + 1 == ed) n1 += p[i + 1].first - p[i].first;
		}
		printf("%d\n", f(n0, n1));
	}
	return 0;
}