51nod 1484 猜数游戏 - dblank

# 51nod 1484 猜数游戏

· 根部是1
· 某个内部结点的编号为 i (i ≤ 2h−1−1) 时，他的左儿子编号为2i，右儿子编号为2i+1。

· u和v一样，
· u 是 v的父亲，
· u 是v的父亲的祖先。

Input

Output

Input示例
4 3
4 10 14 1
3 6 6 0
2 3 3 1
Output示例
14

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<map>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#define endl '\n'
#define debug puts("yes")
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 100000+ 10, Mod = 1000000007;
struct Quastion
{
ll i, l, r, ans;
} q[N];
int h, n;
vector<pair<ll, ll> > v;
int main()
{
scanf("%d%d", &h, &n);
ll f = 1LL<<(h-1), e = (1LL<<(h)) - 1;
map<ll, int> mp;
for(int i = 1; i<=n; i++)
{
scanf("%I64d%I64d%I64d%I64d", &q[i].i, &q[i].l, &q[i].r, &q[i].ans);
while(q[i].i < h)
{
q[i].l *= 2;
q[i].r = q[i].r*2+1;
q[i].i ++;
}
if(q[i].ans)
{
mp[q[i].l]++;
mp[q[i].r+1]--;
}
else
{
mp[f]++;
mp[q[i].l]--;
mp[q[i].r+1]++;
mp[e+1]--;
}
}
map<ll, int>::iterator it;
ll pre = -1, cnt = 0, ans = 0, sum;
for (it = mp.begin(); it!=mp.end(); it++)
{
sum += it->second;
if (pre != -1)
{
cnt += it->first - pre;
ans = pre;
}
if (sum == n)pre = it->first;
else pre = -1;
}
if(cnt == 1)
printf("%I64d\n", ans);
else if(cnt > 1)
puts("Data not sufficient!");
else puts("Game cheated!");
return 0;
}