oj.uz

Submission #1061705

# Submission time Handle Problem Language Result Execution time Memory
1061705 2024-08-16T12:02:57 Z new_acc Escape Route 2 (JOI24_escape2) C++14
90 / 100
 3000 ms 107856 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 res=0,curr=0;
    int g=0;
    b--;
    for(int i=ost;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;
        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:58: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]
   58 |         for(int i2=0;i2<t[i].size();i2++){
      |                      ~~^~~~~~~~~~~~
Main.cpp:67: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]
   67 |         for(int i2=0;i2<t[i].size();i2++){
      |                      ~~^~~~~~~~~~~~
Main.cpp:68: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]
   68 |             while(curr<t[i+1].size() and t[i+1][curr].fi<t[i][i2].se) curr++;
      |                   ~~~~^~~~~~~~~~~~~~
Main.cpp:70: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]
   70 |             if(curr==t[i+1].size()){
      |                ~~~~^~~~~~~~~~~~~~~
Main.cpp:82:17: warning: unused variable 'g' [-Wunused-variable]
   82 |             int g=jp[i][i2].fi;
      |                 ^
Main.cpp:100:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |             for(int i2=0;i2<t2[a].size();i2++){
      |                          ~~^~~~~~~~~~~~~
Main.cpp:114: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]
  114 |                 for(int i3=0;i3<pom.size();i3++){
      |                              ~~^~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 47452 KB Output is correct
2 Correct 44 ms 50616 KB Output is correct
3 Correct 173 ms 64436 KB Output is correct
4 Correct 225 ms 69776 KB Output is correct
5 Correct 173 ms 65200 KB Output is correct
6 Correct 236 ms 69712 KB Output is correct
7 Correct 257 ms 69456 KB Output is correct
8 Correct 181 ms 64172 KB Output is correct
9 Correct 236 ms 69456 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 44 ms 50616 KB Output is correct
3 Correct 173 ms 64436 KB Output is correct
4 Correct 225 ms 69776 KB Output is correct
5 Correct 173 ms 65200 KB Output is correct
6 Correct 236 ms 69712 KB Output is correct
7 Correct 257 ms 69456 KB Output is correct
8 Correct 181 ms 64172 KB Output is correct
9 Correct 236 ms 69456 KB Output is correct
10 Correct 7 ms 47448 KB Output is correct
11 Correct 169 ms 56272 KB Output is correct
12 Correct 181 ms 56224 KB Output is correct
13 Correct 165 ms 56148 KB Output is correct
14 Correct 174 ms 56144 KB Output is correct
15 Correct 189 ms 62800 KB Output is correct
16 Correct 42 ms 50680 KB Output is correct
17 Correct 216 ms 68320 KB Output is correct
18 Correct 181 ms 63568 KB Output is correct
19 Correct 214 ms 67924 KB Output is correct
20 Correct 196 ms 62288 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 44 ms 50616 KB Output is correct
3 Correct 173 ms 64436 KB Output is correct
4 Correct 225 ms 69776 KB Output is correct
5 Correct 173 ms 65200 KB Output is correct
6 Correct 236 ms 69712 KB Output is correct
7 Correct 257 ms 69456 KB Output is correct
8 Correct 181 ms 64172 KB Output is correct
9 Correct 236 ms 69456 KB Output is correct
10 Correct 338 ms 90452 KB Output is correct
11 Correct 569 ms 104200 KB Output is correct
12 Correct 614 ms 104192 KB Output is correct
13 Correct 480 ms 100984 KB Output is correct
14 Correct 590 ms 107856 KB Output is correct
15 Correct 617 ms 107856 KB Output is correct
16 Correct 401 ms 93520 KB Output is correct
17 Correct 624 ms 107800 KB Output is correct
18 Correct 173 ms 84308 KB Output is correct
19 Correct 162 ms 83812 KB Output is correct
20 Correct 181 ms 85328 KB Output is correct
21 Correct 168 ms 85328 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 44 ms 50616 KB Output is correct
3 Correct 173 ms 64436 KB Output is correct
4 Correct 225 ms 69776 KB Output is correct
5 Correct 173 ms 65200 KB Output is correct
6 Correct 236 ms 69712 KB Output is correct
7 Correct 257 ms 69456 KB Output is correct
8 Correct 181 ms 64172 KB Output is correct
9 Correct 236 ms 69456 KB Output is correct
10 Correct 7 ms 47448 KB Output is correct
11 Correct 169 ms 56272 KB Output is correct
12 Correct 181 ms 56224 KB Output is correct
13 Correct 165 ms 56148 KB Output is correct
14 Correct 174 ms 56144 KB Output is correct
15 Correct 189 ms 62800 KB Output is correct
16 Correct 42 ms 50680 KB Output is correct
17 Correct 216 ms 68320 KB Output is correct
18 Correct 181 ms 63568 KB Output is correct
19 Correct 214 ms 67924 KB Output is correct
20 Correct 196 ms 62288 KB Output is correct
21 Correct 338 ms 90452 KB Output is correct
22 Correct 569 ms 104200 KB Output is correct
23 Correct 614 ms 104192 KB Output is correct
24 Correct 480 ms 100984 KB Output is correct
25 Correct 590 ms 107856 KB Output is correct
26 Correct 617 ms 107856 KB Output is correct
27 Correct 401 ms 93520 KB Output is correct
28 Correct 624 ms 107800 KB Output is correct
29 Correct 173 ms 84308 KB Output is correct
30 Correct 162 ms 83812 KB Output is correct
31 Correct 181 ms 85328 KB Output is correct
32 Correct 168 ms 85328 KB Output is correct
33 Correct 735 ms 101540 KB Output is correct
34 Correct 745 ms 101640 KB Output is correct
35 Correct 665 ms 97852 KB Output is correct
36 Correct 647 ms 97808 KB Output is correct
37 Correct 460 ms 99500 KB Output is correct
38 Correct 367 ms 89864 KB Output is correct
39 Correct 447 ms 98132 KB Output is correct
40 Correct 347 ms 88656 KB Output is correct
41 Correct 420 ms 90964 KB Output is correct
42 Correct 531 ms 102736 KB Output is correct
43 Correct 368 ms 90708 KB Output is correct
44 Correct 438 ms 95060 KB Output is correct
45 Correct 165 ms 82520 KB Output is correct
46 Correct 162 ms 80464 KB Output is correct

Subtask #5
36.0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 47448 KB Output is correct
2 Correct 7 ms 47452 KB Output is correct
3 Correct 800 ms 80380 KB Output is correct
4 Correct 823 ms 80212 KB Output is correct
5 Correct 798 ms 80212 KB Output is correct
6 Correct 833 ms 80096 KB Output is correct
7 Correct 838 ms 80216 KB Output is correct
8 Correct 100 ms 65204 KB Output is correct
9 Correct 94 ms 76116 KB Output is correct
10 Correct 40 ms 62156 KB Output is correct
11 Correct 181 ms 84516 KB Output is correct
12 Correct 167 ms 82512 KB Output is correct
13 Correct 156 ms 80460 KB Output is correct
14 Correct 115 ms 77896 KB Output is correct
15 Correct 127 ms 77928 KB Output is correct
16 Correct 110 ms 79956 KB Output is correct
17 Correct 127 ms 79696 KB Output is correct
18 Correct 120 ms 76628 KB Output is correct
19 Correct 109 ms 75392 KB Output is correct
20 Correct 75 ms 76392 KB Output is correct
21 Correct 134 ms 79244 KB Output is correct
22 Correct 77 ms 75344 KB Output is correct
23 Correct 103 ms 77908 KB Output is correct
24 Correct 140 ms 79144 KB Output is correct
25 Correct 64 ms 75644 KB Output is correct
26 Correct 151 ms 80172 KB Output is correct
27 Correct 156 ms 84000 KB Output is correct
28 Correct 185 ms 85304 KB Output is correct
29 Correct 226 ms 85328 KB Output is correct
30 Correct 105 ms 58060 KB Output is correct
31 Correct 40 ms 48856 KB Output is correct
32 Correct 102 ms 61264 KB Output is correct
33 Correct 56 ms 49628 KB Output is correct
34 Correct 75 ms 54608 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 44 ms 50616 KB Output is correct
3 Correct 173 ms 64436 KB Output is correct
4 Correct 225 ms 69776 KB Output is correct
5 Correct 173 ms 65200 KB Output is correct
6 Correct 236 ms 69712 KB Output is correct
7 Correct 257 ms 69456 KB Output is correct
8 Correct 181 ms 64172 KB Output is correct
9 Correct 236 ms 69456 KB Output is correct
10 Correct 7 ms 47448 KB Output is correct
11 Correct 169 ms 56272 KB Output is correct
12 Correct 181 ms 56224 KB Output is correct
13 Correct 165 ms 56148 KB Output is correct
14 Correct 174 ms 56144 KB Output is correct
15 Correct 189 ms 62800 KB Output is correct
16 Correct 42 ms 50680 KB Output is correct
17 Correct 216 ms 68320 KB Output is correct
18 Correct 181 ms 63568 KB Output is correct
19 Correct 214 ms 67924 KB Output is correct
20 Correct 196 ms 62288 KB Output is correct
21 Correct 338 ms 90452 KB Output is correct
22 Correct 569 ms 104200 KB Output is correct
23 Correct 614 ms 104192 KB Output is correct
24 Correct 480 ms 100984 KB Output is correct
25 Correct 590 ms 107856 KB Output is correct
26 Correct 617 ms 107856 KB Output is correct
27 Correct 401 ms 93520 KB Output is correct
28 Correct 624 ms 107800 KB Output is correct
29 Correct 173 ms 84308 KB Output is correct
30 Correct 162 ms 83812 KB Output is correct
31 Correct 181 ms 85328 KB Output is correct
32 Correct 168 ms 85328 KB Output is correct
33 Correct 735 ms 101540 KB Output is correct
34 Correct 745 ms 101640 KB Output is correct
35 Correct 665 ms 97852 KB Output is correct
36 Correct 647 ms 97808 KB Output is correct
37 Correct 460 ms 99500 KB Output is correct
38 Correct 367 ms 89864 KB Output is correct
39 Correct 447 ms 98132 KB Output is correct
40 Correct 347 ms 88656 KB Output is correct
41 Correct 420 ms 90964 KB Output is correct
42 Correct 531 ms 102736 KB Output is correct
43 Correct 368 ms 90708 KB Output is correct
44 Correct 438 ms 95060 KB Output is correct
45 Correct 165 ms 82520 KB Output is correct
46 Correct 162 ms 80464 KB Output is correct
47 Correct 8 ms 47448 KB Output is correct
48 Correct 7 ms 47452 KB Output is correct
49 Correct 800 ms 80380 KB Output is correct
50 Correct 823 ms 80212 KB Output is correct
51 Correct 798 ms 80212 KB Output is correct
52 Correct 833 ms 80096 KB Output is correct
53 Correct 838 ms 80216 KB Output is correct
54 Correct 100 ms 65204 KB Output is correct
55 Correct 94 ms 76116 KB Output is correct
56 Correct 40 ms 62156 KB Output is correct
57 Correct 181 ms 84516 KB Output is correct
58 Correct 167 ms 82512 KB Output is correct
59 Correct 156 ms 80460 KB Output is correct
60 Correct 115 ms 77896 KB Output is correct
61 Correct 127 ms 77928 KB Output is correct
62 Correct 110 ms 79956 KB Output is correct
63 Correct 127 ms 79696 KB Output is correct
64 Correct 120 ms 76628 KB Output is correct
65 Correct 109 ms 75392 KB Output is correct
66 Correct 75 ms 76392 KB Output is correct
67 Correct 134 ms 79244 KB Output is correct
68 Correct 77 ms 75344 KB Output is correct
69 Correct 103 ms 77908 KB Output is correct
70 Correct 140 ms 79144 KB Output is correct
71 Correct 64 ms 75644 KB Output is correct
72 Correct 151 ms 80172 KB Output is correct
73 Correct 156 ms 84000 KB Output is correct
74 Correct 185 ms 85304 KB Output is correct
75 Correct 226 ms 85328 KB Output is correct
76 Correct 105 ms 58060 KB Output is correct
77 Correct 40 ms 48856 KB Output is correct
78 Correct 102 ms 61264 KB Output is correct
79 Correct 56 ms 49628 KB Output is correct
80 Correct 75 ms 54608 KB Output is correct
81 Correct 2174 ms 91732 KB Output is correct
82 Correct 2285 ms 94864 KB Output is correct
83 Correct 2143 ms 94804 KB Output is correct
84 Correct 2069 ms 94804 KB Output is correct
85 Correct 2127 ms 94688 KB Output is correct
86 Correct 236 ms 77888 KB Output is correct
87 Correct 224 ms 91220 KB Output is correct
88 Execution timed out 3040 ms 97796 KB Time limit exceeded
89 Halted 0 ms 0 KB -