oj.uz

Submission #1061684

# Submission time Handle Problem Language Result Execution time Memory
1061684 2024-08-16T11:52:25 Z new_acc Escape Route 2 (JOI24_escape2) C++14
90 / 100
 3000 ms 157620 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){
    ll res=0,curr=0;
    int g=0;
    b--;
    for(int i=L-1;i>=0;i--){
        if(num[jp[a][i].fi].fi>=b) res=curr+jp[a][i].se,g=jp[a][i].fi;
        else{
            curr+=jp[a][i].se;
            a=jp[a][i].fi;
        }
    }
    res+=t[b][num[g].se].se-t[b][num[g].se].fi;
    return res;
}
void solve(){
    cin>>n>>m;
    vector<pair<int,int>> cr;
    int li=0;
    for(int i=1;i<n;i++){
        int a;
        cin>>a;
        cr.clear();
        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;
        }
    }
    for(int i=1;i<n;i++){
        for(int i2=0;i2<L;i2++){
            vector<pair<int,pair<ll,int>>> xd;
            xd.clear();
            for(auto u:t2[i])
                xd.push_back({jp[u][i2].fi,{jp[u][i2].se,u}});
            sort(xd.begin(),xd.end());
            for(int i3=0;i3<xd.size();i3++){
                if(i3==0 or xd[i3-1].fi!=xd[i3].fi)
                    naj[i][i2].push_back(xd[i3].se.se);
            }
        }
    }
    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;
            }
            for(auto u:naj[a][ost]) res=min(res,zn(u,b));
            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:59: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]
   59 |         for(int i2=0;i2<t[i].size();i2++){
      |                      ~~^~~~~~~~~~~~
Main.cpp:68: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]
   68 |         for(int i2=0;i2<t[i].size();i2++){
      |                      ~~^~~~~~~~~~~~
Main.cpp:69: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]
   69 |             while(curr<t[i+1].size() and t[i+1][curr].fi<t[i][i2].se) curr++;
      |                   ~~~~^~~~~~~~~~~~~~
Main.cpp:71: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]
   71 |             if(curr==t[i+1].size()){
      |                ~~~~^~~~~~~~~~~~~~~
Main.cpp:83:17: warning: unused variable 'g' [-Wunused-variable]
   83 |             int g=jp[i][i2].fi;
      |                 ^
Main.cpp:95:28: 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]
   95 |             for(int i3=0;i3<xd.size();i3++){
      |                          ~~^~~~~~~~~~
Main.cpp:113:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |             for(int i2=0;i2<t2[a].size();i2++){
      |                          ~~^~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 47452 KB Output is correct
2 Correct 42 ms 50616 KB Output is correct
3 Correct 188 ms 64848 KB Output is correct
4 Correct 252 ms 71252 KB Output is correct
5 Correct 209 ms 66900 KB Output is correct
6 Correct 292 ms 71764 KB Output is correct
7 Correct 253 ms 71760 KB Output is correct
8 Correct 195 ms 65872 KB Output is correct
9 Correct 254 ms 71760 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 47452 KB Output is correct
2 Correct 42 ms 50616 KB Output is correct
3 Correct 188 ms 64848 KB Output is correct
4 Correct 252 ms 71252 KB Output is correct
5 Correct 209 ms 66900 KB Output is correct
6 Correct 292 ms 71764 KB Output is correct
7 Correct 253 ms 71760 KB Output is correct
8 Correct 195 ms 65872 KB Output is correct
9 Correct 254 ms 71760 KB Output is correct
10 Correct 10 ms 47448 KB Output is correct
11 Correct 221 ms 57712 KB Output is correct
12 Correct 206 ms 57684 KB Output is correct
13 Correct 189 ms 57680 KB Output is correct
14 Correct 204 ms 57684 KB Output is correct
15 Correct 215 ms 64300 KB Output is correct
16 Correct 52 ms 51408 KB Output is correct
17 Correct 255 ms 70360 KB Output is correct
18 Correct 203 ms 65108 KB Output is correct
19 Correct 236 ms 69636 KB Output is correct
20 Correct 203 ms 63568 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 47452 KB Output is correct
2 Correct 42 ms 50616 KB Output is correct
3 Correct 188 ms 64848 KB Output is correct
4 Correct 252 ms 71252 KB Output is correct
5 Correct 209 ms 66900 KB Output is correct
6 Correct 292 ms 71764 KB Output is correct
7 Correct 253 ms 71760 KB Output is correct
8 Correct 195 ms 65872 KB Output is correct
9 Correct 254 ms 71760 KB Output is correct
10 Correct 439 ms 131924 KB Output is correct
11 Correct 709 ms 156240 KB Output is correct
12 Correct 731 ms 156244 KB Output is correct
13 Correct 590 ms 151632 KB Output is correct
14 Correct 775 ms 157620 KB Output is correct
15 Correct 863 ms 157528 KB Output is correct
16 Correct 533 ms 133300 KB Output is correct
17 Correct 826 ms 157588 KB Output is correct
18 Correct 288 ms 132232 KB Output is correct
19 Correct 274 ms 131212 KB Output is correct
20 Correct 328 ms 132444 KB Output is correct
21 Correct 287 ms 132340 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 47452 KB Output is correct
2 Correct 42 ms 50616 KB Output is correct
3 Correct 188 ms 64848 KB Output is correct
4 Correct 252 ms 71252 KB Output is correct
5 Correct 209 ms 66900 KB Output is correct
6 Correct 292 ms 71764 KB Output is correct
7 Correct 253 ms 71760 KB Output is correct
8 Correct 195 ms 65872 KB Output is correct
9 Correct 254 ms 71760 KB Output is correct
10 Correct 10 ms 47448 KB Output is correct
11 Correct 221 ms 57712 KB Output is correct
12 Correct 206 ms 57684 KB Output is correct
13 Correct 189 ms 57680 KB Output is correct
14 Correct 204 ms 57684 KB Output is correct
15 Correct 215 ms 64300 KB Output is correct
16 Correct 52 ms 51408 KB Output is correct
17 Correct 255 ms 70360 KB Output is correct
18 Correct 203 ms 65108 KB Output is correct
19 Correct 236 ms 69636 KB Output is correct
20 Correct 203 ms 63568 KB Output is correct
21 Correct 439 ms 131924 KB Output is correct
22 Correct 709 ms 156240 KB Output is correct
23 Correct 731 ms 156244 KB Output is correct
24 Correct 590 ms 151632 KB Output is correct
25 Correct 775 ms 157620 KB Output is correct
26 Correct 863 ms 157528 KB Output is correct
27 Correct 533 ms 133300 KB Output is correct
28 Correct 826 ms 157588 KB Output is correct
29 Correct 288 ms 132232 KB Output is correct
30 Correct 274 ms 131212 KB Output is correct
31 Correct 328 ms 132444 KB Output is correct
32 Correct 287 ms 132340 KB Output is correct
33 Correct 927 ms 114776 KB Output is correct
34 Correct 855 ms 114808 KB Output is correct
35 Correct 712 ms 107980 KB Output is correct
36 Correct 723 ms 108112 KB Output is correct
37 Correct 503 ms 114516 KB Output is correct
38 Correct 417 ms 117568 KB Output is correct
39 Correct 517 ms 133240 KB Output is correct
40 Correct 382 ms 100944 KB Output is correct
41 Correct 434 ms 115536 KB Output is correct
42 Correct 567 ms 135644 KB Output is correct
43 Correct 423 ms 107348 KB Output is correct
44 Correct 478 ms 111444 KB Output is correct
45 Correct 235 ms 114452 KB Output is correct
46 Correct 198 ms 96852 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 47452 KB Output is correct
2 Correct 7 ms 47696 KB Output is correct
3 Correct 1514 ms 81744 KB Output is correct
4 Correct 1567 ms 81956 KB Output is correct
5 Correct 1548 ms 81732 KB Output is correct
6 Correct 1549 ms 81920 KB Output is correct
7 Correct 1679 ms 81868 KB Output is correct
8 Correct 147 ms 66644 KB Output is correct
9 Correct 123 ms 77824 KB Output is correct
10 Correct 107 ms 65728 KB Output is correct
11 Correct 332 ms 132172 KB Output is correct
12 Correct 264 ms 114356 KB Output is correct
13 Correct 182 ms 96704 KB Output is correct
14 Correct 219 ms 88804 KB Output is correct
15 Correct 187 ms 88280 KB Output is correct
16 Correct 159 ms 90960 KB Output is correct
17 Correct 227 ms 90468 KB Output is correct
18 Correct 184 ms 78572 KB Output is correct
19 Correct 193 ms 77136 KB Output is correct
20 Correct 155 ms 112980 KB Output is correct
21 Correct 214 ms 114908 KB Output is correct
22 Correct 139 ms 94552 KB Output is correct
23 Correct 211 ms 96388 KB Output is correct
24 Correct 244 ms 96912 KB Output is correct
25 Correct 188 ms 94740 KB Output is correct
26 Correct 246 ms 99056 KB Output is correct
27 Correct 237 ms 131924 KB Output is correct
28 Correct 274 ms 133464 KB Output is correct
29 Correct 294 ms 133332 KB Output is correct
30 Correct 115 ms 62624 KB Output is correct
31 Correct 43 ms 50904 KB Output is correct
32 Correct 110 ms 64340 KB Output is correct
33 Correct 60 ms 51976 KB Output is correct
34 Correct 110 ms 56916 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 47452 KB Output is correct
2 Correct 42 ms 50616 KB Output is correct
3 Correct 188 ms 64848 KB Output is correct
4 Correct 252 ms 71252 KB Output is correct
5 Correct 209 ms 66900 KB Output is correct
6 Correct 292 ms 71764 KB Output is correct
7 Correct 253 ms 71760 KB Output is correct
8 Correct 195 ms 65872 KB Output is correct
9 Correct 254 ms 71760 KB Output is correct
10 Correct 10 ms 47448 KB Output is correct
11 Correct 221 ms 57712 KB Output is correct
12 Correct 206 ms 57684 KB Output is correct
13 Correct 189 ms 57680 KB Output is correct
14 Correct 204 ms 57684 KB Output is correct
15 Correct 215 ms 64300 KB Output is correct
16 Correct 52 ms 51408 KB Output is correct
17 Correct 255 ms 70360 KB Output is correct
18 Correct 203 ms 65108 KB Output is correct
19 Correct 236 ms 69636 KB Output is correct
20 Correct 203 ms 63568 KB Output is correct
21 Correct 439 ms 131924 KB Output is correct
22 Correct 709 ms 156240 KB Output is correct
23 Correct 731 ms 156244 KB Output is correct
24 Correct 590 ms 151632 KB Output is correct
25 Correct 775 ms 157620 KB Output is correct
26 Correct 863 ms 157528 KB Output is correct
27 Correct 533 ms 133300 KB Output is correct
28 Correct 826 ms 157588 KB Output is correct
29 Correct 288 ms 132232 KB Output is correct
30 Correct 274 ms 131212 KB Output is correct
31 Correct 328 ms 132444 KB Output is correct
32 Correct 287 ms 132340 KB Output is correct
33 Correct 927 ms 114776 KB Output is correct
34 Correct 855 ms 114808 KB Output is correct
35 Correct 712 ms 107980 KB Output is correct
36 Correct 723 ms 108112 KB Output is correct
37 Correct 503 ms 114516 KB Output is correct
38 Correct 417 ms 117568 KB Output is correct
39 Correct 517 ms 133240 KB Output is correct
40 Correct 382 ms 100944 KB Output is correct
41 Correct 434 ms 115536 KB Output is correct
42 Correct 567 ms 135644 KB Output is correct
43 Correct 423 ms 107348 KB Output is correct
44 Correct 478 ms 111444 KB Output is correct
45 Correct 235 ms 114452 KB Output is correct
46 Correct 198 ms 96852 KB Output is correct
47 Correct 7 ms 47452 KB Output is correct
48 Correct 7 ms 47696 KB Output is correct
49 Correct 1514 ms 81744 KB Output is correct
50 Correct 1567 ms 81956 KB Output is correct
51 Correct 1548 ms 81732 KB Output is correct
52 Correct 1549 ms 81920 KB Output is correct
53 Correct 1679 ms 81868 KB Output is correct
54 Correct 147 ms 66644 KB Output is correct
55 Correct 123 ms 77824 KB Output is correct
56 Correct 107 ms 65728 KB Output is correct
57 Correct 332 ms 132172 KB Output is correct
58 Correct 264 ms 114356 KB Output is correct
59 Correct 182 ms 96704 KB Output is correct
60 Correct 219 ms 88804 KB Output is correct
61 Correct 187 ms 88280 KB Output is correct
62 Correct 159 ms 90960 KB Output is correct
63 Correct 227 ms 90468 KB Output is correct
64 Correct 184 ms 78572 KB Output is correct
65 Correct 193 ms 77136 KB Output is correct
66 Correct 155 ms 112980 KB Output is correct
67 Correct 214 ms 114908 KB Output is correct
68 Correct 139 ms 94552 KB Output is correct
69 Correct 211 ms 96388 KB Output is correct
70 Correct 244 ms 96912 KB Output is correct
71 Correct 188 ms 94740 KB Output is correct
72 Correct 246 ms 99056 KB Output is correct
73 Correct 237 ms 131924 KB Output is correct
74 Correct 274 ms 133464 KB Output is correct
75 Correct 294 ms 133332 KB Output is correct
76 Correct 115 ms 62624 KB Output is correct
77 Correct 43 ms 50904 KB Output is correct
78 Correct 110 ms 64340 KB Output is correct
79 Correct 60 ms 51976 KB Output is correct
80 Correct 110 ms 56916 KB Output is correct
81 Execution timed out 3066 ms 90528 KB Time limit exceeded
82 Halted 0 ms 0 KB -