oj.uz

Submission #874481

# Submission time Handle Problem Language Result Execution time Memory
874481 2023-11-17T06:53:28 Z Parsa_Fallahpour Jakarta Skyscrapers (APIO15_skyscraper) C++17
36 / 100
 176 ms 262144 KB 
/*
    Sag Template by ParsaF(RBS Master)
*/
 
// Heaven
 
#include <bits/stdc++.h>
 
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//#pragma GCC optimize("O3")

using namespace std;
 
 
#define TOF_IO                                   ios_base::sync_with_stdio(false);cin.tie(0) , cout.tie(0);
#define File_IO(x,y)                             freopen(x, "r", stdin); freopen(y, "w", stdout);
 
#define SEP                                      ' '
#define endl                                     '\n'
 
#define F                                        first
#define S                                        second
#define ALL(x)                                   (x).begin(), (x).end()
#define sz(x)                                    (x).size()
#define PB                                       push_back
 
#define toLower(x)                               transform(ALL(x), x.begin(), ::tolower)
#define toUpper(x)                               transform(ALL(x), x.begin(), ::toupper)
 
#define EDGE(arr, x, y)                          arr[x].PB(y), arr[y].PB(x)
#define WEDGE(arr, x, y, z)                      arr[x].PB({y, z}), arr[y].PB({x, z})
 
#define debug(x)                                 cerr << #x << ": " << x << endl
#define kill(x)                                  cout << x << endl, exit(0);

#define BIPC(x)                                  __builtin_popcount(x);
 
#define fD1(arr, ind, x)                         for(int i=0; i<ind; i++) arr[i] = x;
#define fD2(arr, ind1, ind2, x)                  for(int i=0; i<ind1; i++) for(int j=0; j<ind2; j++) arr[i][j] = x;
 
#define lc                                       (id << 1)
#define rc                                       ((id << 1) | 1)
#define isLeaf                                   r - l == 1

typedef long long       ll; 
typedef long double     lld;
typedef pair<ll, ll>    pll;
typedef pair<int, int>  pii;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
const ll N    = 3e4 + 4;
const ll MAXN = 3e4 + 5;
const ll MT   = 323 + 0;
const ll sq   = 320;
 
const ll M    = 1e9 + 7;
const ll IM   = 1e18 + 37;
 
const ll LOG  = 31;
 
const ll INF  = 1e18; 
const lld EPS = 0.00000001;
 
ll prime[] = {1000000009, 1000000007, 988244353, 1000696969, 696969569, 1223232323};
 
 
/***********************************************************       Dark side of Heaven        ************************************************************/
 
/***************************************************************************************************************************************************/
 
 
ll POW(ll a, ll b, ll md); 
ll LIS(vector<ll>& v);
ll MOD(ll a, ll b);
 
void printYES(bool flag);
void printYes(bool flag);
 
inline ll mod_add(ll a, ll b);
inline ll mod_neg(ll a, ll b);
inline ll mod_mlt(ll a, ll b);
 
/*
ll factI[N + 1], Numi[N + 1], fact[N + 1];
void InverseofNumber(ll p); void InverseofFactorial(ll p); void factorial(ll p); ll nPr(ll N, ll R, ll p); ll nCr(ll N, ll R); void comb();
*/

ll n, m;

ll b[N], p[N];

vector<pll> G1[N];

ll dist[N];



ll dij()
{   
    set<pll> st;
    for(int i=0; i<n; i++) dist[i] = INF;
    dist[b[0]] = 0;
    for(int i=0; i<n; i++) st.insert({dist[i], i});
    
    while(sz(st))
    {
        ll v, d;
        v = st.begin() -> S; d = st.begin() -> F;
        st.erase(st.begin());
        
        for(auto P: G1[v])
        {
            ll u, w;
            u = P.F; w = P.S;
            
            if(w+d >= dist[u]) continue;
            st.erase({dist[u], u});
            dist[u] = w+d;
            st.insert({dist[u], u});
        }
    }
    
    return (dist[b[1]]==INF? -1 : dist[b[1]]);
}

void solve()
{
    cin >> n >> m;
    
    for(int i=0; i<m; i++) cin >> b[i] >> p[i];
    
    for(int i=0; i<m; i++)
    {
        ll v = b[i], f=0;
        while(v+p[i] < n)
        {
            v += p[i]; f++;
            G1[b[i]].PB({v, f});
        }
        
        v = b[i]; f=0;
        while(v-p[i] >= 0)
        {
            v -= p[i]; f++;
            G1[b[i]].PB({v, f});
        }
    }
    
    cout << dij() << endl;
}

/*

*/

int main()
{
    TOF_IO;
    
    ll nTest=1;
    //cin >> nTest;
	
    while(nTest--) solve();
	
    return 0;
}

/********************************************************       The line that separates heaven and hell        *******************************************************/
 
// HELL
/*
void InverseofNumber(ll p = M){Numi[0] = Numi[1] = 1; for (ll i = 2; i <= N; i++){Numi[i] = Numi[p % i] * (p - p / i) % p;}}
void InverseofFactorial(ll p = M){factI[0] = factI[1] = 1;for (ll i = 2; i <= N; i++){factI[i] = (Numi[i] * factI[i - 1]) % p;}}
void factorial(ll p = M){fact[0] = 1;for (ll i = 1; i <= N; i++){fact[i] = (fact[i - 1] * i) % p;}}
ll nPr(ll N, ll R, ll p = M){if (N - R < 0 || R < 0) {return 0;}int ans = ((fact[N]) % p * factI[N - R]) % p;return ans;}
ll nCr(ll N, ll R){if (N - R < 0 || R < 0) {return 0;}int ans = ((fact[N] * factI[R]) % M * factI[N - R]) % M;return ans;}
void comb(){ll p = M;InverseofNumber(p);InverseofFactorial(p);factorial(p);}
*/
 
ll POW(ll a, ll b, ll md) {return (!b ? 1 : (b & 1 ? MOD(a * POW(MOD(a * a, md), b / 2, md), md) : MOD(POW(MOD(a * a, md), b / 2, md), md)));}
ll MOD(ll a, ll b){return (a%b + b) % b;}
 
ll LIS(vector<ll>& v){if (v.size() == 0) {return 0;} vector<ll> tail(v.size(), 0); ll length = 1; tail[0] = v[0]; for (int i = 1; i < v.size(); i++) {auto b = tail.begin(), e = tail.begin() + length; auto it = lower_bound(b, e, v[i]); if (it == tail.begin() + length){tail[length++] = v[i];}else{*it = v[i];}} return length;}
 
void YES(bool flag){cout << (flag? "YES\n" : "NO\n");}
void Yes(bool flag){cout << (flag? "Yes\n" : "No\n");}
 
inline ll mod_add(ll a, ll b){ ll res = a + b; return (res >= M? res - M : res); }
inline ll mod_neg(ll a, ll b){ ll res = (abs(a - b) < M? a - b : (a - b) % M); return (res < 0? res + M : res); }
inline ll mod_mlt(ll a, ll b){ return (a * b % M); }

Compilation message

skyscraper.cpp: In function 'll LIS(std::vector<long long int>&)':
skyscraper.cpp:185:133: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  185 | ll LIS(vector<ll>& v){if (v.size() == 0) {return 0;} vector<ll> tail(v.size(), 0); ll length = 1; tail[0] = v[0]; for (int i = 1; i < v.size(); i++) {auto b = tail.begin(), e = tail.begin() + length; auto it = lower_bound(b, e, v[i]); if (it == tail.begin() + length){tail[length++] = v[i];}else{*it = v[i];}} return length;}
      |                                                                                                                                   ~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1112 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 1144 KB Output is correct
11 Correct 1 ms 1372 KB Output is correct
12 Correct 4 ms 6356 KB Output is correct
13 Correct 4 ms 6360 KB Output is correct
14 Correct 1 ms 1116 KB Output is correct
15 Correct 1 ms 1116 KB Output is correct

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1368 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 1 ms 1372 KB Output is correct
12 Correct 5 ms 6612 KB Output is correct
13 Correct 5 ms 7128 KB Output is correct
14 Correct 1 ms 1112 KB Output is correct
15 Correct 1 ms 1116 KB Output is correct
16 Correct 1 ms 1116 KB Output is correct
17 Correct 2 ms 1624 KB Output is correct
18 Correct 1 ms 1368 KB Output is correct
19 Correct 1 ms 1368 KB Output is correct
20 Correct 62 ms 65364 KB Output is correct
21 Correct 1 ms 1116 KB Output is correct
22 Correct 1 ms 1372 KB Output is correct
23 Correct 2 ms 1372 KB Output is correct
24 Correct 2 ms 1628 KB Output is correct
25 Correct 2 ms 1372 KB Output is correct
26 Correct 55 ms 68760 KB Output is correct
27 Correct 52 ms 68260 KB Output is correct
28 Correct 2 ms 1628 KB Output is correct
29 Correct 4 ms 2644 KB Output is correct
30 Correct 2 ms 1628 KB Output is correct
31 Correct 3 ms 1884 KB Output is correct
32 Correct 2 ms 1628 KB Output is correct
33 Correct 6 ms 3780 KB Output is correct
34 Correct 6 ms 3544 KB Output is correct

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1112 KB Output is correct
4 Correct 1 ms 1112 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 1 ms 1372 KB Output is correct
12 Correct 4 ms 5324 KB Output is correct
13 Correct 4 ms 6872 KB Output is correct
14 Correct 1 ms 1116 KB Output is correct
15 Correct 1 ms 1116 KB Output is correct
16 Correct 1 ms 1116 KB Output is correct
17 Correct 2 ms 1628 KB Output is correct
18 Correct 1 ms 1372 KB Output is correct
19 Correct 1 ms 1372 KB Output is correct
20 Correct 66 ms 65504 KB Output is correct
21 Correct 1 ms 1116 KB Output is correct
22 Correct 1 ms 1372 KB Output is correct
23 Correct 2 ms 1372 KB Output is correct
24 Correct 2 ms 1624 KB Output is correct
25 Correct 2 ms 1372 KB Output is correct
26 Correct 55 ms 68996 KB Output is correct
27 Correct 52 ms 66980 KB Output is correct
28 Correct 2 ms 1624 KB Output is correct
29 Correct 4 ms 2396 KB Output is correct
30 Correct 2 ms 1628 KB Output is correct
31 Correct 3 ms 1884 KB Output is correct
32 Correct 2 ms 1628 KB Output is correct
33 Correct 6 ms 3676 KB Output is correct
34 Correct 6 ms 3544 KB Output is correct
35 Correct 7 ms 4700 KB Output is correct
36 Correct 2 ms 1628 KB Output is correct
37 Correct 10 ms 7772 KB Output is correct
38 Correct 15 ms 6592 KB Output is correct
39 Correct 10 ms 7176 KB Output is correct
40 Correct 10 ms 6744 KB Output is correct
41 Correct 10 ms 6488 KB Output is correct
42 Runtime error 176 ms 262144 KB Execution killed with signal 9
43 Halted 0 ms 0 KB -

Subtask #5
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1116 KB Output is correct
2 Correct 1 ms 1116 KB Output is correct
3 Correct 1 ms 1116 KB Output is correct
4 Correct 1 ms 1116 KB Output is correct
5 Correct 1 ms 1116 KB Output is correct
6 Correct 1 ms 1116 KB Output is correct
7 Correct 1 ms 1116 KB Output is correct
8 Correct 1 ms 1116 KB Output is correct
9 Correct 1 ms 1116 KB Output is correct
10 Correct 1 ms 1116 KB Output is correct
11 Correct 1 ms 1372 KB Output is correct
12 Correct 4 ms 5804 KB Output is correct
13 Correct 5 ms 6868 KB Output is correct
14 Correct 1 ms 1116 KB Output is correct
15 Correct 1 ms 1168 KB Output is correct
16 Correct 1 ms 1116 KB Output is correct
17 Correct 2 ms 1628 KB Output is correct
18 Correct 1 ms 1368 KB Output is correct
19 Correct 1 ms 1368 KB Output is correct
20 Correct 76 ms 65452 KB Output is correct
21 Correct 1 ms 1112 KB Output is correct
22 Correct 1 ms 1372 KB Output is correct
23 Correct 2 ms 1372 KB Output is correct
24 Correct 2 ms 1372 KB Output is correct
25 Correct 2 ms 1372 KB Output is correct
26 Correct 58 ms 67712 KB Output is correct
27 Correct 55 ms 68444 KB Output is correct
28 Correct 2 ms 1628 KB Output is correct
29 Correct 5 ms 2396 KB Output is correct
30 Correct 3 ms 1628 KB Output is correct
31 Correct 3 ms 1884 KB Output is correct
32 Correct 2 ms 1792 KB Output is correct
33 Correct 6 ms 3676 KB Output is correct
34 Correct 6 ms 3724 KB Output is correct
35 Correct 8 ms 4444 KB Output is correct
36 Correct 2 ms 1628 KB Output is correct
37 Correct 10 ms 7772 KB Output is correct
38 Correct 11 ms 6456 KB Output is correct
39 Correct 11 ms 6800 KB Output is correct
40 Correct 11 ms 6492 KB Output is correct
41 Correct 11 ms 6444 KB Output is correct
42 Runtime error 164 ms 262144 KB Execution killed with signal 9
43 Halted 0 ms 0 KB -