oj.uz

Submission #1061637

# Submission time Handle Problem Language Result Execution time Memory
1061637 2024-08-16T11:21:21 Z new_acc Escape Route 2 (JOI24_escape2) C++14
90 / 100
 3000 ms 155024 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--;
    if(num[a].fi==b){
        return t[b][num[a].se].se-t[b][num[a].se].fi;
    }
    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;
        }
    }
    vector<pair<int,pair<ll,int>>> xd;
    for(int i=1;i<n;i++){
        for(int i2=0;i2<L;i2++){
            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(auto u:t2[a]) res=min(res,zn(u,b));
            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:62: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]
   62 |         for(int i2=0;i2<t[i].size();i2++){
      |                      ~~^~~~~~~~~~~~
Main.cpp:71: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]
   71 |         for(int i2=0;i2<t[i].size();i2++){
      |                      ~~^~~~~~~~~~~~
Main.cpp:72: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]
   72 |             while(curr<t[i+1].size() and t[i+1][curr].fi<t[i][i2].se) curr++;
      |                   ~~~~^~~~~~~~~~~~~~
Main.cpp:74: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]
   74 |             if(curr==t[i+1].size()){
      |                ~~~~^~~~~~~~~~~~~~~
Main.cpp:86:17: warning: unused variable 'g' [-Wunused-variable]
   86 |             int g=jp[i][i2].fi;
      |                 ^
Main.cpp:98: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]
   98 |             for(int i3=0;i3<xd.size();i3++){
      |                          ~~^~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 47452 KB Output is correct
2 Correct 42 ms 50692 KB Output is correct
3 Correct 205 ms 64772 KB Output is correct
4 Correct 305 ms 70488 KB Output is correct
5 Correct 267 ms 65616 KB Output is correct
6 Correct 305 ms 70164 KB Output is correct
7 Correct 399 ms 70268 KB Output is correct
8 Correct 195 ms 64336 KB Output is correct
9 Correct 298 ms 70220 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 47452 KB Output is correct
2 Correct 42 ms 50692 KB Output is correct
3 Correct 205 ms 64772 KB Output is correct
4 Correct 305 ms 70488 KB Output is correct
5 Correct 267 ms 65616 KB Output is correct
6 Correct 305 ms 70164 KB Output is correct
7 Correct 399 ms 70268 KB Output is correct
8 Correct 195 ms 64336 KB Output is correct
9 Correct 298 ms 70220 KB Output is correct
10 Correct 7 ms 47452 KB Output is correct
11 Correct 247 ms 56508 KB Output is correct
12 Correct 256 ms 56272 KB Output is correct
13 Correct 229 ms 56448 KB Output is correct
14 Correct 240 ms 56368 KB Output is correct
15 Correct 273 ms 63148 KB Output is correct
16 Correct 48 ms 50660 KB Output is correct
17 Correct 272 ms 68836 KB Output is correct
18 Correct 247 ms 63672 KB Output is correct
19 Correct 302 ms 68264 KB Output is correct
20 Correct 315 ms 62368 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 47452 KB Output is correct
2 Correct 42 ms 50692 KB Output is correct
3 Correct 205 ms 64772 KB Output is correct
4 Correct 305 ms 70488 KB Output is correct
5 Correct 267 ms 65616 KB Output is correct
6 Correct 305 ms 70164 KB Output is correct
7 Correct 399 ms 70268 KB Output is correct
8 Correct 195 ms 64336 KB Output is correct
9 Correct 298 ms 70220 KB Output is correct
10 Correct 539 ms 129864 KB Output is correct
11 Correct 832 ms 153720 KB Output is correct
12 Correct 717 ms 153692 KB Output is correct
13 Correct 572 ms 149312 KB Output is correct
14 Correct 823 ms 154976 KB Output is correct
15 Correct 704 ms 155004 KB Output is correct
16 Correct 542 ms 131156 KB Output is correct
17 Correct 736 ms 155024 KB Output is correct
18 Correct 276 ms 130628 KB Output is correct
19 Correct 302 ms 129616 KB Output is correct
20 Correct 266 ms 130908 KB Output is correct
21 Correct 296 ms 130772 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 47452 KB Output is correct
2 Correct 42 ms 50692 KB Output is correct
3 Correct 205 ms 64772 KB Output is correct
4 Correct 305 ms 70488 KB Output is correct
5 Correct 267 ms 65616 KB Output is correct
6 Correct 305 ms 70164 KB Output is correct
7 Correct 399 ms 70268 KB Output is correct
8 Correct 195 ms 64336 KB Output is correct
9 Correct 298 ms 70220 KB Output is correct
10 Correct 7 ms 47452 KB Output is correct
11 Correct 247 ms 56508 KB Output is correct
12 Correct 256 ms 56272 KB Output is correct
13 Correct 229 ms 56448 KB Output is correct
14 Correct 240 ms 56368 KB Output is correct
15 Correct 273 ms 63148 KB Output is correct
16 Correct 48 ms 50660 KB Output is correct
17 Correct 272 ms 68836 KB Output is correct
18 Correct 247 ms 63672 KB Output is correct
19 Correct 302 ms 68264 KB Output is correct
20 Correct 315 ms 62368 KB Output is correct
21 Correct 539 ms 129864 KB Output is correct
22 Correct 832 ms 153720 KB Output is correct
23 Correct 717 ms 153692 KB Output is correct
24 Correct 572 ms 149312 KB Output is correct
25 Correct 823 ms 154976 KB Output is correct
26 Correct 704 ms 155004 KB Output is correct
27 Correct 542 ms 131156 KB Output is correct
28 Correct 736 ms 155024 KB Output is correct
29 Correct 276 ms 130628 KB Output is correct
30 Correct 302 ms 129616 KB Output is correct
31 Correct 266 ms 130908 KB Output is correct
32 Correct 296 ms 130772 KB Output is correct
33 Correct 960 ms 112596 KB Output is correct
34 Correct 979 ms 112308 KB Output is correct
35 Correct 777 ms 105788 KB Output is correct
36 Correct 884 ms 105808 KB Output is correct
37 Correct 535 ms 112208 KB Output is correct
38 Correct 393 ms 115404 KB Output is correct
39 Correct 533 ms 130780 KB Output is correct
40 Correct 440 ms 98792 KB Output is correct
41 Correct 479 ms 113120 KB Output is correct
42 Correct 649 ms 132920 KB Output is correct
43 Correct 380 ms 104848 KB Output is correct
44 Correct 557 ms 109320 KB Output is correct
45 Correct 240 ms 112924 KB Output is correct
46 Correct 204 ms 95312 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 47608 KB Output is correct
3 Correct 1818 ms 80436 KB Output is correct
4 Correct 1811 ms 80408 KB Output is correct
5 Correct 2032 ms 80328 KB Output is correct
6 Correct 2120 ms 80432 KB Output is correct
7 Correct 2072 ms 80256 KB Output is correct
8 Correct 178 ms 65252 KB Output is correct
9 Correct 133 ms 76140 KB Output is correct
10 Correct 135 ms 63880 KB Output is correct
11 Correct 269 ms 130560 KB Output is correct
12 Correct 214 ms 112724 KB Output is correct
13 Correct 179 ms 95312 KB Output is correct
14 Correct 216 ms 87628 KB Output is correct
15 Correct 197 ms 86960 KB Output is correct
16 Correct 206 ms 89624 KB Output is correct
17 Correct 181 ms 88908 KB Output is correct
18 Correct 197 ms 77108 KB Output is correct
19 Correct 161 ms 75640 KB Output is correct
20 Correct 152 ms 111440 KB Output is correct
21 Correct 197 ms 113364 KB Output is correct
22 Correct 165 ms 93012 KB Output is correct
23 Correct 175 ms 94804 KB Output is correct
24 Correct 230 ms 95884 KB Output is correct
25 Correct 160 ms 92852 KB Output is correct
26 Correct 219 ms 96856 KB Output is correct
27 Correct 267 ms 129620 KB Output is correct
28 Correct 332 ms 130712 KB Output is correct
29 Correct 341 ms 130680 KB Output is correct
30 Correct 114 ms 60280 KB Output is correct
31 Correct 55 ms 48856 KB Output is correct
32 Correct 132 ms 62036 KB Output is correct
33 Correct 66 ms 49664 KB Output is correct
34 Correct 115 ms 54848 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 47452 KB Output is correct
2 Correct 42 ms 50692 KB Output is correct
3 Correct 205 ms 64772 KB Output is correct
4 Correct 305 ms 70488 KB Output is correct
5 Correct 267 ms 65616 KB Output is correct
6 Correct 305 ms 70164 KB Output is correct
7 Correct 399 ms 70268 KB Output is correct
8 Correct 195 ms 64336 KB Output is correct
9 Correct 298 ms 70220 KB Output is correct
10 Correct 7 ms 47452 KB Output is correct
11 Correct 247 ms 56508 KB Output is correct
12 Correct 256 ms 56272 KB Output is correct
13 Correct 229 ms 56448 KB Output is correct
14 Correct 240 ms 56368 KB Output is correct
15 Correct 273 ms 63148 KB Output is correct
16 Correct 48 ms 50660 KB Output is correct
17 Correct 272 ms 68836 KB Output is correct
18 Correct 247 ms 63672 KB Output is correct
19 Correct 302 ms 68264 KB Output is correct
20 Correct 315 ms 62368 KB Output is correct
21 Correct 539 ms 129864 KB Output is correct
22 Correct 832 ms 153720 KB Output is correct
23 Correct 717 ms 153692 KB Output is correct
24 Correct 572 ms 149312 KB Output is correct
25 Correct 823 ms 154976 KB Output is correct
26 Correct 704 ms 155004 KB Output is correct
27 Correct 542 ms 131156 KB Output is correct
28 Correct 736 ms 155024 KB Output is correct
29 Correct 276 ms 130628 KB Output is correct
30 Correct 302 ms 129616 KB Output is correct
31 Correct 266 ms 130908 KB Output is correct
32 Correct 296 ms 130772 KB Output is correct
33 Correct 960 ms 112596 KB Output is correct
34 Correct 979 ms 112308 KB Output is correct
35 Correct 777 ms 105788 KB Output is correct
36 Correct 884 ms 105808 KB Output is correct
37 Correct 535 ms 112208 KB Output is correct
38 Correct 393 ms 115404 KB Output is correct
39 Correct 533 ms 130780 KB Output is correct
40 Correct 440 ms 98792 KB Output is correct
41 Correct 479 ms 113120 KB Output is correct
42 Correct 649 ms 132920 KB Output is correct
43 Correct 380 ms 104848 KB Output is correct
44 Correct 557 ms 109320 KB Output is correct
45 Correct 240 ms 112924 KB Output is correct
46 Correct 204 ms 95312 KB Output is correct
47 Correct 7 ms 47452 KB Output is correct
48 Correct 7 ms 47608 KB Output is correct
49 Correct 1818 ms 80436 KB Output is correct
50 Correct 1811 ms 80408 KB Output is correct
51 Correct 2032 ms 80328 KB Output is correct
52 Correct 2120 ms 80432 KB Output is correct
53 Correct 2072 ms 80256 KB Output is correct
54 Correct 178 ms 65252 KB Output is correct
55 Correct 133 ms 76140 KB Output is correct
56 Correct 135 ms 63880 KB Output is correct
57 Correct 269 ms 130560 KB Output is correct
58 Correct 214 ms 112724 KB Output is correct
59 Correct 179 ms 95312 KB Output is correct
60 Correct 216 ms 87628 KB Output is correct
61 Correct 197 ms 86960 KB Output is correct
62 Correct 206 ms 89624 KB Output is correct
63 Correct 181 ms 88908 KB Output is correct
64 Correct 197 ms 77108 KB Output is correct
65 Correct 161 ms 75640 KB Output is correct
66 Correct 152 ms 111440 KB Output is correct
67 Correct 197 ms 113364 KB Output is correct
68 Correct 165 ms 93012 KB Output is correct
69 Correct 175 ms 94804 KB Output is correct
70 Correct 230 ms 95884 KB Output is correct
71 Correct 160 ms 92852 KB Output is correct
72 Correct 219 ms 96856 KB Output is correct
73 Correct 267 ms 129620 KB Output is correct
74 Correct 332 ms 130712 KB Output is correct
75 Correct 341 ms 130680 KB Output is correct
76 Correct 114 ms 60280 KB Output is correct
77 Correct 55 ms 48856 KB Output is correct
78 Correct 132 ms 62036 KB Output is correct
79 Correct 66 ms 49664 KB Output is correct
80 Correct 115 ms 54848 KB Output is correct
81 Execution timed out 3084 ms 86432 KB Time limit exceeded
82 Halted 0 ms 0 KB -