Submission #984133

#	Time	Username	Problem	Language	Result	Execution time	Memory
984133		andrei_iorgulescu	Escape Route 2 (JOI24_escape2)	C++14	100 / 100	1174 ms	433356 KiB

Main

#include <bits/stdc++.h>

using namespace std;

long long inf = (long long)1e9 * (long long)1e9;

const int bulan = 400;

int n,t,Q;
vector<pair<int,int>>flights[100005];
vector<int> urm[100005];
long long answer[100005][bulan + 5];

struct jump
{
    int z,x;///z = nr de zile parcurse, x = ce zbor am luat ultimul
};

struct ura
{
    int first,second,j;
};

vector<ura> relevant_flights[100005];

vector<jump> rmq[100005][17];

bool cmp(pair<int,int> A,pair<int,int> B)
{
    if (A.first != B.first)
        return A.first < B.first;
    return A.second > B.second;
}

vector<pair<int,int>> relevant (vector<pair<int,int>> init)
{
    sort(init.begin(),init.end(),cmp);
    priority_queue<pair<int,int>>rmax;
    for (int i = 0; i < init.size(); i++)
    {
        while (!rmax.empty() and rmax.top().first >= init[i].second)
            rmax.pop();
        rmax.push({init[i].second,i});
    }
    vector<pair<int,int>>fin;
    while (!rmax.empty())
    {
        fin.push_back(init[rmax.top().second]);
        rmax.pop();
    }
    sort(fin.begin(),fin.end());
    return fin;
}

void prec()
{
    for (int l = 1; l < n; l++)
    {
        for (int r = l; r <= n and r - l + 1 <= bulan; r++)
            answer[l][r - l] = inf;
        vector<vector<pair<int,int>>> aj;
        if (n - l + 1 > bulan)
            aj.resize(flights[l + bulan - 1].size());
        for (int j = 0; j < flights[l].size(); j++)
        {
            int nrz = 0,land = j;
            int r;
            for (r = l + 1; r <= n and r - l + 1 <= bulan; r++)
            {
                answer[l][r - l] = min(answer[l][r - l],1ll * t * nrz + flights[r - 1][land].second - flights[l][j].first);
                if (r == n)
                    continue;
                int nxt = urm[r - 1][land];
                if (flights[r - 1][land].second > flights[r][nxt].first)
                    nrz++;
                land = nxt;
            }
            if (r <= n)
            {
                ///avionul j ajunge in land dupa nrz zile
                aj[land].push_back({nrz,j});
            }
        }
        if (n - l + 1 <= bulan)
            continue;
        for (int i = 0; i < aj.size(); i++)
        {
            if (aj[i].empty())
                continue;
            sort(aj[i].begin(),aj[i].end());
            while (aj[i][0].first != aj[i].back().first)
                aj[i].pop_back();
            ura auxxx;
            auxxx.j = aj[i].back().second;
            auxxx.first = flights[l][auxxx.j].first;
            auxxx.second = flights[l][auxxx.j].second;
            relevant_flights[l].push_back(auxxx);
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> t;
    for (int i = 1; i < n; i++)
    {
        int k;
        cin >> k;
        for (int j = 1; j <= k; j++)
        {
            int t1,t2;
            cin >> t1 >> t2;
            flights[i].push_back({t1,t2});
        }
        flights[i] = relevant(flights[i]);
        urm[i].resize(flights[i].size());
        for (int q = 0; q < 17; q++)
            rmq[i][q].resize(flights[i].size());
    }
    for (int i = 1; i <= n - 2; i++)
    {
        for (int j = 0; j < flights[i].size(); j++)
        {
            int mom = flights[i][j].second;
            if (mom > flights[i + 1][flights[i + 1].size() - 1].first)
                urm[i][j] = 0;
            else
            {
                /*for (int jj = flights[i + 1].size() - 1; jj >= 0; jj--)
                    if (mom <= flights[i + 1][jj].first)
                        urm[i][j] = jj;*/
                int stoops = flights[i + 1].size() - 1,paste = (1 << 16);
                while (paste != 0)
                {
                    if (stoops - paste >= 0 and mom <= flights[i + 1][stoops - paste].first)
                        stoops -= paste;
                    paste /= 2;
                }
                urm[i][j] = stoops;
            }
        }
    }
    for (int i = n - 1; i >= 1; i--)
    {
        for (int j = 0; j < flights[i].size(); j++)
        {
            rmq[i][0][j].z = 0;
            rmq[i][0][j].x = j;
            for (int q = 1; q <= 16; q++)
            {
                if (i + (1 << q) > n)
                    continue;
                rmq[i][q][j].z = rmq[i][q - 1][j].z;
                int land = rmq[i][q - 1][j].x;
                int nxt = urm[i - 1 + (1 << (q - 1))][land];
                if (flights[i - 1 + (1 << (q - 1))][land].second > flights[i + (1 << (q - 1))][nxt].first)
                    rmq[i][q][j].z++;
                rmq[i][q][j].z += rmq[i + (1 << (q - 1))][q - 1][nxt].z;
                rmq[i][q][j].x = rmq[i + (1 << (q - 1))][q - 1][nxt].x;
            }
        }
    }
    prec();
    cin >> Q;
    for (int i = 1; i <= Q; i++)
    {
        long long rsp = inf;
        int l,r;
        cin >> l >> r;
        if (r - l + 1 <= bulan)
        {
            cout << answer[l][r - l] << '\n';
            continue;
        }
        //for (int j = 0; j < flights[l].size(); j++)
        for (auto jj : relevant_flights[l])
        {
            int nrz = 0;
            int pos = l;
            int land = jj.j;
            for (int q = 16; q >= 0; q--)
            {
                if (pos + (1 << q) <= r)
                {
                    nrz += rmq[pos][q][land].z;
                    land = rmq[pos][q][land].x;
                    pos += (1 << q);
                    if (pos != r)
                    {
                        int nxt = urm[pos - 1][land];
                        if (flights[pos - 1][land].second > flights[pos][nxt].first)
                            nrz++;
                        land = nxt;
                    }
                }
            }
            rsp = min(rsp,1ll * t * nrz + flights[r - 1][land].second - flights[l][jj.j].first);
        }
        cout << rsp << '\n';
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'std::vector<std::pair<int, int> > relevant(std::vector<std::pair<int, int> >)':
Main.cpp:39:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for (int i = 0; i < init.size(); i++)
      |                     ~~^~~~~~~~~~~~~
Main.cpp: In function 'void prec()':
Main.cpp:64:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for (int j = 0; j < flights[l].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~
Main.cpp:86:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         for (int i = 0; i < aj.size(); i++)
      |                         ~~^~~~~~~~~~~
Main.cpp: In function 'int main()':
Main.cpp:125:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |         for (int j = 0; j < flights[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~
Main.cpp:148:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  148 |         for (int j = 0; j < flights[i].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 17 / 17
• Subtask 4: 23 / 23
• Subtask 5: 36 / 36
• Subtask 6: 10 / 10