Submission #1041183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1041183		aymanrs	Escape Route 2 (JOI24_escape2)	C++17	54 / 100	3031 ms	211580 KiB

Main

#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
const int L = 17;
using namespace std;
void solve(){
    int n, t, r;cin >> n >> t;
    set<pair<int, int>> s[n-1];
    vector<pair<int, int>> pp[n-1];
    for(int i = 0;i < n-1;i++){
        cin >> r;
        while(r--){
            int a, b;cin >> a >> b;            
            if(s[i].empty() || s[i].rbegin()->first<a || s[i].lower_bound({a,-1})->second > b){
                auto p = s[i].insert({a,b}).first;
                while(p != s[i].begin() && prev(p)->second >= b){
                    s[i].erase(prev(p));
                }
                if(p != prev(s[i].end()) && next(p)->first == p->first){
                    s[i].erase(next(p));
                }
            }
        }
        for(auto [a,b] : s[i]) pp[i].emplace_back(a,b);
    }
    vector<long long> bl[L][n-1]; vector<int> blt[L][n-1];
    for(int l = 0;l < L;l++){
        for(int i = 0;i < n-1;i++){
            bl[l][i].resize(s[i].size());
            blt[l][i].resize(s[i].size());
        }
    }
    vector<int> nxt[n-1];
    for(int i = 0;i < n-1;i++){
        for(int j = 0;j < pp[i].size();j++){
            bl[0][i][j] = pp[i][j].second-pp[i][j].first;
            blt[0][i][j] = j;
            if(i==n-2) continue;
            if(pp[i+1].back().first < pp[i][j].second) nxt[i].push_back(0);
            else nxt[i].push_back(lower_bound(pp[i+1].begin(), pp[i+1].end(), pair<int,int>{pp[i][j].second, -1})-pp[i+1].begin());
        }
    }
    for(int l = 1;l < L;l++){
        for(int i = 0;i+(1<<l) < n;i++){
            for(int j = 0;j < pp[i].size();j++){
                int na = pp[i+(1<<l-1)][nxt[i+(1<<l-1)-1][blt[l-1][i][j]]].first;
                int nb = pp[i+(1<<l-1)-1][blt[l-1][i][j]].second;
                if(na < nb){
                    bl[l][i][j] = bl[l-1][i][j] + t+na-nb + bl[l-1][i+(1<<l-1)][0];
                    blt[l][i][j] = blt[l-1][i+(1<<l-1)][0];
                } else {
                    bl[l][i][j] = bl[l-1][i][j] + na-nb + bl[l-1][i+(1<<l-1)][nxt[i+(1<<l-1)-1][blt[l-1][i][j]]];
                    blt[l][i][j] = blt[l-1][i+(1<<l-1)][nxt[i+(1<<l-1)-1][blt[l-1][i][j]]];
                }
            }
        }
    }
    int q;cin >> q;
    while(q--){
        int l,r;cin >> l >> r;l--;r--;
        long long aans = LONG_LONG_MAX;
        int ol = l;
        for(int j = 0;j < pp[ol].size();j++){
            l = ol;
            long long ans = pp[l][j].second-pp[l][j].first;
            int k = j;l++;
            for(int i = L-1;i >= 0;i--){
                if(l+(1<<i) > r) continue;
                int na = pp[l][nxt[l-1][k]].first;
                int nb = pp[l-1][k].second;
                if(na < nb){
                    ans += t+na-nb+bl[i][l][0];
                    k = blt[i][l][0];
                } else {
                    ans += na-nb+bl[i][l][nxt[l-1][k]];
                    k = blt[i][l][nxt[l-1][k]];
                }
                l+=1<<i;
            }
            aans = min(aans, ans);
        }
        cout << aans << '\n';
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:35:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for(int j = 0;j < pp[i].size();j++){
      |                       ~~^~~~~~~~~~~~~~
Main.cpp:45:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |             for(int j = 0;j < pp[i].size();j++){
      |                           ~~^~~~~~~~~~~~~~
Main.cpp:46:36: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   46 |                 int na = pp[i+(1<<l-1)][nxt[i+(1<<l-1)-1][blt[l-1][i][j]]].first;
      |                                   ~^~
Main.cpp:46:52: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   46 |                 int na = pp[i+(1<<l-1)][nxt[i+(1<<l-1)-1][blt[l-1][i][j]]].first;
      |                                                   ~^~
Main.cpp:47:36: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   47 |                 int nb = pp[i+(1<<l-1)-1][blt[l-1][i][j]].second;
      |                                   ~^~
Main.cpp:49:76: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   49 |                     bl[l][i][j] = bl[l-1][i][j] + t+na-nb + bl[l-1][i+(1<<l-1)][0];
      |                                                                           ~^~
Main.cpp:50:52: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   50 |                     blt[l][i][j] = blt[l-1][i+(1<<l-1)][0];
      |                                                   ~^~
Main.cpp:52:74: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   52 |                     bl[l][i][j] = bl[l-1][i][j] + na-nb + bl[l-1][i+(1<<l-1)][nxt[i+(1<<l-1)-1][blt[l-1][i][j]]];
      |                                                                         ~^~
Main.cpp:52:90: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   52 |                     bl[l][i][j] = bl[l-1][i][j] + na-nb + bl[l-1][i+(1<<l-1)][nxt[i+(1<<l-1)-1][blt[l-1][i][j]]];
      |                                                                                         ~^~
Main.cpp:53:52: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   53 |                     blt[l][i][j] = blt[l-1][i+(1<<l-1)][nxt[i+(1<<l-1)-1][blt[l-1][i][j]]];
      |                                                   ~^~
Main.cpp:53:68: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   53 |                     blt[l][i][j] = blt[l-1][i+(1<<l-1)][nxt[i+(1<<l-1)-1][blt[l-1][i][j]]];
      |                                                                   ~^~
Main.cpp:63:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |         for(int j = 0;j < pp[ol].size();j++){
      |                       ~~^~~~~~~~~~~~~~~

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