oj.uz

Submission #984133

# Submission time Handle Problem Language Result Execution time Memory
984133 2024-05-16T10:28:17 Z andrei_iorgulescu Escape Route 2 (JOI24_escape2) C++14
100 / 100
 1174 ms 433356 KB 
#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

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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 48220 KB Output is correct
2 Correct 61 ms 51284 KB Output is correct
3 Correct 75 ms 56252 KB Output is correct
4 Correct 107 ms 59728 KB Output is correct
5 Correct 90 ms 58704 KB Output is correct
6 Correct 111 ms 59528 KB Output is correct
7 Correct 111 ms 59732 KB Output is correct
8 Correct 90 ms 56404 KB Output is correct
9 Correct 116 ms 59728 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 48220 KB Output is correct
2 Correct 61 ms 51284 KB Output is correct
3 Correct 75 ms 56252 KB Output is correct
4 Correct 107 ms 59728 KB Output is correct
5 Correct 90 ms 58704 KB Output is correct
6 Correct 111 ms 59528 KB Output is correct
7 Correct 111 ms 59732 KB Output is correct
8 Correct 90 ms 56404 KB Output is correct
9 Correct 116 ms 59728 KB Output is correct
10 Correct 11 ms 48452 KB Output is correct
11 Correct 68 ms 55112 KB Output is correct
12 Correct 72 ms 55840 KB Output is correct
13 Correct 71 ms 54408 KB Output is correct
14 Correct 71 ms 54100 KB Output is correct
15 Correct 77 ms 56144 KB Output is correct
16 Correct 56 ms 52052 KB Output is correct
17 Correct 95 ms 58960 KB Output is correct
18 Correct 79 ms 55576 KB Output is correct
19 Correct 101 ms 58452 KB Output is correct
20 Correct 80 ms 54572 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 48220 KB Output is correct
2 Correct 61 ms 51284 KB Output is correct
3 Correct 75 ms 56252 KB Output is correct
4 Correct 107 ms 59728 KB Output is correct
5 Correct 90 ms 58704 KB Output is correct
6 Correct 111 ms 59528 KB Output is correct
7 Correct 111 ms 59732 KB Output is correct
8 Correct 90 ms 56404 KB Output is correct
9 Correct 116 ms 59728 KB Output is correct
10 Correct 878 ms 350952 KB Output is correct
11 Correct 1174 ms 432208 KB Output is correct
12 Correct 1172 ms 431764 KB Output is correct
13 Correct 928 ms 431068 KB Output is correct
14 Correct 1080 ms 433356 KB Output is correct
15 Correct 1099 ms 432900 KB Output is correct
16 Correct 783 ms 352104 KB Output is correct
17 Correct 1072 ms 431512 KB Output is correct
18 Correct 574 ms 390484 KB Output is correct
19 Correct 535 ms 389996 KB Output is correct
20 Correct 563 ms 390564 KB Output is correct
21 Correct 567 ms 390484 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 48220 KB Output is correct
2 Correct 61 ms 51284 KB Output is correct
3 Correct 75 ms 56252 KB Output is correct
4 Correct 107 ms 59728 KB Output is correct
5 Correct 90 ms 58704 KB Output is correct
6 Correct 111 ms 59528 KB Output is correct
7 Correct 111 ms 59732 KB Output is correct
8 Correct 90 ms 56404 KB Output is correct
9 Correct 116 ms 59728 KB Output is correct
10 Correct 11 ms 48452 KB Output is correct
11 Correct 68 ms 55112 KB Output is correct
12 Correct 72 ms 55840 KB Output is correct
13 Correct 71 ms 54408 KB Output is correct
14 Correct 71 ms 54100 KB Output is correct
15 Correct 77 ms 56144 KB Output is correct
16 Correct 56 ms 52052 KB Output is correct
17 Correct 95 ms 58960 KB Output is correct
18 Correct 79 ms 55576 KB Output is correct
19 Correct 101 ms 58452 KB Output is correct
20 Correct 80 ms 54572 KB Output is correct
21 Correct 878 ms 350952 KB Output is correct
22 Correct 1174 ms 432208 KB Output is correct
23 Correct 1172 ms 431764 KB Output is correct
24 Correct 928 ms 431068 KB Output is correct
25 Correct 1080 ms 433356 KB Output is correct
26 Correct 1099 ms 432900 KB Output is correct
27 Correct 783 ms 352104 KB Output is correct
28 Correct 1072 ms 431512 KB Output is correct
29 Correct 574 ms 390484 KB Output is correct
30 Correct 535 ms 389996 KB Output is correct
31 Correct 563 ms 390564 KB Output is correct
32 Correct 567 ms 390484 KB Output is correct
33 Correct 715 ms 136196 KB Output is correct
34 Correct 822 ms 136160 KB Output is correct
35 Correct 687 ms 135720 KB Output is correct
36 Correct 703 ms 135168 KB Output is correct
37 Correct 704 ms 170580 KB Output is correct
38 Correct 765 ms 250980 KB Output is correct
39 Correct 974 ms 305516 KB Output is correct
40 Correct 566 ms 142548 KB Output is correct
41 Correct 737 ms 241276 KB Output is correct
42 Correct 1002 ms 305096 KB Output is correct
43 Correct 673 ms 178984 KB Output is correct
44 Correct 695 ms 183136 KB Output is correct
45 Correct 560 ms 277072 KB Output is correct
46 Correct 448 ms 166832 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 48216 KB Output is correct
2 Correct 11 ms 48428 KB Output is correct
3 Correct 141 ms 63584 KB Output is correct
4 Correct 155 ms 63828 KB Output is correct
5 Correct 149 ms 63060 KB Output is correct
6 Correct 153 ms 63060 KB Output is correct
7 Correct 152 ms 63144 KB Output is correct
8 Correct 92 ms 56656 KB Output is correct
9 Correct 167 ms 63832 KB Output is correct
10 Correct 56 ms 55368 KB Output is correct
11 Correct 577 ms 391268 KB Output is correct
12 Correct 582 ms 277992 KB Output is correct
13 Correct 463 ms 166568 KB Output is correct
14 Correct 369 ms 129704 KB Output is correct
15 Correct 352 ms 129396 KB Output is correct
16 Correct 358 ms 131360 KB Output is correct
17 Correct 370 ms 129432 KB Output is correct
18 Correct 286 ms 67972 KB Output is correct
19 Correct 188 ms 65528 KB Output is correct
20 Correct 368 ms 302416 KB Output is correct
21 Correct 413 ms 300380 KB Output is correct
22 Correct 286 ms 183340 KB Output is correct
23 Correct 321 ms 183764 KB Output is correct
24 Correct 331 ms 182148 KB Output is correct
25 Correct 267 ms 184616 KB Output is correct
26 Correct 309 ms 185092 KB Output is correct
27 Correct 511 ms 392860 KB Output is correct
28 Correct 660 ms 393356 KB Output is correct
29 Correct 599 ms 393532 KB Output is correct
30 Correct 126 ms 69864 KB Output is correct
31 Correct 50 ms 51392 KB Output is correct
32 Correct 112 ms 61780 KB Output is correct
33 Correct 52 ms 51964 KB Output is correct
34 Correct 73 ms 53332 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 48220 KB Output is correct
2 Correct 61 ms 51284 KB Output is correct
3 Correct 75 ms 56252 KB Output is correct
4 Correct 107 ms 59728 KB Output is correct
5 Correct 90 ms 58704 KB Output is correct
6 Correct 111 ms 59528 KB Output is correct
7 Correct 111 ms 59732 KB Output is correct
8 Correct 90 ms 56404 KB Output is correct
9 Correct 116 ms 59728 KB Output is correct
10 Correct 11 ms 48452 KB Output is correct
11 Correct 68 ms 55112 KB Output is correct
12 Correct 72 ms 55840 KB Output is correct
13 Correct 71 ms 54408 KB Output is correct
14 Correct 71 ms 54100 KB Output is correct
15 Correct 77 ms 56144 KB Output is correct
16 Correct 56 ms 52052 KB Output is correct
17 Correct 95 ms 58960 KB Output is correct
18 Correct 79 ms 55576 KB Output is correct
19 Correct 101 ms 58452 KB Output is correct
20 Correct 80 ms 54572 KB Output is correct
21 Correct 878 ms 350952 KB Output is correct
22 Correct 1174 ms 432208 KB Output is correct
23 Correct 1172 ms 431764 KB Output is correct
24 Correct 928 ms 431068 KB Output is correct
25 Correct 1080 ms 433356 KB Output is correct
26 Correct 1099 ms 432900 KB Output is correct
27 Correct 783 ms 352104 KB Output is correct
28 Correct 1072 ms 431512 KB Output is correct
29 Correct 574 ms 390484 KB Output is correct
30 Correct 535 ms 389996 KB Output is correct
31 Correct 563 ms 390564 KB Output is correct
32 Correct 567 ms 390484 KB Output is correct
33 Correct 715 ms 136196 KB Output is correct
34 Correct 822 ms 136160 KB Output is correct
35 Correct 687 ms 135720 KB Output is correct
36 Correct 703 ms 135168 KB Output is correct
37 Correct 704 ms 170580 KB Output is correct
38 Correct 765 ms 250980 KB Output is correct
39 Correct 974 ms 305516 KB Output is correct
40 Correct 566 ms 142548 KB Output is correct
41 Correct 737 ms 241276 KB Output is correct
42 Correct 1002 ms 305096 KB Output is correct
43 Correct 673 ms 178984 KB Output is correct
44 Correct 695 ms 183136 KB Output is correct
45 Correct 560 ms 277072 KB Output is correct
46 Correct 448 ms 166832 KB Output is correct
47 Correct 11 ms 48216 KB Output is correct
48 Correct 11 ms 48428 KB Output is correct
49 Correct 141 ms 63584 KB Output is correct
50 Correct 155 ms 63828 KB Output is correct
51 Correct 149 ms 63060 KB Output is correct
52 Correct 153 ms 63060 KB Output is correct
53 Correct 152 ms 63144 KB Output is correct
54 Correct 92 ms 56656 KB Output is correct
55 Correct 167 ms 63832 KB Output is correct
56 Correct 56 ms 55368 KB Output is correct
57 Correct 577 ms 391268 KB Output is correct
58 Correct 582 ms 277992 KB Output is correct
59 Correct 463 ms 166568 KB Output is correct
60 Correct 369 ms 129704 KB Output is correct
61 Correct 352 ms 129396 KB Output is correct
62 Correct 358 ms 131360 KB Output is correct
63 Correct 370 ms 129432 KB Output is correct
64 Correct 286 ms 67972 KB Output is correct
65 Correct 188 ms 65528 KB Output is correct
66 Correct 368 ms 302416 KB Output is correct
67 Correct 413 ms 300380 KB Output is correct
68 Correct 286 ms 183340 KB Output is correct
69 Correct 321 ms 183764 KB Output is correct
70 Correct 331 ms 182148 KB Output is correct
71 Correct 267 ms 184616 KB Output is correct
72 Correct 309 ms 185092 KB Output is correct
73 Correct 511 ms 392860 KB Output is correct
74 Correct 660 ms 393356 KB Output is correct
75 Correct 599 ms 393532 KB Output is correct
76 Correct 126 ms 69864 KB Output is correct
77 Correct 50 ms 51392 KB Output is correct
78 Correct 112 ms 61780 KB Output is correct
79 Correct 52 ms 51964 KB Output is correct
80 Correct 73 ms 53332 KB Output is correct
81 Correct 419 ms 69164 KB Output is correct
82 Correct 411 ms 70224 KB Output is correct
83 Correct 435 ms 72784 KB Output is correct
84 Correct 430 ms 72036 KB Output is correct
85 Correct 438 ms 68944 KB Output is correct
86 Correct 188 ms 61376 KB Output is correct
87 Correct 255 ms 72632 KB Output is correct
88 Correct 625 ms 74184 KB Output is correct
89 Correct 670 ms 73132 KB Output is correct
90 Correct 206 ms 61956 KB Output is correct
91 Correct 92 ms 59548 KB Output is correct
92 Correct 534 ms 144484 KB Output is correct
93 Correct 576 ms 142924 KB Output is correct
94 Correct 548 ms 146412 KB Output is correct
95 Correct 580 ms 144628 KB Output is correct
96 Correct 395 ms 77736 KB Output is correct
97 Correct 256 ms 73036 KB Output is correct
98 Correct 474 ms 305492 KB Output is correct
99 Correct 650 ms 305036 KB Output is correct
100 Correct 420 ms 186200 KB Output is correct
101 Correct 536 ms 188624 KB Output is correct
102 Correct 481 ms 190860 KB Output is correct
103 Correct 381 ms 187148 KB Output is correct
104 Correct 543 ms 186248 KB Output is correct
105 Correct 165 ms 59592 KB Output is correct
106 Correct 119 ms 52048 KB Output is correct
107 Correct 222 ms 64424 KB Output is correct
108 Correct 113 ms 52336 KB Output is correct
109 Correct 117 ms 55536 KB Output is correct