oj.uz

Submission #859342

# Submission time Handle Problem Language Result Execution time Memory
859342 2023-10-10T04:22:42 Z chrispham258 Triple Jump (JOI19_jumps) C++17
100 / 100
 751 ms 95272 KB 
/* Pham Ngoc Tho aka Chis Pham                           */
/* [Author : Pham Ngoc Tho] - THPT Chuyen Nguyen Du      */
/* [ 2024 - 12TH GO VOI 24 ] - From Nguyen Du with love  */

// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include<bits/stdc++.h>
using namespace std;

#define oo 0x3f
#define ff first
#define ss second
#define endl "\n"
#define ins insert
#define chis id<<1
#define pham (id<<1) + 1
#define sqr(x) ((x) * 1ll * (x))
#define gcd(a, b) __gcd(a, b)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(),x.rend()
#define repu(i, x, n) for(int i = x; i <= n; ++i)
#define repd(i, n, x) for(int i = n; i >= x; --i)
#define reset(x, val) memset(x, val, sizeof(x))

typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

template<class T> bool getbit(T val, int i) { return (val >> i) & 1; }
template<class T> int cntbit(T val)        { return val == 0 ? 0 : cntbit(val >> 1) + (val & 1); }
template<class T> ll fpow(T a, const T b) { ll res = 1, x = a, y = b; while(y){if(y & 1)res *= x; x = x * x; y>>=1;}; return res; }
template<class T> ll modfpow(T a, T b, const T &m) { ll res = 1, x = a, y = b; x %= m; while(y){if(y & 1){res *= x; res %= m;}; x = x * x; x %= m; y >>= 1; } return res % m; }
template<class T> T lcm(T &a, T &b) { return a / gcd(a, b) * b; }

const int mod = 1e9 + 7;
const int INF = 1e9 + 7;
const ll LNF = 1e18 + 7;

inline char gc() { static char buf[1 << 23]; static size_t bc, be; if(bc >= be){ buf[0] = 0, bc = 0; be = fread(buf, 1, sizeof(buf), stdin); } return buf[bc++]; }
ll readLL() { ll a, c; while ((a = gc()) < 20); if (a == '-') return -readLL(); while ((c = gc()) >= 48) a = a * 10 + c - 480; return a - 48; }
int readInt() { int a, c; while ((a = gc()) < 10); if (a == '-') return -readInt(); while ((c = gc()) >= 48) a = a * 10 + c - 480; return a - 48; }

mt19937 RND(time(nullptr));
ll rnd(ll l, ll r)
{
    assert(l <= r);ll L = l, R = r;
    ll aft = (L + RND() * 1LL % (R - L + 1));
    return aft;
}

#define TASK "name"
#define FILE "DEBUG"
void setIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    if(fopen(FILE".INP", "r")){freopen(FILE".INP", "r", stdin);freopen(FILE".OUT", "w", stdout);}
    if(fopen(TASK".INP", "r")){freopen(TASK".INP", "r", stdin);freopen(TASK".OUT", "w", stdout);}
}

template<class T> T multi(const T &a, const T &b) { T res = (a*b)%mod; return res;}
template<class T> bool umax(T &a, T b) { if(a < b){ a = b; return 1;} else return 0;}
template<class T> bool umin(T &a, T b) { if(a > b){ a = b; return 1;} else return 0;}

const int NmX = 5e5 + 7;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};

int n;
ll a[NmX];

void read()
{
    cin >> n;
    repu(i, 1, n) cin >> a[i];
}

namespace sub2{
    const int N = 5e3 + 7;

    class IT{
        public:
            int it[4 * N];

            void build(int id, int l, int r){
                if(l == r){
                    it[id] = a[l];
                    return;
                }

                int mid = (l + r) >> 1;
                build(chis, l, mid);
                build(pham, mid + 1, r);
                it[id] = max(it[chis], it[pham]);
            }

            int get(int id, int l, int r, int u, int v){
                if(r < u || v < l) return -INF;
                if(u <= l && r <= v) return it[id];
                int mid = (l + r) >> 1;
                return max(get(chis, l, mid, u, v), get(pham, mid + 1, r, u, v));
            }
    }IT;

    ll f[N][N], fi[N][N];

    void solve(){
        IT.build(1, 1, n);

        repu(i, 1, n)
        {
            repu(j, i + 2, n)
            {
                int k = (i + j)/2;
                f[i][j] = a[i] + a[j] + IT.get(1, 1, n, i + 1, k);
                umax(f[i][j], f[i][j - 1]);
            }
        }

        repd(i, n, 1){
            repu(j, 1, n)
                umax(f[i - 1][j], f[i][j]);
        }        

        int q; cin >> q;
        while(q--){
            int u, v;
            cin >> u >> v;
            cout << f[u][v] << endl;
        }
    }
}

namespace sub3{
    const int N = 2e5 + 7;
    ll pre[2 * N];

    void solve(){
        stack<int> st;
        repu(i, 1, n){
            while(st.size() && a[st.top()] < a[i]){
                umax(pre[2 * i - st.top()], a[i] + a[st.top()]);
                st.pop();
            }
            if(st.size()) umax(pre[2 * i - st.top()], a[i] + a[st.top()]);
            st.push(i);
        }

        repu(i, 1, n) umax(pre[i], pre[i - 1]);
        ll res = 0;
        repu(i, 1, n) umax(res, pre[i] + a[i]);
        cout << res; 
    }
}

namespace sub4{

    vector<pii> qr[NmX], upd[NmX];
    int res[NmX];

    struct node{
        int pre, val, sum;
        node(){ pre = val = sum = 0; };
        node(int pre, int val, int sum) : pre(pre), val(val), sum(sum) {};
        friend node operator + (const node &x, const node &y){
            return node(max(x.pre, y.pre), max(x.val, y.val), max({x.sum, y.sum, x.pre + y.val}));
        }
    };

    node it[4 * NmX];

    void build(int id, int l, int r){
        if(l == r){
            it[id] = node(0, a[l], a[l]);
            return;
        }
        int mid = (l + r) >> 1;
        build(chis, l, mid);
        build(pham, mid + 1, r);
        it[id] = it[chis] + it[pham];
    }

    void update(int id, int l, int r, int pos, int val){
        if(r < pos || pos < l) return;
        if(l == r && r == pos){
            umax(it[id].pre, val);
            it[id].sum = it[id].pre + it[id].val;
            return;
        }
        int mid = (l + r) >> 1;
        update(chis, l, mid, pos, val);
        update(pham, mid + 1, r, pos, val);
        it[id] = it[chis] + it[pham];
    }

    node query(int id, int l, int r, int u, int v){
        if(r < u || v < l) return node(0, 0, 0);
        if(u <= l && r <= v) return it[id];
        int mid = (l + r) >> 1;
        return query(chis, l, mid, u, v) + query(pham, mid + 1, r, u, v);
    }

    void solve(){
        int q; cin >> q;
        repu(i, 1, q){
            int l, r;
            cin >> l >> r;
            qr[l].eb(pii(r, i));
        }

        build(1, 1, n);

        stack<int> st;
        repu(i, 1, n){
            while(st.size() && a[st.top()] < a[i]){
                int j = st.top();
                upd[j].eb(pii(i, a[i] + a[j]));
                st.pop();
            }
            if(st.size())
                upd[st.top()].eb(pii(i, a[i] + a[st.top()]));
            st.push(i);
        }    


        repd(i, n, 1){  
            for(pii x : upd[i]) 
                if(2 * x.ff - i <= n) 
                    update(1, 1, n, 2 * x.ff - i, x.ss);
            for(pii x : qr[i])
                res[x.ss] = query(1, 1, n, i, x.ff).sum;
        }

        repu(i, 1, q) cout << res[i] << endl;
    }
}

void process()
{
    // if(n <= 5000) sub2::solve();
    // else sub3::solve();
    sub4::solve();
}

main()
{
    setIO();
    int test = 1;
    // cin >> test;
    while(test--)
    {
        read();
        process();
    }

    cerr << "Time elapsed: " << (1.0 * clock()/CLOCKS_PER_SEC) * 1000 << "ms.\n";
    return 0;
}

Compilation message

jumps.cpp:250:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  250 | main()
      | ^~~~
jumps.cpp: In function 'void setIO()':
jumps.cpp:62:39: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     if(fopen(FILE".INP", "r")){freopen(FILE".INP", "r", stdin);freopen(FILE".OUT", "w", stdout);}
      |                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:62:71: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |     if(fopen(FILE".INP", "r")){freopen(FILE".INP", "r", stdin);freopen(FILE".OUT", "w", stdout);}
      |                                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:63:39: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     if(fopen(TASK".INP", "r")){freopen(TASK".INP", "r", stdin);freopen(TASK".OUT", "w", stdout);}
      |                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:63:71: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |     if(fopen(TASK".INP", "r")){freopen(TASK".INP", "r", stdin);freopen(TASK".OUT", "w", stdout);}
      |                                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 53864 KB Output is correct
2 Correct 10 ms 53852 KB Output is correct
3 Correct 11 ms 53852 KB Output is correct
4 Correct 12 ms 54108 KB Output is correct
5 Correct 10 ms 53932 KB Output is correct
6 Correct 10 ms 53852 KB Output is correct
7 Correct 11 ms 53852 KB Output is correct
8 Correct 10 ms 53944 KB Output is correct
9 Correct 10 ms 53852 KB Output is correct
10 Correct 11 ms 53852 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 53864 KB Output is correct
2 Correct 10 ms 53852 KB Output is correct
3 Correct 11 ms 53852 KB Output is correct
4 Correct 12 ms 54108 KB Output is correct
5 Correct 10 ms 53932 KB Output is correct
6 Correct 10 ms 53852 KB Output is correct
7 Correct 11 ms 53852 KB Output is correct
8 Correct 10 ms 53944 KB Output is correct
9 Correct 10 ms 53852 KB Output is correct
10 Correct 11 ms 53852 KB Output is correct
11 Correct 242 ms 65876 KB Output is correct
12 Correct 258 ms 65616 KB Output is correct
13 Correct 245 ms 65776 KB Output is correct
14 Correct 239 ms 65876 KB Output is correct
15 Correct 241 ms 65676 KB Output is correct
16 Correct 254 ms 65196 KB Output is correct
17 Correct 243 ms 65256 KB Output is correct
18 Correct 245 ms 65104 KB Output is correct
19 Correct 243 ms 65716 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 63488 KB Output is correct
2 Correct 60 ms 62100 KB Output is correct
3 Correct 62 ms 63060 KB Output is correct
4 Correct 113 ms 63488 KB Output is correct
5 Correct 113 ms 63312 KB Output is correct
6 Correct 115 ms 63572 KB Output is correct
7 Correct 111 ms 63480 KB Output is correct
8 Correct 109 ms 63316 KB Output is correct
9 Correct 109 ms 63472 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 53864 KB Output is correct
2 Correct 10 ms 53852 KB Output is correct
3 Correct 11 ms 53852 KB Output is correct
4 Correct 12 ms 54108 KB Output is correct
5 Correct 10 ms 53932 KB Output is correct
6 Correct 10 ms 53852 KB Output is correct
7 Correct 11 ms 53852 KB Output is correct
8 Correct 10 ms 53944 KB Output is correct
9 Correct 10 ms 53852 KB Output is correct
10 Correct 11 ms 53852 KB Output is correct
11 Correct 242 ms 65876 KB Output is correct
12 Correct 258 ms 65616 KB Output is correct
13 Correct 245 ms 65776 KB Output is correct
14 Correct 239 ms 65876 KB Output is correct
15 Correct 241 ms 65676 KB Output is correct
16 Correct 254 ms 65196 KB Output is correct
17 Correct 243 ms 65256 KB Output is correct
18 Correct 245 ms 65104 KB Output is correct
19 Correct 243 ms 65716 KB Output is correct
20 Correct 112 ms 63488 KB Output is correct
21 Correct 60 ms 62100 KB Output is correct
22 Correct 62 ms 63060 KB Output is correct
23 Correct 113 ms 63488 KB Output is correct
24 Correct 113 ms 63312 KB Output is correct
25 Correct 115 ms 63572 KB Output is correct
26 Correct 111 ms 63480 KB Output is correct
27 Correct 109 ms 63316 KB Output is correct
28 Correct 109 ms 63472 KB Output is correct
29 Correct 747 ms 89808 KB Output is correct
30 Correct 607 ms 86472 KB Output is correct
31 Correct 607 ms 88488 KB Output is correct
32 Correct 729 ms 89484 KB Output is correct
33 Correct 745 ms 89488 KB Output is correct
34 Correct 748 ms 88980 KB Output is correct
35 Correct 718 ms 88748 KB Output is correct
36 Correct 751 ms 89052 KB Output is correct
37 Correct 720 ms 89680 KB Output is correct
38 Correct 590 ms 95272 KB Output is correct
39 Correct 576 ms 95136 KB Output is correct
40 Correct 570 ms 93620 KB Output is correct
41 Correct 575 ms 93308 KB Output is correct
42 Correct 575 ms 93528 KB Output is correct
43 Correct 572 ms 94292 KB Output is correct
44 Correct 606 ms 94664 KB Output is correct
45 Correct 602 ms 94532 KB Output is correct
46 Correct 598 ms 93020 KB Output is correct
47 Correct 601 ms 92976 KB Output is correct
48 Correct 599 ms 92880 KB Output is correct
49 Correct 598 ms 94072 KB Output is correct
50 Correct 653 ms 92368 KB Output is correct
51 Correct 650 ms 92496 KB Output is correct
52 Correct 655 ms 91852 KB Output is correct
53 Correct 643 ms 91984 KB Output is correct
54 Correct 641 ms 91732 KB Output is correct
55 Correct 639 ms 92464 KB Output is correct