oj.uz

Submission #859219

# Submission time Handle Problem Language Result Execution time Memory
859219 2023-10-10T01:53:54 Z chrispham258 Triple Jump (JOI19_jumps) C++17
19 / 100
 1101 ms 149536 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 * NmX];

            void refine(int id){
                int mx = max(it[chis].ff, it[pham].ff);
                if(mx == it[chis].ff) it[id] = it[chis];
                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;
                int mid = (l + r) >> 1;
                if(it[id].ff == it[chis].ff){
                    ll res = it[id].ff + a[pos] + pre[pos + pos - it[id].ss];
                    return max(res, walk(pham, mid + 1, r, pos));
                }
                else{
                    ll res = it[id].ff + a[pos] + pre[pos + pos - it[id].ss];
                    return max(res, 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) umax(res, IT.walk(1, 1, n, i)); 
    }
}
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:193:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  193 | 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 4440 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 5000 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 5200 KB Output is correct
7 Correct 1 ms 4952 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 4440 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 5000 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 5200 KB Output is correct
7 Correct 1 ms 4952 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 1046 ms 149288 KB Output is correct
12 Correct 1066 ms 149332 KB Output is correct
13 Correct 1101 ms 149264 KB Output is correct
14 Correct 1068 ms 149252 KB Output is correct
15 Correct 1073 ms 149536 KB Output is correct
16 Correct 1046 ms 148644 KB Output is correct
17 Correct 1062 ms 148816 KB Output is correct
18 Correct 1088 ms 148640 KB Output is correct
19 Correct 1098 ms 149372 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 38 ms 27772 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 1 ms 4956 KB Output is correct
3 Correct 1 ms 5000 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 5200 KB Output is correct
7 Correct 1 ms 4952 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 1046 ms 149288 KB Output is correct
12 Correct 1066 ms 149332 KB Output is correct
13 Correct 1101 ms 149264 KB Output is correct
14 Correct 1068 ms 149252 KB Output is correct
15 Correct 1073 ms 149536 KB Output is correct
16 Correct 1046 ms 148644 KB Output is correct
17 Correct 1062 ms 148816 KB Output is correct
18 Correct 1088 ms 148640 KB Output is correct
19 Correct 1098 ms 149372 KB Output is correct
20 Runtime error 38 ms 27772 KB Execution killed with signal 11
21 Halted 0 ms 0 KB -