oj.uz

Submission #845851

# Submission time Handle Problem Language Result Execution time Memory
845851 2023-09-06T16:31:36 Z mircea_007 Overtaking (IOI23_overtaking) C++17
100 / 100
 1780 ms 471536 KB 
#include "overtaking.h"

#pragma GCC optimize( "O3,Ofast,unroll-loops" ) // de ce nu

#include <stdio.h>
#include <stdlib.h>

#include <algorithm>
#include <vector>
#include <map>

using ll = long long;
#define magic_sauce inline __attribute__((always_inline))

magic_sauce ll max( ll a, ll b ){ return a > b ? a : b; }

const int MAXN = 1000;
const int MAXM = 1000;
const ll INF = 1e18;

const ll NIL = -1;

struct Range {
  ll begin;
  ll val;

  magic_sauce Range( ll a, ll b ) : begin( a ), val( b ) {}
};

struct Function {
  std::vector<Range> ranges;
  ll add;

  magic_sauce ll operator ()( ll x ){
    int st = 0, dr = (int)ranges.size(), mij;

    while( dr - st > 1 ){
      if( ranges[mij = (st + dr) >> 1].begin > x )
        dr = mij;
      else
        st = mij;
    }

    if( ranges[st].val >= 0 )
      return ranges[st].val;

    return x + add;
  }

  // compunerea de functii
  void operator *= ( Function &other ){
    std::vector<Range> new_ranges;
    int i, j, k, n = (int)ranges.size(), m = (int)other.ranges.size();;
    int st, dr, mij;

    ll start, end;

    for( i = 0 ; i < n ; i++ ){
      start = ranges[i].begin;

      if( i + 1 < n )
        end = ranges[i + 1].begin;
      else
        end = INF;
      
      if( ranges[i].val >= 0 )
        new_ranges.emplace_back( start, other( ranges[i].val ) );
      else{
        // functie liniara

        // [start, end) -> [start + add, end + add)

        // adaugam tot ce este in range-ul [it_start, it_end) doar ca + add
        // tratam separat intervalul ce contine pe start
        st = 0;
        dr = m;
        while( dr - st > 1 )
          if( other.ranges[mij = (st + dr) >> 1].begin > start + add )
            dr = mij;
          else
            st = mij;

        j = st;

        // cazul separat
        new_ranges.emplace_back( start, other.ranges[j].val );

        st = -1;
        dr = m;
        while( dr - st > 1 ){
          if( other.ranges[mij = (st + dr) >> 1].begin < end + add )
            st = mij;
          else
            dr = mij;
        }
        
        j++;
        k = dr;
        while( j < k ){
          new_ranges.emplace_back( other.ranges[j].begin - add, other.ranges[j].val );
          j++;
        }
      }
    }

    // prune next ranges
    ranges = new_ranges;

    add += other.add;
  }
};

struct Solver {
  int l, n, x, m;

  std::vector<ll> t0; // timpul de pornire al autobuzelor
  std::vector<int> speed; // s/m

  std::vector<int> stat; // sorting station

  ll dp[MAXM][MAXN];
  std::map<ll, ll> slowest[MAXM];

  Function f[MAXM];

  void calc_dp(){
    int i, j;

    // facem ce spune enuntul

    for( i = 0 ; i < n ; i++ )
      dp[0][i] = t0[i];

    for( i = 1 ; i < m ; i++ ){
      // for( j = 0 ; j < n ; j++ )
      //   e[j] = dp[i - 1][j] + ((ll)speed[j]) * (stat[i] - stat[i - 1]);

      for( j = 0 ; j < n ; j++ )
        slowest[i][dp[i - 1][j]] = max( slowest[i][dp[i - 1][j]], dp[i - 1][j] + ((ll)speed[j]) * (stat[i] - stat[i - 1]) );

      ll prev = -1;

      for( auto p : slowest[i] ){
        prev = max( slowest[i][p.first], prev );

        slowest[i][p.first] = prev;
      }

      for( j = 0 ; j < n ; j++ ){
        dp[i][j] = dp[i - 1][j] + ((ll)speed[j]) * (stat[i] - stat[i - 1]);

        auto it = slowest[i].lower_bound( dp[i - 1][j] );
        if( it != slowest[i].begin() ){
          it--;

          dp[i][j] = max( dp[i][j], it->second );
        }
      }
    }
  }

  void calc_map( int i ){
    ll add = ((ll)x) * (stat[i] - stat[i - 1]);

    f[i].add = add;

    // daca am ajuns primii suntem liberi sa facem ce vrem
    f[i].ranges.emplace_back( 0, NIL );

    auto it = slowest[i].begin();
    auto next = it;

    while( it != slowest[i].end() ){
      next++;

      ll start = it->first;
      ll cand = it->second;

      ll end = INF;

      if( next != slowest[i].end() )
        end = next->first;

      start++;
      end++;

      // [start, cand - add) -> t' = cand
      // [cand - add, end) -> t' = t + add

      ll mij = cand - add;

      if( start < mij )
        f[i].ranges.emplace_back( start, cand );
      else
        mij = start;

      if( mij < end )
        f[i].ranges.emplace_back( mij, NIL );

      it = next;
    }
  }

  void compress_maps(){
    for( int p2 = 1 ; p2 < 1024 ; p2 <<= 1 )
      for( int i = 1 ; i + p2 < m ; i += (p2 << 1) )
        f[i] *= f[i + p2];
  }

  void pre(){
    // using the dp from the statement we precalculate the positions of the other bussesx
    calc_dp();

    // the old query function is a repeated aplication of M functions (in the math sense)
    // therefore we can hold these functions as a reunion of several intervals
    // each being either a constant function or a linear function with slope 1
    for( int i = 1 ; i < m ; i++ )
      calc_map( i );

    compress_maps();
  }

  ll query( ll t ){
    return f[1]( t );
  }

} sol;

void init( int L, int N, std::vector<ll> T, std::vector<int> W, int X, int M, std::vector<int> S ){
  // first of all, anything faster than x doesn't matter
  // therefore we can assume that the special bus in the
  // fastest one and the others are slowing it down

  // each buss has to worry only about the ones slower than itsself
  // for this exact reason, all the busse's paths (exept N) are predetermined

  // some precalculation

  sol.l = L;
  sol.n = N;
  sol.x = X;
  sol.m = M;

  sol.t0 = T;
  sol.speed = W;
  sol.stat = S;

  sol.pre();
}

ll arrival_time( ll Y ){
  return sol.query( Y );
  
  return 0;
}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 860 KB Output is correct
5 Correct 1 ms 860 KB Output is correct
6 Correct 1 ms 5212 KB Output is correct
7 Correct 2 ms 7516 KB Output is correct
8 Correct 2 ms 8028 KB Output is correct
9 Correct 3 ms 8028 KB Output is correct
10 Correct 2 ms 8028 KB Output is correct
11 Correct 2 ms 7772 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 0 ms 860 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 6 ms 3712 KB Output is correct
10 Correct 6 ms 3712 KB Output is correct
11 Correct 7 ms 4176 KB Output is correct
12 Correct 7 ms 3712 KB Output is correct
13 Correct 6 ms 3692 KB Output is correct
14 Correct 6 ms 3712 KB Output is correct
15 Correct 4 ms 2908 KB Output is correct
16 Correct 4 ms 2648 KB Output is correct
17 Correct 4 ms 2908 KB Output is correct
18 Correct 5 ms 2908 KB Output is correct
19 Correct 4 ms 2908 KB Output is correct
20 Correct 4 ms 2652 KB Output is correct
21 Correct 2 ms 1624 KB Output is correct
22 Correct 2 ms 1116 KB Output is correct
23 Correct 3 ms 1628 KB Output is correct
24 Correct 3 ms 1880 KB Output is correct
25 Correct 4 ms 1880 KB Output is correct
26 Correct 3 ms 2136 KB Output is correct
27 Correct 4 ms 1880 KB Output is correct
28 Correct 3 ms 1372 KB Output is correct
29 Correct 2 ms 1372 KB Output is correct
30 Correct 2 ms 1372 KB Output is correct
31 Correct 3 ms 1372 KB Output is correct
32 Correct 4 ms 2912 KB Output is correct
33 Correct 6 ms 4164 KB Output is correct
34 Correct 7 ms 4116 KB Output is correct
35 Correct 7 ms 4116 KB Output is correct
36 Correct 7 ms 4116 KB Output is correct
37 Correct 7 ms 4116 KB Output is correct
38 Correct 3 ms 1836 KB Output is correct
39 Correct 4 ms 1884 KB Output is correct
40 Correct 5 ms 3084 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 0 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 5212 KB Output is correct
8 Correct 2 ms 7516 KB Output is correct
9 Correct 2 ms 8028 KB Output is correct
10 Correct 3 ms 8028 KB Output is correct
11 Correct 2 ms 8028 KB Output is correct
12 Correct 2 ms 7772 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 6 ms 3712 KB Output is correct
17 Correct 6 ms 3712 KB Output is correct
18 Correct 7 ms 4176 KB Output is correct
19 Correct 7 ms 3712 KB Output is correct
20 Correct 6 ms 3692 KB Output is correct
21 Correct 6 ms 3712 KB Output is correct
22 Correct 4 ms 2908 KB Output is correct
23 Correct 4 ms 2648 KB Output is correct
24 Correct 4 ms 2908 KB Output is correct
25 Correct 5 ms 2908 KB Output is correct
26 Correct 4 ms 2908 KB Output is correct
27 Correct 4 ms 2652 KB Output is correct
28 Correct 2 ms 1624 KB Output is correct
29 Correct 2 ms 1116 KB Output is correct
30 Correct 3 ms 1628 KB Output is correct
31 Correct 3 ms 1880 KB Output is correct
32 Correct 4 ms 1880 KB Output is correct
33 Correct 3 ms 2136 KB Output is correct
34 Correct 4 ms 1880 KB Output is correct
35 Correct 3 ms 1372 KB Output is correct
36 Correct 2 ms 1372 KB Output is correct
37 Correct 2 ms 1372 KB Output is correct
38 Correct 3 ms 1372 KB Output is correct
39 Correct 4 ms 2912 KB Output is correct
40 Correct 6 ms 4164 KB Output is correct
41 Correct 7 ms 4116 KB Output is correct
42 Correct 7 ms 4116 KB Output is correct
43 Correct 7 ms 4116 KB Output is correct
44 Correct 7 ms 4116 KB Output is correct
45 Correct 3 ms 1836 KB Output is correct
46 Correct 4 ms 1884 KB Output is correct
47 Correct 5 ms 3084 KB Output is correct
48 Correct 726 ms 189728 KB Output is correct
49 Correct 749 ms 210928 KB Output is correct
50 Correct 809 ms 232864 KB Output is correct
51 Correct 740 ms 210168 KB Output is correct
52 Correct 748 ms 214140 KB Output is correct
53 Correct 745 ms 211056 KB Output is correct
54 Correct 745 ms 210172 KB Output is correct
55 Correct 350 ms 68584 KB Output is correct
56 Correct 601 ms 150784 KB Output is correct
57 Correct 601 ms 150452 KB Output is correct
58 Correct 607 ms 155272 KB Output is correct
59 Correct 627 ms 161276 KB Output is correct
60 Correct 606 ms 150808 KB Output is correct
61 Correct 611 ms 155496 KB Output is correct
62 Correct 3 ms 8280 KB Output is correct
63 Correct 2 ms 604 KB Output is correct
64 Correct 278 ms 77796 KB Output is correct
65 Correct 299 ms 68984 KB Output is correct
66 Correct 566 ms 133624 KB Output is correct
67 Correct 622 ms 143260 KB Output is correct
68 Correct 603 ms 143084 KB Output is correct
69 Correct 1022 ms 260468 KB Output is correct
70 Correct 1339 ms 415044 KB Output is correct
71 Correct 1392 ms 463936 KB Output is correct
72 Correct 1388 ms 437284 KB Output is correct
73 Correct 1397 ms 464556 KB Output is correct
74 Correct 1438 ms 463876 KB Output is correct
75 Correct 560 ms 107352 KB Output is correct
76 Correct 560 ms 107212 KB Output is correct
77 Correct 570 ms 112284 KB Output is correct
78 Correct 1177 ms 298180 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Correct 0 ms 860 KB Output is correct
4 Correct 1 ms 860 KB Output is correct
5 Correct 0 ms 860 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 5212 KB Output is correct
8 Correct 2 ms 7516 KB Output is correct
9 Correct 2 ms 8028 KB Output is correct
10 Correct 3 ms 8028 KB Output is correct
11 Correct 2 ms 8028 KB Output is correct
12 Correct 2 ms 7772 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 604 KB Output is correct
19 Correct 2 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 604 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 1 ms 604 KB Output is correct
24 Correct 1 ms 604 KB Output is correct
25 Correct 1 ms 604 KB Output is correct
26 Correct 1 ms 604 KB Output is correct
27 Correct 6 ms 3712 KB Output is correct
28 Correct 6 ms 3712 KB Output is correct
29 Correct 7 ms 4176 KB Output is correct
30 Correct 7 ms 3712 KB Output is correct
31 Correct 6 ms 3692 KB Output is correct
32 Correct 6 ms 3712 KB Output is correct
33 Correct 4 ms 2908 KB Output is correct
34 Correct 4 ms 2648 KB Output is correct
35 Correct 4 ms 2908 KB Output is correct
36 Correct 5 ms 2908 KB Output is correct
37 Correct 4 ms 2908 KB Output is correct
38 Correct 4 ms 2652 KB Output is correct
39 Correct 2 ms 1624 KB Output is correct
40 Correct 2 ms 1116 KB Output is correct
41 Correct 3 ms 1628 KB Output is correct
42 Correct 3 ms 1880 KB Output is correct
43 Correct 4 ms 1880 KB Output is correct
44 Correct 3 ms 2136 KB Output is correct
45 Correct 4 ms 1880 KB Output is correct
46 Correct 3 ms 1372 KB Output is correct
47 Correct 2 ms 1372 KB Output is correct
48 Correct 2 ms 1372 KB Output is correct
49 Correct 3 ms 1372 KB Output is correct
50 Correct 4 ms 2912 KB Output is correct
51 Correct 6 ms 4164 KB Output is correct
52 Correct 7 ms 4116 KB Output is correct
53 Correct 7 ms 4116 KB Output is correct
54 Correct 7 ms 4116 KB Output is correct
55 Correct 7 ms 4116 KB Output is correct
56 Correct 3 ms 1836 KB Output is correct
57 Correct 4 ms 1884 KB Output is correct
58 Correct 5 ms 3084 KB Output is correct
59 Correct 726 ms 189728 KB Output is correct
60 Correct 749 ms 210928 KB Output is correct
61 Correct 809 ms 232864 KB Output is correct
62 Correct 740 ms 210168 KB Output is correct
63 Correct 748 ms 214140 KB Output is correct
64 Correct 745 ms 211056 KB Output is correct
65 Correct 745 ms 210172 KB Output is correct
66 Correct 350 ms 68584 KB Output is correct
67 Correct 601 ms 150784 KB Output is correct
68 Correct 601 ms 150452 KB Output is correct
69 Correct 607 ms 155272 KB Output is correct
70 Correct 627 ms 161276 KB Output is correct
71 Correct 606 ms 150808 KB Output is correct
72 Correct 611 ms 155496 KB Output is correct
73 Correct 3 ms 8280 KB Output is correct
74 Correct 2 ms 604 KB Output is correct
75 Correct 278 ms 77796 KB Output is correct
76 Correct 299 ms 68984 KB Output is correct
77 Correct 566 ms 133624 KB Output is correct
78 Correct 622 ms 143260 KB Output is correct
79 Correct 603 ms 143084 KB Output is correct
80 Correct 1022 ms 260468 KB Output is correct
81 Correct 1339 ms 415044 KB Output is correct
82 Correct 1392 ms 463936 KB Output is correct
83 Correct 1388 ms 437284 KB Output is correct
84 Correct 1397 ms 464556 KB Output is correct
85 Correct 1438 ms 463876 KB Output is correct
86 Correct 560 ms 107352 KB Output is correct
87 Correct 560 ms 107212 KB Output is correct
88 Correct 570 ms 112284 KB Output is correct
89 Correct 1177 ms 298180 KB Output is correct
90 Correct 764 ms 189808 KB Output is correct
91 Correct 971 ms 237152 KB Output is correct
92 Correct 1048 ms 257956 KB Output is correct
93 Correct 986 ms 233876 KB Output is correct
94 Correct 959 ms 236088 KB Output is correct
95 Correct 1045 ms 237188 KB Output is correct
96 Correct 959 ms 234076 KB Output is correct
97 Correct 385 ms 71044 KB Output is correct
98 Correct 825 ms 175564 KB Output is correct
99 Correct 786 ms 176084 KB Output is correct
100 Correct 799 ms 180552 KB Output is correct
101 Correct 821 ms 187304 KB Output is correct
102 Correct 799 ms 175792 KB Output is correct
103 Correct 798 ms 180540 KB Output is correct
104 Correct 457 ms 95116 KB Output is correct
105 Correct 490 ms 93264 KB Output is correct
106 Correct 802 ms 164228 KB Output is correct
107 Correct 750 ms 151632 KB Output is correct
108 Correct 796 ms 163976 KB Output is correct
109 Correct 765 ms 151396 KB Output is correct
110 Correct 798 ms 164564 KB Output is correct
111 Correct 1286 ms 268072 KB Output is correct
112 Correct 1606 ms 429824 KB Output is correct
113 Correct 1780 ms 471324 KB Output is correct
114 Correct 1656 ms 417528 KB Output is correct
115 Correct 1772 ms 471536 KB Output is correct
116 Correct 1696 ms 471396 KB Output is correct
117 Correct 722 ms 129888 KB Output is correct
118 Correct 740 ms 135320 KB Output is correct
119 Correct 720 ms 134036 KB Output is correct
120 Correct 752 ms 139932 KB Output is correct
121 Correct 731 ms 136120 KB Output is correct
122 Correct 1424 ms 313252 KB Output is correct
123 Correct 1724 ms 417232 KB Output is correct
124 Correct 1613 ms 397416 KB Output is correct
125 Correct 1617 ms 407024 KB Output is correct