oj.uz

Submission #859254

# Submission time Handle Problem Language Result Execution time Memory
859254 2023-10-10T02:25:17 Z chrispham258 Triple Jump (JOI19_jumps) C++17
19 / 100
 1072 ms 149936 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(pos + pos - it[id].ss > n) return walk(pham, mid + 1, r, pos);

                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, 1, n){
            // cout << i << " " << 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:212:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  212 | 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 4956 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 4956 KB Output is correct
11 Correct 1072 ms 149708 KB Output is correct
12 Correct 1062 ms 149844 KB Output is correct
13 Correct 1058 ms 149620 KB Output is correct
14 Correct 1060 ms 149740 KB Output is correct
15 Correct 1065 ms 149836 KB Output is correct
16 Correct 1057 ms 149232 KB Output is correct
17 Correct 1060 ms 148960 KB Output is correct
18 Correct 1056 ms 149180 KB Output is correct
19 Correct 1058 ms 149936 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 10844 KB Output is correct
2 Incorrect 25 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 4956 KB Output is correct
11 Correct 1072 ms 149708 KB Output is correct
12 Correct 1062 ms 149844 KB Output is correct
13 Correct 1058 ms 149620 KB Output is correct
14 Correct 1060 ms 149740 KB Output is correct
15 Correct 1065 ms 149836 KB Output is correct
16 Correct 1057 ms 149232 KB Output is correct
17 Correct 1060 ms 148960 KB Output is correct
18 Correct 1056 ms 149180 KB Output is correct
19 Correct 1058 ms 149936 KB Output is correct
20 Correct 18 ms 10844 KB Output is correct
21 Incorrect 25 ms 10844 KB Output isn't correct
22 Halted 0 ms 0 KB -