oj.uz

Submission #838996

# Submission time Handle Problem Language Result Execution time Memory
838996 2023-08-28T13:05:50 Z Joshua_Andersson Railway Trip 2 (JOI22_ho_t4) C++14
100 / 100
 1498 ms 128680 KB 
#undef _GLIBCXX_DEBUG                // disable run-time bound checking, etc
#pragma GCC optimize("Ofast,inline") // Ofast = O3,fast-math,allow-store-data-races,no-protect-parens
#pragma GCC optimize ("unroll-loops")

#pragma GCC target("bmi,bmi2,lzcnt,popcnt")                      // bit manipulation
#pragma GCC target("movbe")                                      // byte swap
#pragma GCC target("aes,pclmul,rdrnd")                           // encryption
#pragma GCC target("avx,avx2,f16c,fma,sse3,ssse3,sse4.1,sse4.2") // SIMD

#include <vector>
#include <string>
#include <random>
#include <chrono>
#include <iostream>
#include <sstream>
using namespace std;

#define enablell 1

typedef long long ll;
typedef unsigned long long ull;
#if enablell
#define int ll
#define inf int(1e18)
#else
const int inf = int(2e9);
#endif
typedef vector<ull> vull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vvvi> vvvvi;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
typedef pair<int, int> p2;
typedef vector<p2> vp2;
typedef vector<vp2> vvp2;
typedef vector<vvp2> vvvp2;
typedef tuple<int, int, int> p3;
typedef vector<p3> vp3;
typedef vector<vp3> vvp3;
typedef vector<vvp3> vvvp3;
typedef tuple<int, int, int, int> p4;
typedef vector<p4> vp4;

#define _LOCAL _MSC_VER > 0
#if _LOCAL

#define assert(x) debassert(x)
#define popcount(x) __popcnt(x)
uint32_t clz(uint32_t x) { return _lzcnt_u32(x); }
uint32_t ctz(uint32_t x) { return _tzcnt_u32(x); }
#define bswap64(x) _byteswap_uint64(x)
#else

#define popcount(x) __builtin_popcountll(x)
uint32_t clz(uint32_t x) { return __builtin_clz(x); }
uint32_t ctz(uint32_t x) { return __builtin_ctzll(x); }
#define bswap64(x) __builtin_bswap64(x)

#if 0
namespace pbds
{
    using namespace __gnu_pbds;

    template<typename T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
    template<typename T, typename U> using indexed_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

    struct chash { // large odd number for C
        const uint64_t C = ll(4e18 * acos(0)) | 71;
        ll operator()(ll x) const { return __builtin_bswap64(x * C); }
    };
    template<typename T, typename U> using fast_map = __gnu_pbds::gp_hash_table<T, U, chash>;
    template<typename T> using fast_set = __gnu_pbds::gp_hash_table<T, null_type, chash>;
    template<typename T, typename H> using fast_set_h = __gnu_pbds::gp_hash_table<T, null_type, H>;
}
using namespace pbds;
#endif
#endif

inline void fast() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }
#define FAST_INPUT 0
#if FAST_INPUT && !_LOCAL
#define gc() getchar_unlocked()
inline void read(int& v) { v = 0; int sign = 1; char c = gc(); if (c == '-') { sign = -1; } else { v += c - '0'; } while ((c = gc()) && c != ' ' && c != '\n') { if (c == EOF) { v = -1; return; } v *= 10; v += c - '0'; } v *= sign; }
inline void read(int& u, int& v) { read(u); read(v); }
inline void read(int& u, int& v, int& k) { read(u); read(v); read(k); }
//inline void read(int& v) { char c; while ((c = getchar()) != EOF && c != ' ' && c != '\n') { v *= 10; v += c - '0'; } }
inline void read(string& s) { char c; while ((c = gc()) != EOF && c != '\n' && c != ' ') { s.push_back(c); } }
inline void readline(string& s) { char c; while ((c = gc()) != EOF && c != '\n') { s.push_back(c); } }
#else
template <typename T> inline void read(T& a) { cin >> a; }
template <typename T> inline void read(T& a, T& b) { cin >> a >> b; }
template <typename T> inline void read(T& a, T& b, T& c) { cin >> a >> b >> c; }
#endif
#define quit cout << endl; _Exit(0);
#define dread(type, a) type a; read(a)
#define dread2(type, a, b) dread(type, a); dread(type, b)
#define dread3(type, a, b, c) dread2(type, a, b); dread(type, c)
#define dread4(type, a, b, c, d) dread3(type, a, b, c); dread(type, d)
#define dread5(type, a, b, c, d, e) dread4(type, a, b, c, d); dread(type, e)
#define readvector(type, name, size) vector<type> name(size); rep(i,size) {dread(type,temp); name[i]=temp;}
#ifdef _DEBUG
#define noop cout << "";
#define deb __debugbreak();
#define debassert(expr) if(!(expr)) deb;
#define debif(expr) if(expr) deb;
void print(const string& s) { cout << s << "\n"; }
#else
#define noop ;
#define deb ;
#define debif(expr) ;
#define debassert(expr) ;
void print(const string& s) {  }
#endif

#define rep(i, high) for (int i = 0; i < high; i++)
#define repp(i, low, high) for (int i = low; i < high; i++)
#define repe(i, container) for (auto& i : container)
#define per(i, high) for (int i = high-1; i >= 0; i--)

#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define setcontains(set, x) (set.find(x) != set.end())
#define sz(container) ((int)container.size())
#define mp(a,b) (make_pair(a,b))

#define ceildiv(x,y) ((x + y - 1) / y)

template <typename T, typename U> inline void operator+=(pair<T, U>& l, const pair<T, U>& r) { l = { l.first + r.first,l.second + r.second }; }
template <typename T, typename U> inline pair<T, U> operator+(const pair<T, U> l, const pair<T, U> r) { return { l.first + r.first, l.second + r.second }; }
template <typename T, typename U> inline pair<T, U> operator-(const pair<T, U> l, const pair<T, U> r) { return { l.first - r.first, l.second - r.second }; }
template <typename T, typename U> inline pair<T, U> operator*(const pair<T, U> l, const int m) { return { l.first * m, l.second * m }; }
template <typename Out> inline void split(const string& s, char delim, Out result) { istringstream iss(s); string item; while (getline(iss, item, delim)) { *result++ = item; } }
inline vector<string> split(const string& s, char delim) { vector<string> elems; split(s, delim, back_inserter(elems)); return elems; }
vector<string> split(string s, string d) { size_t k = 0, n, e = d.length(); string t; vector<string> r; while ((n = s.find(d, k)) != string::npos) { t = s.substr(k, n - k); k = n + e; r.push_back(t); } r.push_back(s.substr(k)); return r; }
ll binpow(ll a, ll b) { ll res = 1; while (b > 0) { if (b & 1) res = res * a; a = a * a; b >>= 1; } return res; }
ll binpow(ll a, ll b, ll m) { a %= m; long long res = 1; while (b > 0) { if (b & 1) res = res * a % m; a = a * a % m; b >>= 1; } return res; } // For a < 2^31

#if 1
auto Start = chrono::high_resolution_clock::now();
void resettimer() { Start = chrono::high_resolution_clock::now(); }
int elapsedmillis() { return chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - Start).count(); }
random_device rd;
mt19937 rng(rd());
template<typename T, typename U> inline int randint(T lo, U hi) { return uniform_int_distribution<int>((int)lo, (int)hi)(rng); } // [lo,hi]
template<typename T> inline T randel(vector<T>& v) { return v[uniform_int_distribution<int>(int(0), int(v.size()) - int(1))(rng)]; } // [lo,hi]
#endif
const ll mod = 1e9 + 7;
vp2 dirs = { {0,1},{0,-1},{1,0},{-1,0} };

struct LazyTree
{
    vi tree;
    vi lazy;
    LazyTree(int n) : tree(n * 4, inf), lazy(n*4,inf) {}

    inline void push(int x)
    {
        tree[x * 2] = min(tree[x * 2], lazy[x]);
        tree[x * 2 + 1] = min(tree[x * 2 + 1], lazy[x]);
        lazy[x * 2] = min(lazy[x * 2], lazy[x]);
        lazy[x * 2+1] = min(lazy[x * 2+1], lazy[x]);
        lazy[x] = inf;
    }

    void update(int x, int l, int r, int ql, int qr, int v)
    {
        if (l > qr || r < ql) return;
        if (l >= ql && r <= qr)
        {
            lazy[x] = min(lazy[x], v);
            tree[x] = min(tree[x], v);
            return;
        }
        push(x);
        int mid = (l + r) / 2;
        update(x * 2, l, mid, ql, qr, v);
        update(x * 2 + 1, mid + 1, r, ql, qr, v);
        tree[x] = min(tree[x * 2], tree[x * 2 + 1]);
    }

    int query(int x, int l, int r, int ql, int qr)
    {
        if (l > qr || r < ql) return inf;
        if (l >= ql && r <= qr) return tree[x];
        push(x);
        int mid = (l + r) / 2;
        return min(query(x * 2, l, mid, ql, qr), query(x * 2 + 1, mid + 1, r, ql, qr));
    }
};

struct Tree
{
    vi tree;
    Tree(int n) : tree(n * 4, inf) {}

    void update(int x, int l, int r, int i, int v)
    {
        if (l == r) tree[x] = min(tree[x], v);
        else
        {
            int mid = (l + r) / 2;
            if (i<=mid) update(x * 2, l, mid, i, v);
            else update(x * 2 + 1, mid + 1, r, i, v);
            tree[x] = min(tree[x * 2], tree[x * 2 + 1]);
        }
    }

    int query(int x, int l, int r, int ql, int qr)
    {
        if (l > qr || r < ql) return inf;
        if (l >= ql && r <= qr) return tree[x];
        int mid = (l + r) / 2;
        return min(query(x * 2, l, mid, ql, qr), query(x * 2 + 1, mid + 1, r, ql, qr));
    }
};

int32_t main()
{
    fast();

    dread2(int, n, k);
    vector<Tree> treesmin(18,Tree(n));
    vector<Tree> treesmax(18,Tree(n));
    dread(int, m);

    LazyTree rootr(n);
    LazyTree rootl(n);
    rep(i, n)
    {
        rootl.update(1, 0, n - 1, i, i, i);
        rootr.update(1, 0, n - 1, i, i, -i);
    }
    rep(i, m)
    {
        dread2(int, a, b);
        a--; b--;
        int l, r;
        if (a<b)
        {
            l = a; r = min(a + k - 1, b);
            rootr.update(1, 0, n - 1, a, min(a+k-1,b), -b);
        }
        else
        {
            l = max(a - k + 1, b + 1); r = a;
            rootl.update(1, 0, n - 1, max(a - k + 1, b+1), a, b);
        }
    }

    rep(i, n)
    {
        treesmin[0].update(1, 0, n - 1, i, rootl.query(1, 0, n - 1, i, i));
        treesmax[0].update(1, 0, n - 1, i, rootr.query(1, 0, n - 1, i, i));
    }

    repp(d, 1, 18)
    {
        rep(i, n)
        {
            int l = treesmin[d - 1].query(1, 0, n - 1, i, i);
            int r = -treesmax[d - 1].query(1, 0, n - 1, i, i);

            int nl = treesmin[d - 1].query(1, 0, n - 1, l, r);
            int nr = treesmax[d - 1].query(1, 0, n - 1, l, r);
            treesmin[d].update(1, 0, n - 1, i, nl);
            treesmax[d].update(1, 0, n - 1, i, nr);
        }
    }

    dread(int, q);
    rep(i, q)
    {
        dread2(int, a, b);
        a--; b--;
        if (a<b)
        {
            if (-treesmax.back().query(1,0,n-1,a,a)<b)
            {
                cout << -1 << "\n";
                continue;
            }

            int l = a;
            int r = a;
            int ans = 0;
            per(d, 18)
            {
                if (-treesmax[d].query(1, 0, n - 1, l, r) < b)
                {
                    ans += 1 << d;
                    int nl = treesmin[d].query(1, 0, n - 1, l, r);
                    r = -treesmax[d].query(1, 0, n - 1, l, r);
                    l = nl;
                }
            }
            cout << ans+1 << "\n";
        }
        else
        {
            if (treesmin.back().query(1, 0, n - 1, a, a) > b)
            {
                cout << -1 << "\n";
                continue;
            }

            int l = a;
            int r = a;
            int ans = 0;
            per(d, 18)  
            {
                if (treesmin[d].query(1, 0, n - 1, l, r) > b)
                {
                    ans += 1 << d;
                    int nl = treesmin[d].query(1, 0, n - 1, l, r);
                    r = -treesmax[d].query(1, 0, n - 1, l, r);
                    l = nl;
                }
            }
            cout << ans+1 << "\n";
        }

    }

    quit;
}

Compilation message

Main.cpp: In function 'int32_t main()':
Main.cpp:240:13: warning: variable 'l' set but not used [-Wunused-but-set-variable]
  240 |         int l, r;
      |             ^
Main.cpp:240:16: warning: variable 'r' set but not used [-Wunused-but-set-variable]
  240 |         int l, r;
      |                ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 6 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 2 ms 716 KB Output is correct
12 Correct 3 ms 596 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 6 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 2 ms 716 KB Output is correct
12 Correct 3 ms 596 KB Output is correct
13 Correct 20 ms 2864 KB Output is correct
14 Correct 18 ms 2772 KB Output is correct
15 Correct 15 ms 2772 KB Output is correct
16 Correct 14 ms 2876 KB Output is correct
17 Correct 19 ms 2772 KB Output is correct
18 Correct 15 ms 2772 KB Output is correct
19 Correct 19 ms 2644 KB Output is correct
20 Correct 13 ms 2772 KB Output is correct
21 Correct 13 ms 2776 KB Output is correct
22 Correct 14 ms 2772 KB Output is correct
23 Correct 20 ms 2868 KB Output is correct
24 Correct 17 ms 2876 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1120 ms 125632 KB Output is correct
2 Correct 1116 ms 126588 KB Output is correct
3 Correct 1131 ms 126732 KB Output is correct
4 Correct 1077 ms 126480 KB Output is correct
5 Correct 715 ms 128012 KB Output is correct
6 Correct 1114 ms 127932 KB Output is correct
7 Correct 687 ms 127660 KB Output is correct
8 Correct 652 ms 125484 KB Output is correct
9 Correct 653 ms 126696 KB Output is correct
10 Correct 945 ms 127920 KB Output is correct
11 Correct 903 ms 127928 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1068 ms 125812 KB Output is correct
2 Correct 923 ms 126092 KB Output is correct
3 Correct 1281 ms 126172 KB Output is correct
4 Correct 792 ms 126092 KB Output is correct
5 Correct 776 ms 124844 KB Output is correct
6 Correct 810 ms 126132 KB Output is correct
7 Correct 1139 ms 126180 KB Output is correct
8 Correct 1095 ms 126220 KB Output is correct

Subtask #5
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 948 ms 125756 KB Output is correct
2 Correct 1498 ms 126272 KB Output is correct
3 Correct 1418 ms 126228 KB Output is correct
4 Correct 1361 ms 126192 KB Output is correct
5 Correct 1177 ms 126128 KB Output is correct
6 Correct 1189 ms 126116 KB Output is correct
7 Correct 950 ms 126008 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 15 ms 2772 KB Output is correct
10 Correct 924 ms 126012 KB Output is correct
11 Correct 1066 ms 126004 KB Output is correct
12 Correct 997 ms 124820 KB Output is correct
13 Correct 1061 ms 126104 KB Output is correct
14 Correct 2 ms 596 KB Output is correct
15 Correct 18 ms 2772 KB Output is correct
16 Correct 1055 ms 126056 KB Output is correct
17 Correct 1365 ms 126220 KB Output is correct
18 Correct 1331 ms 126232 KB Output is correct
19 Correct 1217 ms 126328 KB Output is correct

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 596 KB Output is correct
2 Correct 2 ms 724 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 6 ms 596 KB Output is correct
7 Correct 2 ms 596 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 2 ms 716 KB Output is correct
12 Correct 3 ms 596 KB Output is correct
13 Correct 20 ms 2864 KB Output is correct
14 Correct 18 ms 2772 KB Output is correct
15 Correct 15 ms 2772 KB Output is correct
16 Correct 14 ms 2876 KB Output is correct
17 Correct 19 ms 2772 KB Output is correct
18 Correct 15 ms 2772 KB Output is correct
19 Correct 19 ms 2644 KB Output is correct
20 Correct 13 ms 2772 KB Output is correct
21 Correct 13 ms 2776 KB Output is correct
22 Correct 14 ms 2772 KB Output is correct
23 Correct 20 ms 2868 KB Output is correct
24 Correct 17 ms 2876 KB Output is correct
25 Correct 1120 ms 125632 KB Output is correct
26 Correct 1116 ms 126588 KB Output is correct
27 Correct 1131 ms 126732 KB Output is correct
28 Correct 1077 ms 126480 KB Output is correct
29 Correct 715 ms 128012 KB Output is correct
30 Correct 1114 ms 127932 KB Output is correct
31 Correct 687 ms 127660 KB Output is correct
32 Correct 652 ms 125484 KB Output is correct
33 Correct 653 ms 126696 KB Output is correct
34 Correct 945 ms 127920 KB Output is correct
35 Correct 903 ms 127928 KB Output is correct
36 Correct 1068 ms 125812 KB Output is correct
37 Correct 923 ms 126092 KB Output is correct
38 Correct 1281 ms 126172 KB Output is correct
39 Correct 792 ms 126092 KB Output is correct
40 Correct 776 ms 124844 KB Output is correct
41 Correct 810 ms 126132 KB Output is correct
42 Correct 1139 ms 126180 KB Output is correct
43 Correct 1095 ms 126220 KB Output is correct
44 Correct 948 ms 125756 KB Output is correct
45 Correct 1498 ms 126272 KB Output is correct
46 Correct 1418 ms 126228 KB Output is correct
47 Correct 1361 ms 126192 KB Output is correct
48 Correct 1177 ms 126128 KB Output is correct
49 Correct 1189 ms 126116 KB Output is correct
50 Correct 950 ms 126008 KB Output is correct
51 Correct 2 ms 596 KB Output is correct
52 Correct 15 ms 2772 KB Output is correct
53 Correct 924 ms 126012 KB Output is correct
54 Correct 1066 ms 126004 KB Output is correct
55 Correct 997 ms 124820 KB Output is correct
56 Correct 1061 ms 126104 KB Output is correct
57 Correct 2 ms 596 KB Output is correct
58 Correct 18 ms 2772 KB Output is correct
59 Correct 1055 ms 126056 KB Output is correct
60 Correct 1365 ms 126220 KB Output is correct
61 Correct 1331 ms 126232 KB Output is correct
62 Correct 1217 ms 126328 KB Output is correct
63 Correct 1329 ms 127152 KB Output is correct
64 Correct 1468 ms 127400 KB Output is correct
65 Correct 1301 ms 127296 KB Output is correct
66 Correct 752 ms 128612 KB Output is correct
67 Correct 1330 ms 128680 KB Output is correct
68 Correct 1018 ms 127160 KB Output is correct
69 Correct 786 ms 128528 KB Output is correct
70 Correct 1099 ms 128552 KB Output is correct
71 Correct 1308 ms 128680 KB Output is correct