Submission #56048160

---

Source Code Expand

#include <random>
#include <algorithm>
#include <bitset>
#include <chrono>
#include <cmath>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <chrono>
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((x).size())
typedef long long ll;
using ull = unsigned long long;
using namespace std;
mt19937 rnd(348502);
ll mod1 = 998244353;
ll mod = 1e9 + 7;
const int N = 200007;


void solve()
{
    int n, i, j, q, x, y, b, k;
    cin >> n >> q;
    vector<int> v;
    for ( i = 0; i < n; i++)
    {
        cin >> x;
        v.push_back(x);
    }
    sort(all(v));
    for ( i = 0; i < q; i++)
    {
        cin >> b >> k;
        int qaq = 0;
        if (v[0] >= b)
        {
            cout << v[k - 1] - b << '\n';
            continue;
        }
        if (v.back() <= b)
        {
            cout << b - v[v.size() - k] << '\n';
            continue;
        }
        int l = 0, r = upper_bound(all(v), b) - v.begin();
        int ll = upper_bound(all(v), b) - v.begin(), rr = n - 1;
        int m, m1, ans = -1;
        while (l <= r)
        {
            m = (l + r) / 2;
            int her = abs(b - v[m]);
            int ans1 = -1;
            int l1 = m, r1 = rr;
            while (l1 <= r1)
            {
                m1 = (l1 + r1) / 2;
                if (abs(v[m1] - b) <= abs(b - v[m]))
                {
                    ans1 = m1;
                    l1 = m1 + 1;
                }
                else
                {
                    r1 = m1 - 1;
                }
            }
            if (abs(m - ans1) + 1 >= k)
            {
                ans = m;
                qaq = ans1;
                l = m + 1;
            }
            else
            {
                r = m - 1;
            }
        }
        if (ans != -1)
        {
            if (ans + k - 1 < v.size() && v[ans + k - 1] == v[qaq])
            {
                cout << abs(v[ans] - b) << '\n';
                continue;
            }
        }
        ll = 0, rr = lower_bound(all(v), b) - v.begin() - 1;
        l = lower_bound(all(v), b) - v.begin() - 1, r = n - 1;
        m, m1, ans = -1;
        qaq = 0;
        while (l <= r)
        {
            m = (l + r) / 2;
            int her = abs(b - v[m]);
            int ans1 = -1;
            int l1 = ll, r1 = m;
            while (l1 <= r1)
            {
                m1 = (l1 + r1) / 2;
                if (abs(v[m1] - b) <= abs(b - v[m]))
                {
                    ans1 = m1;
                    r1 = m1 - 1;
                }
                else
                {
                    l1 = m1 + 1;
                }
            }
            if (abs(m - ans1) + 1 >= k)
            {
                ans = m;
                qaq = ans1;
                r = m - 1;
            }
            else
            {
                l = m + 1;
            }
        }
        cout << abs(v[ans] - b) << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

Submission Info

Compile Error

Main.cpp: In function ‘void solve()’:
Main.cpp:63:17: warning: unused variable ‘her’ [-Wunused-variable]
   63 |             int her = abs(b - v[m]);
      |                 ^~~
Main.cpp:92:29: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   92 |             if (ans + k - 1 < v.size() && v[ans + k - 1] == v[qaq])
      |                 ~~~~~~~~~~~~^~~~~~~~~~
Main.cpp:100:9: warning: left operand of comma operator has no effect [-Wunused-value]
  100 |         m, m1, ans = -1;
      |         ^
Main.cpp:100:23: warning: right operand of comma operator has no effect [-Wunused-value]
  100 |         m, m1, ans = -1;
      |                       ^
Main.cpp:105:17: warning: unused variable ‘her’ [-Wunused-variable]
  105 |             int her = abs(b - v[m]);
      |                 ^~~
Main.cpp:34:15: warning: unused variable ‘j’ [-Wunused-variable]
   34 |     int n, i, j, q, x, y, b, k;
      |               ^
Main.cpp:34:24: warning: unused variable ‘y’ [-Wunused-variable]
   34 |     int n, i, j, q, x, y, b, k;
      |                        ^

Judge Result