Submission #859349

#	Time	Username	Problem	Language	Result	Execution time	Memory
859349		Boycl07	Triple Jump (JOI19_jumps)	C++17	100 / 100	470 ms	48624 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

#define rep(i, n) for(int i = 1; i <= n; ++i)
#define forn(i, l, r) for(int i = l; i <= r; ++i)
#define ford(i, r, l) for(int i = r; i >= l; --i)
#define FOR(i, n) for(int i = 0; i < n; ++i)
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define task "MEETING"
#define endl "\n"
#define sz(a) int(a.size())
#define C(x, y) make_pair(x, y)
#define all(a) (a).begin(), (a).end()
#define bit(i, mask) (mask >> i & 1)

template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }


const int N =  5e5 + 10;
const int N1 = 2e3 + 10;
const int K = 1e2 + 1;
const int MOD = 1e9 + 7;
const int INF = 1e9 + 1;
const int block_size = 230;
const int LOG = 13;
const int offset = N;
const int LIM = 2e5;
const int AL = 26;
const int M = 11;
const int lim = (1 << 10) - 1;


int n;
int a[N];
int q;

struct node
{
    int x, y, v;
    node () {
        x = 0, y = 0, v = 0;
    }
    node (int x_, int y_, int v_) : x(x_), y(y_), v(v_) {}
    friend node operator + (const node &u, const node &v) {
        return node(max(u.x, v.x), max(u.y, v.y), max(max(u.v, v.v), u.x + v.y));
    }
};


node st[N << 1];

void build()
{
    for(int i = 1; i <= n; ++i)
        st[i + n].y = st[i + n].v = a[i], st[i + n].x = 0;
    for(int i = n; i >= 1; --i)
        st[i] = st[i << 1] + st[i << 1 | 1];
}

void update(int idx, int val)
{
    idx += n;
    maximize(st[idx].x, val);
    st[idx].v = st[idx].x + st[idx].y;
    for(; idx >>= 1;)
    {
        st[idx] = st[idx << 1] + st[idx << 1 | 1];
    }
}

ll get(int l, int r)
{
    node resl(0, 0, 0);
    node resr(0, 0, 0);
    for(l += n, r += n + 1; l < r; l >>= 1, r >>= 1)
    {
        
        if(l & 1) resl = resl + st[l++];
        if( r & 1) resr = st[--r] + resr;
        //cout << l << " " << r << endl;
        //cout << endl;
    }
    return (resl + resr).v;
}


vector<pii> query[N];
int res[N];

void solve()
{
    cin >> n;
    rep(i, n) cin >> a[i];
    build();
    cin >> q;
    rep(i, q)
    {
        int l, r;
        cin >> l >> r;
        query[l].pb({r, i});
    }   

    stack<int> s;
    ford(i, n, 1)
    {
        while(sz(s) && a[s.top()] < a[i])
        {
            if(2 * s.top() - i <= n)
                update(2 * s.top() - i, a[i] + a[s.top()]);// cout << 2 * s.top() - i << " " << a[i] + a[s.top()] << endl;
           
            s.pop();
        }
        if(sz(s))
        {
            if(2 * s.top() - i <= n)
                update(2 * s.top() - i, a[i] + a[s.top()]);// cout << 2 * s.top() - i << " " << a[i] + a[s.top()] << endl;
        }
        s.push(i);
        for(auto &[j, idx] : query[i])
            res[idx] = get(i, j);
    }
    rep(i, q) cout << res[i] << endl;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    if(fopen("trie.inp", "r"))
    {
        freopen("trie.inp", "r", stdin);
        freopen("trie.out", "w", stdout);
    }

    int TC = 1;

    while(TC--)
    {
        solve();
        cout << endl;
    }

    return 0;
}
//ha

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:140:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |         freopen("trie.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:141:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |         freopen("trie.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54