3 条题解

  • 1
    @ 2023-12-19 23:02:50
    #include<iostream>
    #include<algorithm>
    #include<cmath>
    #include<vector>
    #include<set>
    #include<string>
    #include<iomanip>
    #include<cstring>
    #include<ctime>
    #include<unordered_map>
    #include<stack>
    #include<queue>
    //*****************************************************************************************************************
    //                .-~~~~~~~~~-._       _.-~~~~~~~~~-.
    //            __.'              ~.   .~              `.__
    //          .'//                  \./                  \\`.
    //        .'//                     |                     \\`.
    //      .'// .-~"""""""~~~~-._     |     _,-~~~~"""""""~-. \\`.
    //    .'//.-"                 `-.  |  .-'                 "-.\\`.
    //  .'//______.============-..   \ | /   ..-============.______\\`.
    //.'______________________________\|/______________________________`.
    //*****************************************************************************************************************
    using namespace std;
    const int o = 1e7 + 10;
    typedef pair<long, long>ll;
    long long a[o], s[o], l1[o], r1[o], c1[o], t = 0;
    void num(int l, int r, int c)
    {
        a[l] -= c;
        a[r + 1] += c;
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
        long long n, m;
        cin >> n >> m;
        long long l = 1, r = n;
        long long cmp = 0;
        for (int i = 1; i <= n; i++)
        {
            cin >> l1[i] >> r1[i] >> c1[i];
        }
        while (l <= r)
        {
            for (int i = 1; i <= n; i++)
            {
                s[i] = m;
                a[i] = s[i] - s[i - 1];
            }
            bool fg = 0;
            long long mid = l + r>> 1;
            for (int i = 1; i <= mid; i++)
            {
                num(l1[i], r1[i], c1[i]);
            }
            for (int i = 1; i <= n;i++)
            {
                s[i] = a[i] + s[i - 1];
                if (s[i]<= 0)
                {
                    fg = 1;
                }
            }
            if (fg)
            {
                r = mid-1;
                cmp = mid;
            }
            else
            {
                l = mid+1;
            }
        }
        if (cmp!=0)
        {
            cout << cmp;
        }
        else
        {
            cout << "impossible";
        }
    }
    

    信息

    ID
    965
    时间
    1000ms
    内存
    256MiB
    难度
    9
    标签
    递交数
    708
    已通过
    66
    上传者