oj.uz

Submission #1061619

# Submission time Handle Problem Language Result Execution time Memory
1061619 2024-08-16T11:16:48 Z new_acc Escape Route 2 (JOI24_escape2) C++14
90 / 100
 3000 ms 557652 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=1e6+10;
const int SS=1<<1;
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;
        }
    }
    for(int i=1;i<n;i++){
        for(int i2=0;i2<L;i2++){
            vector<pair<int,pair<ll,int>>> xd;
            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:63: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]
   63 |         for(int i2=0;i2<t[i].size();i2++){
      |                      ~~^~~~~~~~~~~~
Main.cpp:72: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]
   72 |         for(int i2=0;i2<t[i].size();i2++){
      |                      ~~^~~~~~~~~~~~
Main.cpp:73: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]
   73 |             while(curr<t[i+1].size() and t[i+1][curr].fi<t[i][i2].se) curr++;
      |                   ~~~~^~~~~~~~~~~~~~
Main.cpp:75: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]
   75 |             if(curr==t[i+1].size()){
      |                ~~~~^~~~~~~~~~~~~~~
Main.cpp:87:17: warning: unused variable 'g' [-Wunused-variable]
   87 |             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 149 ms 447316 KB Output is correct
2 Correct 175 ms 451152 KB Output is correct
3 Correct 301 ms 466320 KB Output is correct
4 Correct 376 ms 471516 KB Output is correct
5 Correct 336 ms 466108 KB Output is correct
6 Correct 404 ms 470580 KB Output is correct
7 Correct 393 ms 470608 KB Output is correct
8 Correct 321 ms 464720 KB Output is correct
9 Correct 386 ms 470612 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 447316 KB Output is correct
2 Correct 175 ms 451152 KB Output is correct
3 Correct 301 ms 466320 KB Output is correct
4 Correct 376 ms 471516 KB Output is correct
5 Correct 336 ms 466108 KB Output is correct
6 Correct 404 ms 470580 KB Output is correct
7 Correct 393 ms 470608 KB Output is correct
8 Correct 321 ms 464720 KB Output is correct
9 Correct 386 ms 470612 KB Output is correct
10 Correct 139 ms 447316 KB Output is correct
11 Correct 344 ms 456880 KB Output is correct
12 Correct 332 ms 456780 KB Output is correct
13 Correct 335 ms 456616 KB Output is correct
14 Correct 355 ms 456784 KB Output is correct
15 Correct 355 ms 463440 KB Output is correct
16 Correct 187 ms 450300 KB Output is correct
17 Correct 421 ms 469328 KB Output is correct
18 Correct 375 ms 463956 KB Output is correct
19 Correct 392 ms 468420 KB Output is correct
20 Correct 333 ms 462548 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 447316 KB Output is correct
2 Correct 175 ms 451152 KB Output is correct
3 Correct 301 ms 466320 KB Output is correct
4 Correct 376 ms 471516 KB Output is correct
5 Correct 336 ms 466108 KB Output is correct
6 Correct 404 ms 470580 KB Output is correct
7 Correct 393 ms 470608 KB Output is correct
8 Correct 321 ms 464720 KB Output is correct
9 Correct 386 ms 470612 KB Output is correct
10 Correct 600 ms 530792 KB Output is correct
11 Correct 978 ms 556276 KB Output is correct
12 Correct 990 ms 556088 KB Output is correct
13 Correct 736 ms 551760 KB Output is correct
14 Correct 911 ms 557480 KB Output is correct
15 Correct 883 ms 557652 KB Output is correct
16 Correct 668 ms 532052 KB Output is correct
17 Correct 899 ms 557516 KB Output is correct
18 Correct 428 ms 532308 KB Output is correct
19 Correct 427 ms 531544 KB Output is correct
20 Correct 439 ms 532560 KB Output is correct
21 Correct 423 ms 532564 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 447316 KB Output is correct
2 Correct 175 ms 451152 KB Output is correct
3 Correct 301 ms 466320 KB Output is correct
4 Correct 376 ms 471516 KB Output is correct
5 Correct 336 ms 466108 KB Output is correct
6 Correct 404 ms 470580 KB Output is correct
7 Correct 393 ms 470608 KB Output is correct
8 Correct 321 ms 464720 KB Output is correct
9 Correct 386 ms 470612 KB Output is correct
10 Correct 139 ms 447316 KB Output is correct
11 Correct 344 ms 456880 KB Output is correct
12 Correct 332 ms 456780 KB Output is correct
13 Correct 335 ms 456616 KB Output is correct
14 Correct 355 ms 456784 KB Output is correct
15 Correct 355 ms 463440 KB Output is correct
16 Correct 187 ms 450300 KB Output is correct
17 Correct 421 ms 469328 KB Output is correct
18 Correct 375 ms 463956 KB Output is correct
19 Correct 392 ms 468420 KB Output is correct
20 Correct 333 ms 462548 KB Output is correct
21 Correct 600 ms 530792 KB Output is correct
22 Correct 978 ms 556276 KB Output is correct
23 Correct 990 ms 556088 KB Output is correct
24 Correct 736 ms 551760 KB Output is correct
25 Correct 911 ms 557480 KB Output is correct
26 Correct 883 ms 557652 KB Output is correct
27 Correct 668 ms 532052 KB Output is correct
28 Correct 899 ms 557516 KB Output is correct
29 Correct 428 ms 532308 KB Output is correct
30 Correct 427 ms 531544 KB Output is correct
31 Correct 439 ms 532560 KB Output is correct
32 Correct 423 ms 532564 KB Output is correct
33 Correct 1057 ms 514896 KB Output is correct
34 Correct 1039 ms 514900 KB Output is correct
35 Correct 964 ms 507476 KB Output is correct
36 Correct 929 ms 507520 KB Output is correct
37 Correct 669 ms 513872 KB Output is correct
38 Correct 575 ms 516264 KB Output is correct
39 Correct 694 ms 533332 KB Output is correct
40 Correct 537 ms 498516 KB Output is correct
41 Correct 634 ms 514640 KB Output is correct
42 Correct 798 ms 534464 KB Output is correct
43 Correct 567 ms 505176 KB Output is correct
44 Correct 674 ms 509920 KB Output is correct
45 Correct 416 ms 514644 KB Output is correct
46 Correct 357 ms 496980 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 447440 KB Output is correct
2 Correct 145 ms 447296 KB Output is correct
3 Correct 1871 ms 482036 KB Output is correct
4 Correct 1908 ms 482180 KB Output is correct
5 Correct 1906 ms 482076 KB Output is correct
6 Correct 2043 ms 482132 KB Output is correct
7 Correct 1896 ms 481928 KB Output is correct
8 Correct 372 ms 464980 KB Output is correct
9 Correct 257 ms 478032 KB Output is correct
10 Correct 229 ms 464292 KB Output is correct
11 Correct 472 ms 532280 KB Output is correct
12 Correct 420 ms 514648 KB Output is correct
13 Correct 354 ms 496992 KB Output is correct
14 Correct 353 ms 489184 KB Output is correct
15 Correct 377 ms 488572 KB Output is correct
16 Correct 356 ms 491344 KB Output is correct
17 Correct 392 ms 490636 KB Output is correct
18 Correct 347 ms 478664 KB Output is correct
19 Correct 325 ms 477524 KB Output is correct
20 Correct 347 ms 513216 KB Output is correct
21 Correct 364 ms 515152 KB Output is correct
22 Correct 294 ms 494816 KB Output is correct
23 Correct 335 ms 496724 KB Output is correct
24 Correct 372 ms 497292 KB Output is correct
25 Correct 338 ms 494360 KB Output is correct
26 Correct 376 ms 498368 KB Output is correct
27 Correct 420 ms 531420 KB Output is correct
28 Correct 441 ms 532564 KB Output is correct
29 Correct 446 ms 532564 KB Output is correct
30 Correct 272 ms 461260 KB Output is correct
31 Correct 182 ms 449292 KB Output is correct
32 Correct 244 ms 461704 KB Output is correct
33 Correct 201 ms 450272 KB Output is correct
34 Correct 235 ms 455252 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 447316 KB Output is correct
2 Correct 175 ms 451152 KB Output is correct
3 Correct 301 ms 466320 KB Output is correct
4 Correct 376 ms 471516 KB Output is correct
5 Correct 336 ms 466108 KB Output is correct
6 Correct 404 ms 470580 KB Output is correct
7 Correct 393 ms 470608 KB Output is correct
8 Correct 321 ms 464720 KB Output is correct
9 Correct 386 ms 470612 KB Output is correct
10 Correct 139 ms 447316 KB Output is correct
11 Correct 344 ms 456880 KB Output is correct
12 Correct 332 ms 456780 KB Output is correct
13 Correct 335 ms 456616 KB Output is correct
14 Correct 355 ms 456784 KB Output is correct
15 Correct 355 ms 463440 KB Output is correct
16 Correct 187 ms 450300 KB Output is correct
17 Correct 421 ms 469328 KB Output is correct
18 Correct 375 ms 463956 KB Output is correct
19 Correct 392 ms 468420 KB Output is correct
20 Correct 333 ms 462548 KB Output is correct
21 Correct 600 ms 530792 KB Output is correct
22 Correct 978 ms 556276 KB Output is correct
23 Correct 990 ms 556088 KB Output is correct
24 Correct 736 ms 551760 KB Output is correct
25 Correct 911 ms 557480 KB Output is correct
26 Correct 883 ms 557652 KB Output is correct
27 Correct 668 ms 532052 KB Output is correct
28 Correct 899 ms 557516 KB Output is correct
29 Correct 428 ms 532308 KB Output is correct
30 Correct 427 ms 531544 KB Output is correct
31 Correct 439 ms 532560 KB Output is correct
32 Correct 423 ms 532564 KB Output is correct
33 Correct 1057 ms 514896 KB Output is correct
34 Correct 1039 ms 514900 KB Output is correct
35 Correct 964 ms 507476 KB Output is correct
36 Correct 929 ms 507520 KB Output is correct
37 Correct 669 ms 513872 KB Output is correct
38 Correct 575 ms 516264 KB Output is correct
39 Correct 694 ms 533332 KB Output is correct
40 Correct 537 ms 498516 KB Output is correct
41 Correct 634 ms 514640 KB Output is correct
42 Correct 798 ms 534464 KB Output is correct
43 Correct 567 ms 505176 KB Output is correct
44 Correct 674 ms 509920 KB Output is correct
45 Correct 416 ms 514644 KB Output is correct
46 Correct 357 ms 496980 KB Output is correct
47 Correct 138 ms 447440 KB Output is correct
48 Correct 145 ms 447296 KB Output is correct
49 Correct 1871 ms 482036 KB Output is correct
50 Correct 1908 ms 482180 KB Output is correct
51 Correct 1906 ms 482076 KB Output is correct
52 Correct 2043 ms 482132 KB Output is correct
53 Correct 1896 ms 481928 KB Output is correct
54 Correct 372 ms 464980 KB Output is correct
55 Correct 257 ms 478032 KB Output is correct
56 Correct 229 ms 464292 KB Output is correct
57 Correct 472 ms 532280 KB Output is correct
58 Correct 420 ms 514648 KB Output is correct
59 Correct 354 ms 496992 KB Output is correct
60 Correct 353 ms 489184 KB Output is correct
61 Correct 377 ms 488572 KB Output is correct
62 Correct 356 ms 491344 KB Output is correct
63 Correct 392 ms 490636 KB Output is correct
64 Correct 347 ms 478664 KB Output is correct
65 Correct 325 ms 477524 KB Output is correct
66 Correct 347 ms 513216 KB Output is correct
67 Correct 364 ms 515152 KB Output is correct
68 Correct 294 ms 494816 KB Output is correct
69 Correct 335 ms 496724 KB Output is correct
70 Correct 372 ms 497292 KB Output is correct
71 Correct 338 ms 494360 KB Output is correct
72 Correct 376 ms 498368 KB Output is correct
73 Correct 420 ms 531420 KB Output is correct
74 Correct 441 ms 532564 KB Output is correct
75 Correct 446 ms 532564 KB Output is correct
76 Correct 272 ms 461260 KB Output is correct
77 Correct 182 ms 449292 KB Output is correct
78 Correct 244 ms 461704 KB Output is correct
79 Correct 201 ms 450272 KB Output is correct
80 Correct 235 ms 455252 KB Output is correct
81 Execution timed out 3111 ms 488964 KB Time limit exceeded
82 Halted 0 ms 0 KB -