oj.uz

Submission #1034240

# Submission time Handle Problem Language Result Execution time Memory
1034240 2024-07-25T11:10:01 Z Antekb Escape Route 2 (JOI24_escape2) C++17
6 / 100
 3000 ms 39036 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];

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){
                V.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]);
    }
    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];
            }
            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:64: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]
   64 |     for(int j=1; j<co.size(); j++){
      |                  ~^~~~~~~~~~
Main.cpp:92: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]
   92 |         for(int i=0; i<loty[l].size(); i++){
      |                      ~^~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14424 KB Output is correct
2 Correct 52 ms 18548 KB Output is correct
3 Correct 321 ms 33024 KB Output is correct
4 Correct 496 ms 39036 KB Output is correct
5 Correct 418 ms 33656 KB Output is correct
6 Correct 560 ms 38736 KB Output is correct
7 Correct 541 ms 38736 KB Output is correct
8 Correct 358 ms 32684 KB Output is correct
9 Correct 582 ms 38740 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14424 KB Output is correct
2 Correct 52 ms 18548 KB Output is correct
3 Correct 321 ms 33024 KB Output is correct
4 Correct 496 ms 39036 KB Output is correct
5 Correct 418 ms 33656 KB Output is correct
6 Correct 560 ms 38736 KB Output is correct
7 Correct 541 ms 38736 KB Output is correct
8 Correct 358 ms 32684 KB Output is correct
9 Correct 582 ms 38740 KB Output is correct
10 Correct 7 ms 14424 KB Output is correct
11 Correct 287 ms 25424 KB Output is correct
12 Correct 260 ms 25324 KB Output is correct
13 Correct 257 ms 25300 KB Output is correct
14 Correct 245 ms 25256 KB Output is correct
15 Correct 405 ms 31828 KB Output is correct
16 Execution timed out 3056 ms 14424 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14424 KB Output is correct
2 Correct 52 ms 18548 KB Output is correct
3 Correct 321 ms 33024 KB Output is correct
4 Correct 496 ms 39036 KB Output is correct
5 Correct 418 ms 33656 KB Output is correct
6 Correct 560 ms 38736 KB Output is correct
7 Correct 541 ms 38736 KB Output is correct
8 Correct 358 ms 32684 KB Output is correct
9 Correct 582 ms 38740 KB Output is correct
10 Execution timed out 3031 ms 25988 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14424 KB Output is correct
2 Correct 52 ms 18548 KB Output is correct
3 Correct 321 ms 33024 KB Output is correct
4 Correct 496 ms 39036 KB Output is correct
5 Correct 418 ms 33656 KB Output is correct
6 Correct 560 ms 38736 KB Output is correct
7 Correct 541 ms 38736 KB Output is correct
8 Correct 358 ms 32684 KB Output is correct
9 Correct 582 ms 38740 KB Output is correct
10 Correct 7 ms 14424 KB Output is correct
11 Correct 287 ms 25424 KB Output is correct
12 Correct 260 ms 25324 KB Output is correct
13 Correct 257 ms 25300 KB Output is correct
14 Correct 245 ms 25256 KB Output is correct
15 Correct 405 ms 31828 KB Output is correct
16 Execution timed out 3056 ms 14424 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14428 KB Output is correct
2 Correct 7 ms 14520 KB Output is correct
3 Correct 2795 ms 23988 KB Output is correct
4 Correct 2903 ms 23956 KB Output is correct
5 Execution timed out 3068 ms 22828 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 14424 KB Output is correct
2 Correct 52 ms 18548 KB Output is correct
3 Correct 321 ms 33024 KB Output is correct
4 Correct 496 ms 39036 KB Output is correct
5 Correct 418 ms 33656 KB Output is correct
6 Correct 560 ms 38736 KB Output is correct
7 Correct 541 ms 38736 KB Output is correct
8 Correct 358 ms 32684 KB Output is correct
9 Correct 582 ms 38740 KB Output is correct
10 Correct 7 ms 14424 KB Output is correct
11 Correct 287 ms 25424 KB Output is correct
12 Correct 260 ms 25324 KB Output is correct
13 Correct 257 ms 25300 KB Output is correct
14 Correct 245 ms 25256 KB Output is correct
15 Correct 405 ms 31828 KB Output is correct
16 Execution timed out 3056 ms 14424 KB Time limit exceeded
17 Halted 0 ms 0 KB -