19.6 แบบฝึกหัด

เขียนแต่ละข้อเป็นไฟล์ใหม่ใน Code::Blocks รันแล้วเทียบกับผลลัพธ์ที่ต้องได้ให้ตรงทุกตัวอักษร รวมถึงช่องว่างและการขึ้นบรรทัด ติดจริงๆ ค่อยเปิดคำใบ้ และเปิดเฉลยหลังทำเสร็จแล้วเท่านั้น

ข้อ 1 ส่งน้ำแข็งถึงกี่บ้าน

ระดับง่าย เวลาไม่เกิน 1 วินาที

ร้านน้ำแข็งส่งของให้ลูกค้าที่อยู่ริมถนนเส้นตรงเส้นเดียว บ้านลูกค้า N หลังอยู่ที่ตำแหน่ง x₁, x₂, ..., x_N กิโลเมตรจากหลักกิโลเมตรศูนย์ ตำแหน่งติดลบคืออยู่อีกฝั่งของหลัก บ้านหลายหลังอาจอยู่ตำแหน่งเดียวกันได้ เช่น ห้องในตึกเดียวกัน

ร้านวางแผนส่งของ Q วัน วันหนึ่งรถจะจอดที่ตำแหน่ง p และน้ำแข็งละลายเร็ว จึงส่งได้เฉพาะบ้านที่อยู่ห่างจากรถไม่เกิน d กิโลเมตร ไม่ว่าทางซ้ายหรือทางขวา ให้หาว่าแต่ละวันส่งของถึงบ้านได้กี่หลัง

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ Q คั่นด้วยช่องว่าง โดยที่ 1 ≤ N ≤ 200000 และ 1 ≤ Q ≤ 200000

บรรทัดที่สองมีจำนวนเต็ม N ตัว คือตำแหน่งของบ้าน โดยที่ -10⁹ ≤ x_i ≤ 10⁹

อีก Q บรรทัด แต่ละบรรทัดมีจำนวนเต็ม p และ d คั่นด้วยช่องว่าง โดยที่ -10⁹ ≤ p ≤ 10⁹ และ 0 ≤ d ≤ 10⁹

ข้อมูลออก

Q บรรทัด ตอบตามลำดับวัน บรรทัดละหนึ่งวัน เป็นจำนวนบ้านที่อยู่ห่างจาก p ไม่เกิน d

6 4
3 -2 10 3 7 15
5 2
0 3
12 1
3 0

ดูคำใบ้

เรียงตำแหน่งบ้านครั้งเดียว แล้วแต่ละวันนับบ้านที่ตำแหน่งอยู่ตั้งแต่ p - d ถึง p + d ด้วย upper_bound(p + d) ลบ lower_bound(p - d) ตามหน้า 19.2 ระวังบ้านที่อยู่ตรงขอบช่วงพอดี และบ้านหลายหลังที่อยู่ตำแหน่งเดียวกัน วิธีไล่ดูทุกบ้านทุกวันต้องเทียบถึง 4 × 10¹⁰ ครั้ง ไม่ทันเวลา

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<long long> houses(n);
    for (int i = 0; i < n; i++) {
        cin >> houses[i];
    }
    sort(houses.begin(), houses.end());
    for (int k = 0; k < q; k++) {
        long long p, d;
        cin >> p >> d;
        int from = lower_bound(houses.begin(), houses.end(), p - d) - houses.begin();
        int to = upper_bound(houses.begin(), houses.end(), p + d) - houses.begin();
        cout << to - from << '\n';
    }
    return 0;
}

ข้อ 2 อ่านครบเมื่อไร

ระดับง่าย เวลาไม่เกิน 1 วินาที

น้องจดไว้ว่าตลอด N วันที่ผ่านมา วันที่ i อ่านหนังสือไป a_i หน้า บางวันไม่ได้อ่านเลย เพื่อนๆ ในชมรมอยากเทียบกันว่า ถ้าเริ่มนับตั้งแต่วันที่ s จะต้องถึงวันที่เท่าไรน้องจึงอ่านรวมได้อย่างน้อย t หน้า มีคำถามแบบนี้ Q ข้อ

คำตอบของคำถามหนึ่งข้อคือวันที่ d ที่น้อยที่สุด ที่ d ≥ s และ a_s + a_s+1 + ... + a_d ≥ t ถ้าอ่านถึงวันที่ N แล้วยังไม่ถึง t หน้า ให้ตอบ -1

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ Q คั่นด้วยช่องว่าง โดยที่ 1 ≤ N ≤ 200000 และ 1 ≤ Q ≤ 200000

บรรทัดที่สองมีจำนวนเต็ม N ตัว คือ a₁ ถึง a_N โดยที่ 0 ≤ a_i ≤ 10000

อีก Q บรรทัด แต่ละบรรทัดมีจำนวนเต็ม s และ t คั่นด้วยช่องว่าง โดยที่ 1 ≤ s ≤ N และ 1 ≤ t ≤ 10⁹

ข้อมูลออก

Q บรรทัด ตอบตามลำดับคำถาม บรรทัดละหนึ่งข้อ เป็นวันที่ d หรือ -1

7 5
30 45 0 0 60 25 40
1 75
3 1
3 60
6 66
2 200

ดูคำใบ้

สร้าง prefix ของจำนวนหน้าก่อน ถ้าเริ่มวันที่ s จำนวนหน้าที่อ่านถึงวันที่ d คือ prefix[d] - prefix[s - 1] ต้องการให้ค่านี้อย่างน้อย t ก็คือ prefix[d] >= prefix[s - 1] + t ตัวเลขทางขวาเป็นค่าคงที่ของคำถามนั้น จำนวนหน้าไม่ติดลบ prefix จึงเรียงอยู่แล้ว ใช้ lower_bound ค้นตั้งแต่ prefix.begin() + s ตามหน้า 19.2 วันที่ไม่ได้อ่านทำให้มีค่าซ้ำ ต้องได้วันแรก

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<long long> prefix(n + 1, 0);
    for (int day = 1; day <= n; day++) {
        int pages;
        cin >> pages;
        prefix[day] = prefix[day - 1] + pages;
    }
    for (int k = 0; k < q; k++) {
        int start;
        long long target;
        cin >> start >> target;
        long long need = prefix[start - 1] + target;
        int day = lower_bound(prefix.begin() + start, prefix.end(), need) - prefix.begin();
        if (day > n) {
            cout << -1 << '\n';
        } else {
            cout << day << '\n';
        }
    }
    return 0;
}

ข้อ 3 ปูกระเบื้องจัตุรัส

ระดับง่าย เวลาไม่เกิน 1 วินาที

ช่างปูกระเบื้องมีกระเบื้องแผ่นสี่เหลี่ยมจัตุรัสขนาดเท่ากัน n แผ่น ลูกค้าอยากได้ลานที่ปูเป็นรูปสี่เหลี่ยมจัตุรัสเต็มผืน ขนาด k × k แผ่น ให้หาว่าลานใหญ่ที่สุดที่ปูได้มีด้านยาวกี่แผ่น กระเบื้องที่เหลือเก็บไว้ใช้งานอื่น ช่างมีงานแบบนี้ T งาน ให้ตอบทุกงาน

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม T โดยที่ 1 ≤ T ≤ 100000

อีก T บรรทัด แต่ละบรรทัดมีจำนวนเต็ม n หนึ่งตัว โดยที่ 0 ≤ n ≤ 10¹⁸

ข้อมูลออก

T บรรทัด ตอบตามลำดับงาน บรรทัดละหนึ่งงาน เป็นจำนวนเต็ม k ที่มากที่สุดที่ k × k ≤ n

5
10
16
0
99
1000000000000000000

ดูคำใบ้

คำตอบคือ k ที่มากที่สุดที่ k × k ≤ n ถ้า k ใช้ได้ k - 1 ก็ใช้ได้ จึงเป็น binary search หา "ใช่" ตัวสุดท้ายแบบโจทย์ตัดไม้ในหน้า 19.3 ที่ต้องปัดจุดกลางขึ้น คำตอบไม่เกิน 10⁹ จึงให้ hi เริ่มที่ 10⁹ ถ้าเริ่มที่ n จุดกลางจะใหญ่จน mid * mid ล้นแม้เป็น long long และอย่าใช้ sqrt ของ double ซึ่งแม่นแค่ราว 16 หลัก ลองกับ n = 999999999999999999 ดู คำตอบต้องเป็น 999999999

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    for (int job = 0; job < t; job++) {
        long long n;
        cin >> n;
        long long lo = 0, hi = 1000000000;
        while (lo < hi) {
            long long mid = lo + (hi - lo + 1) / 2;
            if (mid * mid <= n) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }
        cout << lo << '\n';
    }
    return 0;
}

ข้อ 4 ทาสีรั้วโรงเรียน

ระดับง่าย เวลาไม่เกิน 1 วินาที

รั้วไม้ของโรงเรียนมีไม้เรียงกัน N แผ่น หมายเลข 1 ถึง N วันอาสามีนักเรียนมาช่วยทาสีกันแดด Q กลุ่ม กลุ่มที่ j ทาไม้ตั้งแต่แผ่นที่ l ถึงแผ่นที่ r ทับลงไปอีก c ชั้น สีกันแดดจะได้ผลเมื่อหนาอย่างน้อย K ชั้น หลังทุกกลุ่มทาเสร็จ ให้นับว่ามีไม้กี่แผ่นที่สียังหนาไม่ถึง K ชั้น ซึ่งต้องนัดมาทาซ่อมอีกวัน

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N Q และ K คั่นด้วยช่องว่าง โดยที่ 1 ≤ N ≤ 200000, 1 ≤ Q ≤ 200000 และ 1 ≤ K ≤ 10¹⁵

อีก Q บรรทัด แต่ละบรรทัดมีจำนวนเต็ม l r และ c คั่นด้วยช่องว่าง โดยที่ 1 ≤ l ≤ r ≤ N และ 1 ≤ c ≤ 10⁹

ข้อมูลออก

จำนวนแผ่นที่สีหนาน้อยกว่า K ชั้น

ดูคำใบ้

ถ้าวนทาทีละแผ่นทุกกลุ่ม เมื่อ N กับ Q เป็นสองแสนและทุกกลุ่มทาเกือบทั้งรั้ว ต้องบวกถึง 4 × 10¹⁰ ครั้ง ใช้ difference array ในหน้า 19.5 แต่ละกลุ่มจดแค่สองช่อง แล้วสะสมครั้งเดียวก็ได้จำนวนชั้นของทุกแผ่น จำนวนชั้นรวมได้ถึง 2 × 10¹⁴ และ K ก็เกิน int ได้ ใช้ long long ทั้งคู่ ระวังกลุ่มที่ทาถึงแผ่นที่ N ซึ่งต้องลบที่ช่อง N + 1

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    long long k;
    cin >> n >> q >> k;
    vector<long long> diff(n + 2, 0);
    for (int j = 0; j < q; j++) {
        int l, r, layers;
        cin >> l >> r >> layers;
        diff[l] += layers;
        diff[r + 1] -= layers;
    }
    long long current = 0;
    int thin = 0;
    for (int board = 1; board <= n; board++) {
        current += diff[board];
        if (current < k) {
            thin++;
        }
    }
    cout << thin << '\n';
    return 0;
}

ข้อ 5 ริบบิ้นผูกช่อดอกไม้

ระดับง่าย เวลาไม่เกิน 1 วินาที

ร้านดอกไม้มีริบบิ้นอยู่ N ม้วน ม้วนที่ i ยาว L_i เซนติเมตร งานรับปริญญาสัปดาห์หน้ามีช่อดอกไม้ K ช่อ ทุกช่อต้องผูกริบบิ้นหนึ่งเส้นที่ยาวเท่ากันทุกช่อ และยาวเป็นจำนวนเต็มเซนติเมตร ริบบิ้นแต่ละเส้นต้องตัดมาจากม้วนเดียว ห้ามเอาเศษสองม้วนมาต่อกัน เศษที่เหลือจากการตัดทิ้งได้

ริบบิ้นยิ่งยาวช่อยิ่งสวย ให้หาว่าตัดให้ได้อย่างน้อย K เส้นโดยแต่ละเส้นยาวที่สุดได้กี่เซนติเมตร ถ้าตัดเส้นละ 1 เซนติเมตรแล้วยังไม่ถึง K เส้น ให้ตอบ 0

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ K คั่นด้วยช่องว่าง โดยที่ 1 ≤ N ≤ 100000 และ 1 ≤ K ≤ 10⁹

บรรทัดที่สองมีจำนวนเต็ม N ตัว คือ L₁ ถึง L_N โดยที่ 1 ≤ L_i ≤ 10⁹

ข้อมูลออก

ความยาวที่มากที่สุดเป็นเซนติเมตร หรือ 0

5 13
730 410 980 260 555

3 20
5 9 4

ดูคำใบ้

ถ้าตัดยาว x ซม. ได้จำนวนเส้นรวมเท่ากับผลรวมของ L_i / x แบบปัดเศษทิ้ง ยิ่งยาวยิ่งได้น้อย ถ้า x ใช้ได้ x - 1 ก็ใช้ได้ คำตอบคือ "ใช่" ตัวสุดท้ายแบบโจทย์ตัดไม้ในหน้า 19.3 ให้ lo เริ่มที่ 0 hi เริ่มที่ม้วนที่ยาวที่สุด และปัดจุดกลางขึ้น ซึ่งทำให้ไม่ต้องหารด้วย 0 ด้วย ตอนตัดยาว 1 ซม. จำนวนเส้นรวมถึง 10¹⁴ ต้องนับด้วย long long ถ้าลองทุกความยาวจากยาวไปสั้น เมื่อคำตอบสั้นแต่ริบบิ้นยาวพันล้าน ต้องลองเกือบพันล้านค่า

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

long long pieces(const vector<int> &lengths, int cut)
{
    long long total = 0;
    for (int i = 0; i < (int)lengths.size(); i++) {
        total += lengths[i] / cut;
    }
    return total;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long k;
    cin >> n >> k;
    vector<int> lengths(n);
    int lo = 0, hi = 0;
    for (int i = 0; i < n; i++) {
        cin >> lengths[i];
        hi = max(hi, lengths[i]);
    }
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;
        if (pieces(lengths, mid) >= k) {
            lo = mid;
        } else {
            hi = mid - 1;
        }
    }
    cout << lo << '\n';
    return 0;
}

ข้อ 6 เตาอบขนม

ระดับกลาง เวลาไม่เกิน 1 วินาที

โรงงานขนมมีเตาอบ N เตา ทุกเตาเริ่มอบพร้อมกันที่นาทีที่ 0 และอบต่อเนื่องไม่หยุด เตาที่ i อบขนมเสร็จหนึ่งถาดทุก t_i นาที คือเสร็จถาดแรกที่นาทีที่ t_i ถาดที่สองที่นาทีที่ 2t_i ไปเรื่อยๆ วันนี้มีออร์เดอร์ M ถาด ให้หาว่าต้องใช้เวลาน้อยที่สุดกี่นาทีจึงได้ขนมครบ M ถาด

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ M คั่นด้วยช่องว่าง โดยที่ 1 ≤ N ≤ 100000 และ 1 ≤ M ≤ 10⁹

บรรทัดที่สองมีจำนวนเต็ม N ตัว คือ t₁ ถึง t_N โดยที่ 1 ≤ t_i ≤ 10⁹

ข้อมูลออก

จำนวนนาทีที่น้อยที่สุด

3 10
4 6 10

ดูคำใบ้

ภายใน T นาที เตาที่ i อบได้ T / t_i ถาดแบบปัดเศษทิ้ง ถ้า T นาทีพอ T + 1 นาทีก็พอ จึงหา T แรกที่พอด้วยลูปแบบหน้า 19.3 คำตอบไม่เกิน M คูณเวลาของเตาที่เร็วที่สุด ซึ่งถึง 10¹⁸ ต้องใช้ long long ทั้ง lo hi mid และตัวนับถาด ถ้าตั้ง hi ใหญ่กว่านั้น ตัวนับถาดอาจล้นแม้เป็น long long ให้หยุดนับทันทีที่ได้ครบ M ถาด

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

bool enough(const vector<long long> &minutes, long long time, long long trays)
{
    long long baked = 0;
    for (int i = 0; i < (int)minutes.size(); i++) {
        baked += time / minutes[i];
        if (baked >= trays) {
            return true;
        }
    }
    return false;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long trays;
    cin >> n >> trays;
    vector<long long> minutes(n);
    long long fastest = LLONG_MAX;
    for (int i = 0; i < n; i++) {
        cin >> minutes[i];
        fastest = min(fastest, minutes[i]);
    }
    long long lo = 1, hi = fastest * trays;
    while (lo < hi) {
        long long mid = lo + (hi - lo) / 2;
        if (enough(minutes, mid, trays)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    cout << lo << '\n';
    return 0;
}

ข้อ 7 เสาสัญญาณริมถนน

ระดับกลาง เวลาไม่เกิน 1 วินาที

ถนนชนบทเส้นหนึ่งเป็นเส้นตรง มีจุดที่ได้รับอนุญาตให้ตั้งเสาสัญญาณ N จุด จุดที่ i อยู่ห่างจากต้นถนน x_i เมตร ไม่มีสองจุดไหนอยู่ตำแหน่งเดียวกัน บริษัทต้องตั้งเสา C ต้นบนจุดเหล่านี้ จุดละไม่เกินหนึ่งต้น เสาที่อยู่ใกล้กันจะรบกวนสัญญาณกัน บริษัทจึงอยากให้ระยะห่างของเสาคู่ที่อยู่ใกล้กันที่สุดมากที่สุดเท่าที่ทำได้ ให้หาระยะนั้น

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ C คั่นด้วยช่องว่าง โดยที่ 2 ≤ C ≤ N ≤ 100000

บรรทัดที่สองมีจำนวนเต็ม N ตัว คือ x₁ ถึง x_N ไม่ได้เรียงมา และไม่ซ้ำกัน โดยที่ 0 ≤ x_i ≤ 10⁹

ข้อมูลออก

ระยะห่างของเสาคู่ที่ใกล้กันที่สุด ที่มากที่สุดเท่าที่ทำได้

6 3
12 3 30 1 20 8

ดูคำใบ้

ทำตามหัวข้อระยะห่างมากที่สุดในหน้า 19.3 เรียงตำแหน่งก่อน แล้วถามว่า "ตั้ง C ต้นให้ทุกคู่ห่างกันอย่างน้อย D ได้ไหม" ตอบด้วย greedy ตั้งต้นแรกที่จุดซ้ายสุด ไล่ไปทางขวา ตั้งต้นถัดไปที่จุดแรกที่ห่างจากต้นล่าสุดอย่างน้อย D ถ้า D ทำได้ D - 1 ก็ทำได้ จึงหา "ใช่" ตัวสุดท้าย ปัดจุดกลางขึ้น ถ้าลองทุกคู่ของจุดเป็นค่า D ที่เป็นไปได้ จะมีถึง 5 × 10⁹ ค่าเมื่อ N เป็นแสน

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

bool can_place(const vector<int> &spots, int towers, int gap)
{
    int placed = 1;
    int last = spots[0];
    for (int i = 1; i < (int)spots.size(); i++) {
        if (spots[i] - last >= gap) {
            placed++;
            last = spots[i];
            if (placed >= towers) {
                return true;
            }
        }
    }
    return placed >= towers;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, towers;
    cin >> n >> towers;
    vector<int> spots(n);
    for (int i = 0; i < n; i++) {
        cin >> spots[i];
    }
    sort(spots.begin(), spots.end());
    int lo = 0, hi = spots[n - 1] - spots[0];
    while (lo < hi) {
        int mid = lo + (hi - lo + 1) / 2;
        if (can_place(spots, towers, mid)) {
            lo = mid;
        } else {
            hi = mid - 1;
        }
    }
    cout << lo << '\n';
    return 0;
}

ข้อ 8 ยอดผู้ติดตามเปลี่ยนเท่ากับ K

ระดับยาก เวลาไม่เกิน 1 วินาที

น้องทำช่องวิดีโอ และจดว่ายอดผู้ติดตามเปลี่ยนไปเท่าไรในแต่ละวันตลอด N วัน วันที่ i เปลี่ยนไป a_i คน ถ้ามีคนเลิกติดตามมากกว่าคนติดตามใหม่ a_i จะติดลบ น้องอยากรู้ว่ามีกี่ช่วงวันติดกันที่ยอดผู้ติดตามรวมแล้วเปลี่ยนไป K คนพอดี

ช่วงวันคือคู่ l กับ r ที่ 1 ≤ l ≤ r ≤ N และยอดที่เปลี่ยนรวมคือ a_l + a_l+1 + ... + a_r ช่วงที่ l หรือ r ต่างกันนับเป็นคนละช่วง แม้ผลรวมจะมาจากวันชุดที่ดูคล้ายกัน

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ K คั่นด้วยช่องว่าง โดยที่ 1 ≤ N ≤ 200000 และ -10¹⁵ ≤ K ≤ 10¹⁵

บรรทัดที่สองมีจำนวนเต็ม N ตัว คือ a₁ ถึง a_N โดยที่ -10⁹ ≤ a_i ≤ 10⁹

ข้อมูลออก

จำนวนช่วงวันที่ยอดเปลี่ยนรวมเท่ากับ K พอดี

7 4
2 2 -3 5 0 -1 4

ดูคำใบ้

ช่วงวันที่ l ถึง r เปลี่ยนรวม K พอดีเมื่อ prefix[l - 1] = prefix[r] - K ตามหน้า 19.5 ค่าในแต่ละวันกว้างถึง ±10⁹ ใช้อาเรย์นับไม่ได้ ให้เรียงคู่ (prefix, index) แล้วใช้ lower_bound สองครั้งต่อหนึ่งวัน r อย่าลืมใส่ prefix[0] และจำนวนช่วงถึง N(N + 1)/2 ซึ่งเกิน int ลองทุกคู่ l กับ r ต้องทำราว 2 × 10¹⁰ คู่เมื่อ N เป็นสองแสน

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long k;
    cin >> n >> k;
    vector<long long> prefix(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        long long change;
        cin >> change;
        prefix[i] = prefix[i - 1] + change;
    }
    vector<pair<long long, int>> sorted_prefix(n + 1);
    for (int j = 0; j <= n; j++) {
        sorted_prefix[j] = make_pair(prefix[j], j);
    }
    sort(sorted_prefix.begin(), sorted_prefix.end());
    long long count = 0;
    for (int r = 1; r <= n; r++) {
        long long want = prefix[r] - k;
        auto from = lower_bound(sorted_prefix.begin(), sorted_prefix.end(), make_pair(want, 0));
        auto to = lower_bound(sorted_prefix.begin(), sorted_prefix.end(), make_pair(want, r));
        count += to - from;
    }
    cout << count << '\n';
    return 0;
}

ข้อ 9 จุดนัดพบ

ระดับกลาง เวลาไม่เกิน 1 วินาที

เพื่อน N คนอยู่บนถนนเส้นตรงเส้นเดียวกัน คนที่ i อยู่ห่างจากต้นถนน x_i เมตร และเคลื่อนที่ได้เร็วที่สุด v_i เมตรต่อวินาที บางคนเดิน บางคนปั่นจักรยาน ทุกคนออกเดินทางพร้อมกัน เพื่อไปพบกันที่จุดนัดจุดเดียวบนถนน จุดนัดจะอยู่ตรงไหนก็ได้ ไม่จำเป็นต้องเป็นจำนวนเต็ม คนที่ไปถึงก่อนรอได้ ให้หาว่าทุกคนมาพร้อมหน้ากันได้เร็วที่สุดภายในกี่วินาที

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N โดยที่ 1 ≤ N ≤ 100000

บรรทัดที่สองมีจำนวนเต็ม N ตัว คือ x₁ ถึง x_N โดยที่ 0 ≤ x_i ≤ 10⁹ หลายคนอาจอยู่ที่เดียวกันได้

บรรทัดที่สามมีจำนวนเต็ม N ตัว คือ v₁ ถึง v_N โดยที่ 1 ≤ v_i ≤ 1000

ข้อมูลออก

เวลาที่น้อยที่สุดเป็นวินาที พิมพ์ทศนิยม 4 ตำแหน่ง ชุดทดสอบเลือกไว้แล้วว่าคำตอบจริงไม่อยู่ใกล้กึ่งกลางระหว่างสองค่าที่ปัดได้ คำตอบที่คลาดจากค่าจริงไม่เกิน 10^-6 จะปัดได้ตรงกับเฉลยเสมอ

3
0 10 40
2 3 1

13.3333

2
5 5
7 9

0.0000

ดูคำใบ้

ถามว่า "ภายใน T วินาที ทุกคนไปเจอกันได้ไหม" ภายใน T วินาที คนที่ i ไปได้ทุกจุดตั้งแต่ x_i - v_iT ถึง x_i + v_iT ทุกคนเจอกันได้เมื่อช่วงทั้งหมดมีจุดร่วม คือขอบซ้ายที่มากที่สุดไม่เกินขอบขวาที่น้อยที่สุด ถ้า T ทำได้ เวลาที่มากกว่าก็ทำได้ ใช้ binary search บนจำนวนจริงแบบหน้า 19.4 วน 100 รอบ ช่วงเริ่มที่ 0 ถึง 10⁹ พิมพ์ด้วย fixed กับ setprecision(4) ถ้าลองทุกคู่ของคน จะมีห้าพันล้านคู่เมื่อ N เป็นแสน

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

bool can_meet(const vector<int> &place, const vector<int> &speed, double time)
{
    double left = -1e30, right = 1e30;
    for (int i = 0; i < (int)place.size(); i++) {
        left = max(left, place[i] - speed[i] * time);
        right = min(right, place[i] + speed[i] * time);
    }
    return left <= right;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> place(n), speed(n);
    for (int i = 0; i < n; i++) {
        cin >> place[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> speed[i];
    }
    double lo = 0, hi = 1e9;
    for (int step = 0; step < 100; step++) {
        double mid = (lo + hi) / 2;
        if (can_meet(place, speed, mid)) {
            hi = mid;
        } else {
            lo = mid;
        }
    }
    cout << fixed << setprecision(4) << hi << '\n';
    return 0;
}

ข้อ 10 แผนรดน้ำต้นไม้

ระดับยาก เวลาไม่เกิน 1 วินาที

สวนผักของโรงเรียนมีต้นไม้ปลูกเรียงเป็นแถว N ต้น หมายเลข 1 ถึง N ช่วงปิดเทอม ต้นที่ i ต้องได้น้ำรวมอย่างน้อย need_i ลิตรจึงจะรอด ครูวางแผนรดน้ำไว้ Q ครั้งตามลำดับ ครั้งที่ j รดต้นตั้งแต่ต้นที่ l ถึงต้นที่ r ต้นละ w ลิตร ครูอยากรู้ว่าต้องรดตามแผนไปกี่ครั้งแรก ทุกต้นจึงได้น้ำครบตามที่ต้องการ จะได้หยุดรดหลังจากนั้นเพื่อประหยัดน้ำ

คำตอบคือ k ที่น้อยที่สุดที่หลังจากรดครั้งที่ 1 ถึง k แล้ว ทุกต้นได้น้ำรวมอย่างน้อย need_i ลิตร ถ้าทุกต้นต้องการ 0 ลิตรตั้งแต่แรก คำตอบคือ 0 ถ้ารดครบทั้ง Q ครั้งแล้วยังมีต้นที่ได้น้ำไม่พอ ให้ตอบ -1

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ Q คั่นด้วยช่องว่าง โดยที่ 1 ≤ N ≤ 200000 และ 1 ≤ Q ≤ 200000

บรรทัดที่สองมีจำนวนเต็ม N ตัว คือ need₁ ถึง need_N โดยที่ 0 ≤ need_i ≤ 10¹⁴

อีก Q บรรทัด บรรทัดที่ j มีจำนวนเต็ม l r และ w ของการรดครั้งที่ j คั่นด้วยช่องว่าง โดยที่ 1 ≤ l ≤ r ≤ N และ 1 ≤ w ≤ 10⁹

ข้อมูลออก

จำนวนครั้งที่น้อยที่สุด หรือ -1

ดูคำใบ้

ถ้ารดครบ k ครั้งแรกแล้วทุกต้นได้น้ำพอ รดเพิ่มอีกครั้งก็ยังพอ เพราะน้ำมีแต่เพิ่ม คำตอบจึงเป็น k แรกที่ตอบ "ใช่" แบบหน้า 19.3 ส่วนการตรวจว่า k ครั้งแรกพอไหม ใช้ difference array ในหน้า 19.5 กับ k รายการแรก แล้วสะสมเทียบกับที่แต่ละต้นต้องการ ตรวจหนึ่งครั้งเป็น O(N + Q) และตรวจราว 18 ครั้ง ถ้ารดครบ Q ครั้งแล้วยังไม่พอ ตอบ -1 ถ้าทุกต้นต้องการ 0 ลิตร ตอบ 0 ปริมาณน้ำและความต้องการเกิน int

ดูเฉลย

#include <bits/stdc++.h>
using namespace std;

int n, q;
vector<long long> need;
vector<int> from_tree, to_tree, water;

bool enough_after(int rounds)
{
    vector<long long> diff(n + 2, 0);
    for (int j = 0; j < rounds; j++) {
        diff[from_tree[j]] += water[j];
        diff[to_tree[j] + 1] -= water[j];
    }
    long long current = 0;
    for (int tree = 1; tree <= n; tree++) {
        current += diff[tree];
        if (current < need[tree]) {
            return false;
        }
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    need.assign(n + 1, 0);
    for (int tree = 1; tree <= n; tree++) {
        cin >> need[tree];
    }
    from_tree.resize(q);
    to_tree.resize(q);
    water.resize(q);
    for (int j = 0; j < q; j++) {
        cin >> from_tree[j] >> to_tree[j] >> water[j];
    }
    if (!enough_after(q)) {
        cout << -1 << '\n';
        return 0;
    }
    int lo = 0, hi = q;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (enough_after(mid)) {
            hi = mid;
        } else {
            lo = mid + 1;
        }
    }
    cout << lo << '\n';
    return 0;
}