Submission #1182923

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182923		dragst	Tower (JOI24_tower)	C++20	0 / 100	1171 ms	20104 KiB

Main

#include <bits/stdc++.h>
#define pll pair<long long, long long>
using namespace std;

struct seg
{
    long long l, r, val;
};

const long long inf=1e9;
pll a[200005];
long long b[200005], id[100005], ans[200005];
vector<long long> v2;
vector<seg> v[2], v3[500005];
seg seg1, seg2;

bool sortt(long long x, long long y) {return b[x]<b[y];}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n, q, d, x, y, m, i, j, k, sz1, sz2, id1, id2;
    cin >> n >> q >> d >> x >> y;
    y=min(y, x*d);
    for (i=1; i<=n; i++)
    {
        cin >> a[i].first >> a[i].second;
        v2.push_back(a[i].first/d);
        v2.push_back(a[i].second/d);
    };
    sort(a+1, a+n+1);
    for (i=1; i<=q; i++)
    {
        cin >> b[i];
        v2.push_back(b[i]/d);
        id[i]=i; ans[i]=-1;
    };
    sort(id+1, id+q+1, sortt);
    sort(v2.begin(), v2.end());
    v2.erase(unique(v2.begin(), v2.end()), v2.end());
    j=v2.size();
    for (i=1; i<j; i++)
    {
        if (v2[i]!=v2[i-1]+1)
        {
            v2.push_back(v2[i-1]+1);
            v2.push_back(v2[i]-1);
        };
    };
    v2.push_back(0);
    sort(v2.begin(), v2.end());
    v2.erase(unique(v2.begin(), v2.end()), v2.end());
    for (i=1; i<=n; i++)
    {
        j=lower_bound(v2.begin(), v2.end(), a[i].first/d)-v2.begin();
        k=lower_bound(v2.begin(), v2.end(), a[i].second/d)-v2.begin();
        if (j==k) {v3[j].push_back({a[i].first%d, a[i].second%d, -1});}
        else
        {
            v3[j].push_back({a[i].first%d, d-1, -1});
            v3[k].push_back({0, a[i].second%d, -1});
        };
    };
    if (v3[0].size())
    {
        v[0].push_back({0, v3[0][0].l-1, 0});
        v[0].push_back({v3[0][0].l, d-1, -1});
    }
    else {v[0].push_back({0, d-1, 0});};
    m=v2.size(); j=1;
    for (i=0; i<m; i++)
    {
        if (i>0)
        {
            v[i%2].clear();
            sz1=v[1-i%2].size(); sz2=v3[i].size();
            id1=id2=0;
            if (v[1-i%2][0].val==-1 && v[1-i%2].back().val!=-1 && (v3[i].empty() || v3[i][0].l!=0)) {v[1-i%2][0].val=v[1-i%2].back().val+(d-v[1-i%2].back().l)*x-y;};
            while (id1<sz1 || id2<sz2)
            {
                if (id1<sz1) {seg1=v[1-i%2][id1];};
                if (id2<sz2) {seg2=v3[i][id2];};
                if (id1==sz1)
                {
                    if (!v[i%2].empty() && v[i%2].back().val==-1) {v[i%2].back().r=d-1;}
                    else {v[i%2].push_back({seg2.l, d-1, -1});};
                    id2=sz2;
                }
                else if (id2==sz2)
                {
                    if (seg1.val==-1)
                    {
                        if (v[i%2].empty()) {v[i%2].push_back(seg1);}
                        else {v[i%2].back().r=max(v[i%2].back().r, seg1.r);};
                    }
                    else
                    {
                        if (v[i%2].empty()) {v[i%2].push_back({seg1.l, seg1.r, seg1.val+y});}
                        else if (v[i%2].back().val==-1 && v[i%2].back().r<seg1.r) {v[i%2].push_back({v[i%2].back().r+1, seg1.r, seg1.val+y+(v[i%2].back().r+1-seg1.l)*x});}
                        else if (v[i%2].back().val==-1) {v[i%2].back().r=max(v[i%2].back().r, seg1.r);}
                        else {v[i%2].push_back({seg1.l, seg1.r, seg1.val+y});};
                    };
                    id1++;
                }
                else if (seg1.l<seg2.l)
                {
                    if (seg1.val==-1)
                    {
                        if (v[i%2].empty()) {v[i%2].push_back(seg1);}
                        else if (seg1.r<seg2.l) {v[i%2].back().r=max(v[i%2].back().r, seg1.r);}
                        else {v[i%2].back().r=max(v[i%2].back().r, seg2.l-1);};
                    }
                    else if (v[i%2].empty())
                    {
                        if (seg1.r<seg2.l) {v[i%2].push_back({seg1.l, seg1.r, seg1.val+y});}
                        else {v[i%2].push_back({seg1.l, seg2.l-1, seg1.val+y});};
                    }
                    else
                    {
                        if (v[i%2].back().val==-1 && v[i%2].back().r<seg1.r) {v[i%2].push_back({v[i%2].back().r+1, seg1.r, seg1.val+y+(v[i%2].back().r+1-seg1.l)*x});}
                        else if (v[i%2].back().val==-1) {v[i%2].back().r=max(v[i%2].back().r, seg1.r);}
                        else if (seg1.r<seg2.l) {v[i%2].push_back({seg1.l, seg1.r, seg1.val+y});}
                        else {v[i%2].push_back({seg1.l, seg2.l-1, seg1.val+y});};
                    };
                    id1++;
                }
                else
                {
                    if (!v[i%2].empty() && v[i%2].back().val==-1) {v[i%2].back().r=seg2.r;}
                    else {v[i%2].push_back(seg2);};
                    id2++;
                };
            };
        };
        k=0;
        while (j<=q && b[id[j]]/d==v2[i])
        {
            while (k<(long long)v[i%2].size() && v[i%2][k].r<b[id[j]]%d) {k++;};
            if (v[i%2][k].val==-1) {ans[id[j]]=-1;}
            else {ans[id[j]]=v[i%2][k].val+(b[id[j]]%d-v[i%2][k].l)*x;};
            j++;
        };
    };
    for (i=1; i<=q; i++) {cout << ans[i] << "\n";};
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 38
• Subtask 3: 0 / 25
• Subtask 4: 0 / 32