oj.uz

Submission #859245

# Submission time Handle Problem Language Result Execution time Memory
859245 2023-10-10T02:16:57 Z chrispham258 Triple Jump (JOI19_jumps) C++17
19 / 100
 1075 ms 149836 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 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[N];

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

            void refine(int id){
                int mx = max(it[chis].ff, it[pham].ff);
                if(mx == it[chis].ff){
                    it[id] = it[chis];
                    if(mx == it[pham].ff) it[id].ss = max(it[chis].ss, it[pham].ss);
                }
                else it[id] = it[pham];
            }

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

            ll walk(int id, int l, int r, int pos){
                if(pos < l) return 0;
                if(l == r && it[id].ss == pos) return 0;
                else if(l == r) return it[id].ff + a[pos] + pre[pos + pos - it[id].ss];
                int mid = (l + r) >> 1;
                
                if(it[id].ss == pos)
                    return max(walk(chis, l, mid, pos), walk(pham, mid + 1, r, pos));
                else{
                    if(it[id].ff == it[chis].ff){
                        if(pos + pos - it[chis].ss > pos){
                            ll res = it[id].ff + a[pos] + pre[pos + pos - it[chis].ss];
                            return max(res, walk(pham, mid + 1, r, pos));
                        }else return walk(pham, mid + 1, r, pos);
                    }else{
                        if(pos + pos - it[pham].ss > pos){
                            ll res = it[id].ff + a[pos] + pre[pos + pos - it[pham].ss];
                            return max(res, walk(chis, l, mid, pos));
                        }else return walk(chis, l, mid, pos);
                    }
                }
            }
    }IT;


    void solve(){
        IT.build(1, 1, n);
        pre[n] = a[n];
        repd(i, n - 1, 1) umax(pre[i], max(pre[i + 1], a[i]));
        
        ll res = 0;
        repu(i, 2, n - 1){
            // cout << IT.walk(1, 1, n, i) << endl;
            umax(res, IT.walk(1, 1, n, i)); 
        }
        cout << res;
    }
}
void process()
{
    if(n <= 5000) sub2::solve();
    else sub3::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:210:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  210 | main()
      | ^~~~
jumps.cpp: In function 'void setIO()':
jumps.cpp:61:39: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     if(fopen(FILE".INP", "r")){freopen(FILE".INP", "r", stdin);freopen(FILE".OUT", "w", stdout);}
      |                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:61:71: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |     if(fopen(FILE".INP", "r")){freopen(FILE".INP", "r", stdin);freopen(FILE".OUT", "w", stdout);}
      |                                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
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(TASK".INP", "r")){freopen(TASK".INP", "r", stdin);freopen(TASK".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(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 1 ms 4444 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 1 ms 4956 KB Output is correct
10 Correct 1 ms 4952 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 1 ms 4956 KB Output is correct
10 Correct 1 ms 4952 KB Output is correct
11 Correct 1042 ms 149680 KB Output is correct
12 Correct 1074 ms 149792 KB Output is correct
13 Correct 1071 ms 149608 KB Output is correct
14 Correct 1045 ms 149836 KB Output is correct
15 Correct 1067 ms 149724 KB Output is correct
16 Correct 1055 ms 149204 KB Output is correct
17 Correct 1070 ms 149016 KB Output is correct
18 Correct 1044 ms 149492 KB Output is correct
19 Correct 1075 ms 149760 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 10844 KB Output is correct
2 Incorrect 30 ms 10844 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 4956 KB Output is correct
4 Correct 1 ms 4956 KB Output is correct
5 Correct 1 ms 4956 KB Output is correct
6 Correct 1 ms 4956 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 1 ms 4956 KB Output is correct
9 Correct 1 ms 4956 KB Output is correct
10 Correct 1 ms 4952 KB Output is correct
11 Correct 1042 ms 149680 KB Output is correct
12 Correct 1074 ms 149792 KB Output is correct
13 Correct 1071 ms 149608 KB Output is correct
14 Correct 1045 ms 149836 KB Output is correct
15 Correct 1067 ms 149724 KB Output is correct
16 Correct 1055 ms 149204 KB Output is correct
17 Correct 1070 ms 149016 KB Output is correct
18 Correct 1044 ms 149492 KB Output is correct
19 Correct 1075 ms 149760 KB Output is correct
20 Correct 19 ms 10844 KB Output is correct
21 Incorrect 30 ms 10844 KB Output isn't correct
22 Halted 0 ms 0 KB -