oj.uz

Submission #1034257

# Submission time Handle Problem Language Result Execution time Memory
1034257 2024-07-25T11:21:25 Z Antekb Escape Route 2 (JOI24_escape2) C++17
54 / 100
 3000 ms 52020 KB 
#include "bits/stdc++.h"	/** keep-include */
using namespace std;

#define rep(i, b, e) for(int i = (b); i <= (e); i++)
#define per(i, b, e) for(int i = (e); i >= (b); i--)
#define FOR(i, b, e) rep(i, b, (e) - 1)
#define SZ(x) int(x.size())
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define st first
#define nd second
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;

auto &operator<<(auto &o, pair<auto, auto> p) {
	return o << "(" << p.st << ", " << p.nd << ")"; }
auto operator<<(auto &o, auto x)->decltype(end(x), o) {
	o << "{"; int i=0; for(auto e: x) o << ", " + 2*!i++ << e;
	return o << "}"; }
#ifdef LOCAL
#define deb(x...) cerr << "[" #x "]: ", [](auto...$) { \
	((cerr << $ << "; "),...) << endl; }(x)
#else
#define deb(...)
#endif

const int K=19, N=3e5+5;

vector<pii> loty[N];
vector<int> id[N];
int nxt[K][N];
ll czas[K][N];

pair<int, ll> jump(int v, int t){
    ll res=0;
    for(int k=K-1; k>=0; k--){
        if(t>=(1<<k)){
            res+=czas[k][v];
            v=nxt[k][v];
            t-=(1<<k);
        }
    }
    return mp(v, res);
}

void solve() {
	int n, t;
    cin>>n>>t;
    vector<pair<pii, int> > co;
    co.pb(mp(mp(0, 0), 0));
    for(int i=1; i<n; i++){
        int k;
        cin>>k;
        vector<pair<int, int> > V(k);
        for(auto &j:V){
            cin>>j.st>>j.nd;
        }
        sort(all(V));
        vector<pii> V2;
        for(auto &j:V){
            while(V2.size() && V2.back().nd>=j.nd){
                V2.pop_back();
            }
            V2.pb(j);
        }
        k=V2.size();
        for(int j=0; j<k; j++){
            id[i].pb(co.size());
            co.pb(mp(V2[j], i));
        }
        loty[i]=V2;
    }

    for(int j=1; j<co.size(); j++){
        auto &[seg, i] = co[j];
        if(i!=n-1){
            auto it=lower_bound(all(loty[i+1]), mp(seg.nd, 0));
            if(it==loty[i+1].end()){
                it=loty[i+1].begin();
                nxt[0][j]=id[i+1][it-loty[i+1].begin()];
                czas[0][j]=it->nd-seg.nd+t;
                deb(czas[0][j], it->nd, seg.nd,t);
            }
            else{
                nxt[0][j]=id[i+1][it-loty[i+1].begin()];
                czas[0][j]=it->nd-seg.nd;
            }
        }
        deb(j, seg, i, co[nxt[0][j]], czas[0][j]);
    }
    for(int k=1; k<K; k++){
        for(int i=1; i<co.size(); i++){
            nxt[k][i]=nxt[k-1][nxt[k-1][i]];
            czas[k][i]=czas[k-1][i]+czas[k-1][nxt[k-1][i]];
        }
    }
    map<pair<int, int> , ll> old_ans;
    int q;
    cin>>q;
    while(q--){
        int l, r;
        cin>>l>>r;
        /*if(old_ans.find(mp(l, r))!=old_ans.end()){
            cout<<old_ans[mp(l, r)]<<"\n";
            continue;
        }*/
        ll ans=1e18;
        for(int i=0; i<loty[l].size(); i++){
            ll part=loty[l][i].nd-loty[l][i].st;
            int lot=id[l][i];
            deb(lot);
            /*for(int j=l+1; j<r; j++){
                part+=czas[0][lot];
                lot=nxt[0][lot];
            }*/
            part+=jump(lot, r-l-1).nd;
            //deb(part);
            ans=min(ans, part);
        }
        //old_ans[mp(l, r)]=ans;
        cout<<ans<<"\n";
    }
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int tt = 1;
	// cin >> tt;
	FOR(te, 0, tt) solve();
	return 0;
}

Compilation message

Main.cpp:17:18: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   17 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                  ^~~~
Main.cpp:17:32: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   17 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                                ^~~~
Main.cpp:17:38: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   17 | auto &operator<<(auto &o, pair<auto, auto> p) {
      |                                      ^~~~
Main.cpp:19:17: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
      |                 ^~~~
Main.cpp:19:26: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   19 | auto operator<<(auto &o, auto x)->decltype(end(x), o) {
      |                          ^~~~
Main.cpp: In function 'void solve()':
Main.cpp:76:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |     for(int j=1; j<co.size(); j++){
      |                  ~^~~~~~~~~~
Main.cpp:94:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for(int i=1; i<co.size(); i++){
      |                      ~^~~~~~~~~~
Main.cpp:110: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]
  110 |         for(int i=0; i<loty[l].size(); i++){
      |                      ~^~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14640 KB Output is correct
2 Correct 45 ms 17748 KB Output is correct
3 Correct 56 ms 18004 KB Output is correct
4 Correct 100 ms 19280 KB Output is correct
5 Correct 74 ms 18272 KB Output is correct
6 Correct 66 ms 19228 KB Output is correct
7 Correct 70 ms 19284 KB Output is correct
8 Correct 54 ms 18004 KB Output is correct
9 Correct 69 ms 19280 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14640 KB Output is correct
2 Correct 45 ms 17748 KB Output is correct
3 Correct 56 ms 18004 KB Output is correct
4 Correct 100 ms 19280 KB Output is correct
5 Correct 74 ms 18272 KB Output is correct
6 Correct 66 ms 19228 KB Output is correct
7 Correct 70 ms 19284 KB Output is correct
8 Correct 54 ms 18004 KB Output is correct
9 Correct 69 ms 19280 KB Output is correct
10 Correct 6 ms 14684 KB Output is correct
11 Correct 94 ms 18776 KB Output is correct
12 Correct 81 ms 18772 KB Output is correct
13 Correct 80 ms 19796 KB Output is correct
14 Correct 80 ms 19792 KB Output is correct
15 Correct 80 ms 20304 KB Output is correct
16 Correct 49 ms 18768 KB Output is correct
17 Correct 69 ms 21584 KB Output is correct
18 Correct 75 ms 21188 KB Output is correct
19 Correct 71 ms 21452 KB Output is correct
20 Correct 77 ms 21076 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14640 KB Output is correct
2 Correct 45 ms 17748 KB Output is correct
3 Correct 56 ms 18004 KB Output is correct
4 Correct 100 ms 19280 KB Output is correct
5 Correct 74 ms 18272 KB Output is correct
6 Correct 66 ms 19228 KB Output is correct
7 Correct 70 ms 19284 KB Output is correct
8 Correct 54 ms 18004 KB Output is correct
9 Correct 69 ms 19280 KB Output is correct
10 Correct 159 ms 43676 KB Output is correct
11 Correct 257 ms 52020 KB Output is correct
12 Correct 235 ms 51972 KB Output is correct
13 Correct 186 ms 50172 KB Output is correct
14 Correct 213 ms 51972 KB Output is correct
15 Correct 220 ms 51828 KB Output is correct
16 Correct 129 ms 43376 KB Output is correct
17 Correct 214 ms 51976 KB Output is correct
18 Correct 115 ms 44660 KB Output is correct
19 Correct 76 ms 43984 KB Output is correct
20 Correct 113 ms 44524 KB Output is correct
21 Correct 83 ms 44552 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14640 KB Output is correct
2 Correct 45 ms 17748 KB Output is correct
3 Correct 56 ms 18004 KB Output is correct
4 Correct 100 ms 19280 KB Output is correct
5 Correct 74 ms 18272 KB Output is correct
6 Correct 66 ms 19228 KB Output is correct
7 Correct 70 ms 19284 KB Output is correct
8 Correct 54 ms 18004 KB Output is correct
9 Correct 69 ms 19280 KB Output is correct
10 Correct 6 ms 14684 KB Output is correct
11 Correct 94 ms 18776 KB Output is correct
12 Correct 81 ms 18772 KB Output is correct
13 Correct 80 ms 19796 KB Output is correct
14 Correct 80 ms 19792 KB Output is correct
15 Correct 80 ms 20304 KB Output is correct
16 Correct 49 ms 18768 KB Output is correct
17 Correct 69 ms 21584 KB Output is correct
18 Correct 75 ms 21188 KB Output is correct
19 Correct 71 ms 21452 KB Output is correct
20 Correct 77 ms 21076 KB Output is correct
21 Correct 159 ms 43676 KB Output is correct
22 Correct 257 ms 52020 KB Output is correct
23 Correct 235 ms 51972 KB Output is correct
24 Correct 186 ms 50172 KB Output is correct
25 Correct 213 ms 51972 KB Output is correct
26 Correct 220 ms 51828 KB Output is correct
27 Correct 129 ms 43376 KB Output is correct
28 Correct 214 ms 51976 KB Output is correct
29 Correct 115 ms 44660 KB Output is correct
30 Correct 76 ms 43984 KB Output is correct
31 Correct 113 ms 44524 KB Output is correct
32 Correct 83 ms 44552 KB Output is correct
33 Correct 201 ms 49336 KB Output is correct
34 Correct 175 ms 49208 KB Output is correct
35 Correct 168 ms 46596 KB Output is correct
36 Correct 176 ms 46464 KB Output is correct
37 Correct 153 ms 47620 KB Output is correct
38 Correct 128 ms 43872 KB Output is correct
39 Correct 217 ms 51956 KB Output is correct
40 Correct 146 ms 40680 KB Output is correct
41 Correct 137 ms 41452 KB Output is correct
42 Correct 178 ms 49664 KB Output is correct
43 Correct 121 ms 41220 KB Output is correct
44 Correct 148 ms 43012 KB Output is correct
45 Correct 73 ms 43780 KB Output is correct
46 Correct 81 ms 41992 KB Output is correct

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14684 KB Output is correct
2 Correct 6 ms 14684 KB Output is correct
3 Correct 410 ms 40052 KB Output is correct
4 Correct 425 ms 40196 KB Output is correct
5 Correct 423 ms 40180 KB Output is correct
6 Correct 477 ms 40072 KB Output is correct
7 Correct 390 ms 40120 KB Output is correct
8 Correct 226 ms 29452 KB Output is correct
9 Correct 397 ms 41216 KB Output is correct
10 Execution timed out 3050 ms 27532 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14640 KB Output is correct
2 Correct 45 ms 17748 KB Output is correct
3 Correct 56 ms 18004 KB Output is correct
4 Correct 100 ms 19280 KB Output is correct
5 Correct 74 ms 18272 KB Output is correct
6 Correct 66 ms 19228 KB Output is correct
7 Correct 70 ms 19284 KB Output is correct
8 Correct 54 ms 18004 KB Output is correct
9 Correct 69 ms 19280 KB Output is correct
10 Correct 6 ms 14684 KB Output is correct
11 Correct 94 ms 18776 KB Output is correct
12 Correct 81 ms 18772 KB Output is correct
13 Correct 80 ms 19796 KB Output is correct
14 Correct 80 ms 19792 KB Output is correct
15 Correct 80 ms 20304 KB Output is correct
16 Correct 49 ms 18768 KB Output is correct
17 Correct 69 ms 21584 KB Output is correct
18 Correct 75 ms 21188 KB Output is correct
19 Correct 71 ms 21452 KB Output is correct
20 Correct 77 ms 21076 KB Output is correct
21 Correct 159 ms 43676 KB Output is correct
22 Correct 257 ms 52020 KB Output is correct
23 Correct 235 ms 51972 KB Output is correct
24 Correct 186 ms 50172 KB Output is correct
25 Correct 213 ms 51972 KB Output is correct
26 Correct 220 ms 51828 KB Output is correct
27 Correct 129 ms 43376 KB Output is correct
28 Correct 214 ms 51976 KB Output is correct
29 Correct 115 ms 44660 KB Output is correct
30 Correct 76 ms 43984 KB Output is correct
31 Correct 113 ms 44524 KB Output is correct
32 Correct 83 ms 44552 KB Output is correct
33 Correct 201 ms 49336 KB Output is correct
34 Correct 175 ms 49208 KB Output is correct
35 Correct 168 ms 46596 KB Output is correct
36 Correct 176 ms 46464 KB Output is correct
37 Correct 153 ms 47620 KB Output is correct
38 Correct 128 ms 43872 KB Output is correct
39 Correct 217 ms 51956 KB Output is correct
40 Correct 146 ms 40680 KB Output is correct
41 Correct 137 ms 41452 KB Output is correct
42 Correct 178 ms 49664 KB Output is correct
43 Correct 121 ms 41220 KB Output is correct
44 Correct 148 ms 43012 KB Output is correct
45 Correct 73 ms 43780 KB Output is correct
46 Correct 81 ms 41992 KB Output is correct
47 Correct 6 ms 14684 KB Output is correct
48 Correct 6 ms 14684 KB Output is correct
49 Correct 410 ms 40052 KB Output is correct
50 Correct 425 ms 40196 KB Output is correct
51 Correct 423 ms 40180 KB Output is correct
52 Correct 477 ms 40072 KB Output is correct
53 Correct 390 ms 40120 KB Output is correct
54 Correct 226 ms 29452 KB Output is correct
55 Correct 397 ms 41216 KB Output is correct
56 Execution timed out 3050 ms 27532 KB Time limit exceeded
57 Halted 0 ms 0 KB -