oj.uz

Submission #1061711

# Submission time Handle Problem Language Result Execution time Memory
1061711 2024-08-16T12:06:22 Z new_acc Escape Route 2 (JOI24_escape2) C++14
100 / 100
 2193 ms 111560 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e5+10;
const int INFi=2e9;
const ll INFl=1e16;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=2027865967;
const ll p=70032301;
const ull p2=913;
const int L=17;
int n,m;
vector<pair<int,int>> t[N];
vi t2[N],naj[N][L];
pair<int,ll> jp[N][L];
pair<int,int> num[N];
map<pair<int,int>, ll> mm;
ll zn(int a,int b,int ost){
    ll curr=0;
    b--;
    for(int i=ost;i>=0;i--){
        if(num[jp[a][i].fi].fi<=b){
            curr+=jp[a][i].se;
            a=jp[a][i].fi;
        }
    }
    curr+=t[b][num[a].se].se-t[b][num[a].se].fi;
    return curr;
}
void solve(){
    cin>>n>>m;
    vector<pair<int,int>> cr;
    int li=0;
    for(int i=1;i<n;i++){
        int a;
        cin>>a;
        while(a--){
            int x,d;
            cin>>x>>d;
            cr.push_back({x,d});
        }
        sort(cr.begin(),cr.end());
        reverse(cr.begin(),cr.end());
        while(cr.size()){
            while(t[i].size() and t[i].back().se>=cr.back().se) t[i].pop_back();
            t[i].push_back(cr.back());
            cr.pop_back();
        }
        for(int i2=0;i2<t[i].size();i2++){
            t2[i].push_back(++li);
            num[li]={i,i2};
        }
    }
    num[li+1].fi=n;
    for(int i=0;i<L;i++) jp[li+1][i].fi=li+1;
    for(int i=1;i<n;i++){
        int curr=0;
        for(int i2=0;i2<t[i].size();i2++){
            while(curr<t[i+1].size() and t[i+1][curr].fi<t[i][i2].se) curr++;
            ll xd=t[i][i2].se-t[i][i2].fi;
            if(curr==t[i+1].size()){
                if(i<n-1) xd+=m-t[i][i2].se+t[i+1][0].fi,jp[t2[i][i2]][0].fi=t2[i+1][0];
                else jp[t2[i][i2]][0].fi=li+1;
            }else{
                xd+=t[i+1][curr].fi-t[i][i2].se;
                jp[t2[i][i2]][0].fi=t2[i+1][curr];
            }
            jp[t2[i][i2]][0].se=xd;
        }
    }
    for(int i2=1;i2<L;i2++){
        for(int i=1;i<=li;i++){
            int g=jp[i][i2].fi;
            jp[i][i2].se=jp[i][i2-1].se+jp[jp[i][i2-1].fi][i2-1].se;
            jp[i][i2].fi=jp[jp[i][i2-1].fi][i2-1].fi;
        }
    }
    vector<pair<int,pair<ll,int>>> pom;
    int q;
    cin>>q;
    for(int i=1;i<=q;i++){
        int a,b;
        cin>>a>>b;
        if(mm.count(make_pair(a,b))>0){
            cout<<mm[make_pair(a,b)]<<"\n";
            continue;
        }
        ll res=INFl;
        int xd=b-a-1;
        if(xd==0){
            for(int i2=0;i2<t2[a].size();i2++){
                res=min(res,(ll)t[b-1][i2].se-(ll)t[b-1][i2].fi);
            }
            mm[make_pair(a,b)]=res;
            cout<<res<<"\n";
        }else{
            int ost=0;
            for(int i2=0;i2<L;i2++){
                if((1<<i2)<=xd) ost=i2;
            }
            if(!naj[a][ost].size()){
                pom.clear();
                for(auto u:t2[a]) pom.push_back({jp[u][ost].fi,{jp[u][ost].se,u}});
                sort(pom.begin(),pom.end());
                for(int i3=0;i3<pom.size();i3++){
                    if(i3==0 or pom[i3-1].fi!=pom[i3].fi)
                        naj[a][ost].push_back(pom[i3].se.se);
                }
            }
            for(auto u:naj[a][ost]) res=min(res,zn(u,b,ost));
            mm[make_pair(a,b)]=res;
            cout<<res<<"\n";
        }
    } 
}
int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int tt=1;
    while(tt--) solve();
}

Compilation message

Main.cpp: In function 'void solve()':
Main.cpp:56:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for(int i2=0;i2<t[i].size();i2++){
      |                      ~~^~~~~~~~~~~~
Main.cpp:65:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for(int i2=0;i2<t[i].size();i2++){
      |                      ~~^~~~~~~~~~~~
Main.cpp:66: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]
   66 |             while(curr<t[i+1].size() and t[i+1][curr].fi<t[i][i2].se) curr++;
      |                   ~~~~^~~~~~~~~~~~~~
Main.cpp:68:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             if(curr==t[i+1].size()){
      |                ~~~~^~~~~~~~~~~~~~~
Main.cpp:80:17: warning: unused variable 'g' [-Wunused-variable]
   80 |             int g=jp[i][i2].fi;
      |                 ^
Main.cpp:98:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |             for(int i2=0;i2<t2[a].size();i2++){
      |                          ~~^~~~~~~~~~~~~
Main.cpp:112:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<long long int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |                 for(int i3=0;i3<pom.size();i3++){
      |                              ~~^~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 47452 KB Output is correct
2 Correct 48 ms 51356 KB Output is correct
3 Correct 174 ms 65692 KB Output is correct
4 Correct 241 ms 71764 KB Output is correct
5 Correct 190 ms 66736 KB Output is correct
6 Correct 281 ms 71336 KB Output is correct
7 Correct 297 ms 69716 KB Output is correct
8 Correct 196 ms 65620 KB Output is correct
9 Correct 266 ms 69804 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 47452 KB Output is correct
2 Correct 48 ms 51356 KB Output is correct
3 Correct 174 ms 65692 KB Output is correct
4 Correct 241 ms 71764 KB Output is correct
5 Correct 190 ms 66736 KB Output is correct
6 Correct 281 ms 71336 KB Output is correct
7 Correct 297 ms 69716 KB Output is correct
8 Correct 196 ms 65620 KB Output is correct
9 Correct 266 ms 69804 KB Output is correct
10 Correct 7 ms 47452 KB Output is correct
11 Correct 181 ms 56492 KB Output is correct
12 Correct 170 ms 57844 KB Output is correct
13 Correct 189 ms 57824 KB Output is correct
14 Correct 175 ms 57800 KB Output is correct
15 Correct 237 ms 64340 KB Output is correct
16 Correct 54 ms 51540 KB Output is correct
17 Correct 243 ms 70280 KB Output is correct
18 Correct 224 ms 65088 KB Output is correct
19 Correct 277 ms 69540 KB Output is correct
20 Correct 214 ms 62128 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 47452 KB Output is correct
2 Correct 48 ms 51356 KB Output is correct
3 Correct 174 ms 65692 KB Output is correct
4 Correct 241 ms 71764 KB Output is correct
5 Correct 190 ms 66736 KB Output is correct
6 Correct 281 ms 71336 KB Output is correct
7 Correct 297 ms 69716 KB Output is correct
8 Correct 196 ms 65620 KB Output is correct
9 Correct 266 ms 69804 KB Output is correct
10 Correct 427 ms 91988 KB Output is correct
11 Correct 688 ms 107604 KB Output is correct
12 Correct 720 ms 107604 KB Output is correct
13 Correct 496 ms 104020 KB Output is correct
14 Correct 682 ms 111524 KB Output is correct
15 Correct 722 ms 111488 KB Output is correct
16 Correct 404 ms 95052 KB Output is correct
17 Correct 728 ms 111560 KB Output is correct
18 Correct 217 ms 86352 KB Output is correct
19 Correct 189 ms 85628 KB Output is correct
20 Correct 206 ms 87352 KB Output is correct
21 Correct 197 ms 87336 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 47452 KB Output is correct
2 Correct 48 ms 51356 KB Output is correct
3 Correct 174 ms 65692 KB Output is correct
4 Correct 241 ms 71764 KB Output is correct
5 Correct 190 ms 66736 KB Output is correct
6 Correct 281 ms 71336 KB Output is correct
7 Correct 297 ms 69716 KB Output is correct
8 Correct 196 ms 65620 KB Output is correct
9 Correct 266 ms 69804 KB Output is correct
10 Correct 7 ms 47452 KB Output is correct
11 Correct 181 ms 56492 KB Output is correct
12 Correct 170 ms 57844 KB Output is correct
13 Correct 189 ms 57824 KB Output is correct
14 Correct 175 ms 57800 KB Output is correct
15 Correct 237 ms 64340 KB Output is correct
16 Correct 54 ms 51540 KB Output is correct
17 Correct 243 ms 70280 KB Output is correct
18 Correct 224 ms 65088 KB Output is correct
19 Correct 277 ms 69540 KB Output is correct
20 Correct 214 ms 62128 KB Output is correct
21 Correct 427 ms 91988 KB Output is correct
22 Correct 688 ms 107604 KB Output is correct
23 Correct 720 ms 107604 KB Output is correct
24 Correct 496 ms 104020 KB Output is correct
25 Correct 682 ms 111524 KB Output is correct
26 Correct 722 ms 111488 KB Output is correct
27 Correct 404 ms 95052 KB Output is correct
28 Correct 728 ms 111560 KB Output is correct
29 Correct 217 ms 86352 KB Output is correct
30 Correct 189 ms 85628 KB Output is correct
31 Correct 206 ms 87352 KB Output is correct
32 Correct 197 ms 87336 KB Output is correct
33 Correct 845 ms 105012 KB Output is correct
34 Correct 838 ms 104928 KB Output is correct
35 Correct 762 ms 100676 KB Output is correct
36 Correct 731 ms 100564 KB Output is correct
37 Correct 590 ms 102484 KB Output is correct
38 Correct 500 ms 92680 KB Output is correct
39 Correct 500 ms 101464 KB Output is correct
40 Correct 426 ms 89556 KB Output is correct
41 Correct 480 ms 93836 KB Output is correct
42 Correct 629 ms 106064 KB Output is correct
43 Correct 420 ms 91984 KB Output is correct
44 Correct 506 ms 98508 KB Output is correct
45 Correct 189 ms 84568 KB Output is correct
46 Correct 171 ms 82260 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 47452 KB Output is correct
2 Correct 7 ms 47452 KB Output is correct
3 Correct 614 ms 82052 KB Output is correct
4 Correct 734 ms 82000 KB Output is correct
5 Correct 671 ms 82004 KB Output is correct
6 Correct 617 ms 81892 KB Output is correct
7 Correct 587 ms 81952 KB Output is correct
8 Correct 123 ms 66900 KB Output is correct
9 Correct 106 ms 78012 KB Output is correct
10 Correct 63 ms 61896 KB Output is correct
11 Correct 192 ms 86628 KB Output is correct
12 Correct 195 ms 84456 KB Output is correct
13 Correct 163 ms 82120 KB Output is correct
14 Correct 118 ms 79712 KB Output is correct
15 Correct 117 ms 79720 KB Output is correct
16 Correct 122 ms 81780 KB Output is correct
17 Correct 143 ms 81452 KB Output is correct
18 Correct 148 ms 78228 KB Output is correct
19 Correct 114 ms 77140 KB Output is correct
20 Correct 103 ms 78204 KB Output is correct
21 Correct 110 ms 80996 KB Output is correct
22 Correct 81 ms 77132 KB Output is correct
23 Correct 125 ms 79836 KB Output is correct
24 Correct 141 ms 80780 KB Output is correct
25 Correct 66 ms 77180 KB Output is correct
26 Correct 159 ms 81708 KB Output is correct
27 Correct 151 ms 85584 KB Output is correct
28 Correct 170 ms 87124 KB Output is correct
29 Correct 183 ms 87128 KB Output is correct
30 Correct 99 ms 59760 KB Output is correct
31 Correct 42 ms 50392 KB Output is correct
32 Correct 107 ms 62804 KB Output is correct
33 Correct 59 ms 51044 KB Output is correct
34 Correct 82 ms 55872 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 47452 KB Output is correct
2 Correct 48 ms 51356 KB Output is correct
3 Correct 174 ms 65692 KB Output is correct
4 Correct 241 ms 71764 KB Output is correct
5 Correct 190 ms 66736 KB Output is correct
6 Correct 281 ms 71336 KB Output is correct
7 Correct 297 ms 69716 KB Output is correct
8 Correct 196 ms 65620 KB Output is correct
9 Correct 266 ms 69804 KB Output is correct
10 Correct 7 ms 47452 KB Output is correct
11 Correct 181 ms 56492 KB Output is correct
12 Correct 170 ms 57844 KB Output is correct
13 Correct 189 ms 57824 KB Output is correct
14 Correct 175 ms 57800 KB Output is correct
15 Correct 237 ms 64340 KB Output is correct
16 Correct 54 ms 51540 KB Output is correct
17 Correct 243 ms 70280 KB Output is correct
18 Correct 224 ms 65088 KB Output is correct
19 Correct 277 ms 69540 KB Output is correct
20 Correct 214 ms 62128 KB Output is correct
21 Correct 427 ms 91988 KB Output is correct
22 Correct 688 ms 107604 KB Output is correct
23 Correct 720 ms 107604 KB Output is correct
24 Correct 496 ms 104020 KB Output is correct
25 Correct 682 ms 111524 KB Output is correct
26 Correct 722 ms 111488 KB Output is correct
27 Correct 404 ms 95052 KB Output is correct
28 Correct 728 ms 111560 KB Output is correct
29 Correct 217 ms 86352 KB Output is correct
30 Correct 189 ms 85628 KB Output is correct
31 Correct 206 ms 87352 KB Output is correct
32 Correct 197 ms 87336 KB Output is correct
33 Correct 845 ms 105012 KB Output is correct
34 Correct 838 ms 104928 KB Output is correct
35 Correct 762 ms 100676 KB Output is correct
36 Correct 731 ms 100564 KB Output is correct
37 Correct 590 ms 102484 KB Output is correct
38 Correct 500 ms 92680 KB Output is correct
39 Correct 500 ms 101464 KB Output is correct
40 Correct 426 ms 89556 KB Output is correct
41 Correct 480 ms 93836 KB Output is correct
42 Correct 629 ms 106064 KB Output is correct
43 Correct 420 ms 91984 KB Output is correct
44 Correct 506 ms 98508 KB Output is correct
45 Correct 189 ms 84568 KB Output is correct
46 Correct 171 ms 82260 KB Output is correct
47 Correct 8 ms 47452 KB Output is correct
48 Correct 7 ms 47452 KB Output is correct
49 Correct 614 ms 82052 KB Output is correct
50 Correct 734 ms 82000 KB Output is correct
51 Correct 671 ms 82004 KB Output is correct
52 Correct 617 ms 81892 KB Output is correct
53 Correct 587 ms 81952 KB Output is correct
54 Correct 123 ms 66900 KB Output is correct
55 Correct 106 ms 78012 KB Output is correct
56 Correct 63 ms 61896 KB Output is correct
57 Correct 192 ms 86628 KB Output is correct
58 Correct 195 ms 84456 KB Output is correct
59 Correct 163 ms 82120 KB Output is correct
60 Correct 118 ms 79712 KB Output is correct
61 Correct 117 ms 79720 KB Output is correct
62 Correct 122 ms 81780 KB Output is correct
63 Correct 143 ms 81452 KB Output is correct
64 Correct 148 ms 78228 KB Output is correct
65 Correct 114 ms 77140 KB Output is correct
66 Correct 103 ms 78204 KB Output is correct
67 Correct 110 ms 80996 KB Output is correct
68 Correct 81 ms 77132 KB Output is correct
69 Correct 125 ms 79836 KB Output is correct
70 Correct 141 ms 80780 KB Output is correct
71 Correct 66 ms 77180 KB Output is correct
72 Correct 159 ms 81708 KB Output is correct
73 Correct 151 ms 85584 KB Output is correct
74 Correct 170 ms 87124 KB Output is correct
75 Correct 183 ms 87128 KB Output is correct
76 Correct 99 ms 59760 KB Output is correct
77 Correct 42 ms 50392 KB Output is correct
78 Correct 107 ms 62804 KB Output is correct
79 Correct 59 ms 51044 KB Output is correct
80 Correct 82 ms 55872 KB Output is correct
81 Correct 1390 ms 93648 KB Output is correct
82 Correct 1404 ms 92968 KB Output is correct
83 Correct 1344 ms 92720 KB Output is correct
84 Correct 1357 ms 92692 KB Output is correct
85 Correct 1411 ms 92880 KB Output is correct
86 Correct 250 ms 76112 KB Output is correct
87 Correct 233 ms 89336 KB Output is correct
88 Correct 2193 ms 105928 KB Output is correct
89 Correct 1685 ms 102896 KB Output is correct
90 Correct 306 ms 83544 KB Output is correct
91 Correct 68 ms 66000 KB Output is correct
92 Correct 304 ms 94300 KB Output is correct
93 Correct 294 ms 93780 KB Output is correct
94 Correct 334 ms 104384 KB Output is correct
95 Correct 385 ms 101260 KB Output is correct
96 Correct 273 ms 91912 KB Output is correct
97 Correct 229 ms 87120 KB Output is correct
98 Correct 154 ms 86768 KB Output is correct
99 Correct 315 ms 95660 KB Output is correct
100 Correct 192 ms 85480 KB Output is correct
101 Correct 278 ms 93780 KB Output is correct
102 Correct 303 ms 92640 KB Output is correct
103 Correct 133 ms 87168 KB Output is correct
104 Correct 400 ms 98872 KB Output is correct
105 Correct 268 ms 73448 KB Output is correct
106 Correct 83 ms 54740 KB Output is correct
107 Correct 329 ms 81492 KB Output is correct
108 Correct 161 ms 57804 KB Output is correct
109 Correct 199 ms 64856 KB Output is correct