题解

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define edge(i, u) for (int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define N 100005
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define lowbit(x) (x & -x)
#define ls (k << 1)
#define rs (k << 1 | 1)
#define mod 998244353
#define up 10000
int v, p, n, m, a[N], u[N], w[N], tot, cnt, t[N];
std::queue<ll> q;
inline bool check (int x)
{
fo (i, 1, n)
if (!a[i]) q.push(1); else q.push((a[i] < u[x]) ? 1ll << 60 : 0);
ll d, e, f;
while (!q.empty())
{
d = q.front(); q.pop(); if (q.empty()) return d <= t[x];
e = q.front(); q.pop(); f = q.front(); q.pop();
q.push(std::min(std::min(d + e, e + f), std::min(f + d, 1ll << 60)));
}
}
int main ()
{
scanf("%d %d", &n, &m);
fo (i, 1, m)
{
scanf("%d %d", &v, &p);
a[p] = v;
w[++tot] = v;
u[tot] = w[tot];
}
fo (i, 1, n - m)
{
scanf("%d", &w[++tot]);
u[tot] = w[tot];
}
std::sort(u + 1, u + tot + 1);
cnt = std::unique(u + 1, u + tot + 1) - u - 1;
fo (i, 1, tot)
{
w[i] = std::lower_bound(u + 1, u + cnt + 1, w[i]) - u;
if (m < i)
++t[w[i]];
}
fd (i, cnt, 1)
t[i] += t[i + 1];
int l = 1, r = cnt;
while (l < r)
{
int mid = l + r + 1 >> 1;
if (check(mid))
l = mid;
else
r = mid - 1;
}
printf("%d", u[l]);
}