제출 #515465

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
515465		fcmalkcin	3단 점프 (JOI19_jumps)	C++17	100 / 100	1244 ms	107244 KiB

jumps

/*#pragma GCC optimize("Ofast")
#pragma GCC optimization("unroll-loops, no-stack-protector")
#pragma GCC target("avx,avx2,fma")*/

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

#define ll  long long
#define pll pair<ll,ll>
#define ff first
#define ss second
#define pb push_back
#define endl "\n"
#define F(i,a,b) for (ll i=a;i<=b;i++)

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=5e5+40;
const ll mod=1000003 ;
const ll base=3e18;

/// you will be the best but now you just are trash
/// goal 1/7
ll n;
ll a[maxn];
vector<pll> adj[maxn];
vector<ll> adj1[maxn];
ll res[maxn];

struct tk
{
    ll la=0;
    ll val=0;
    ll mx=0;
};
tk st[4*maxn];
tk mer(tk a,tk b)
{
    a.la=0;
    b.la=0;
    if (a.mx==-base) return b;
    if (b.mx==-base) return a;
    tk c;
    c.val=max(a.val,b.val);
    c.mx=max(a.mx,b.mx);
    return c ;
}
void build(ll id,ll left,ll right)
{
    if (left==right)
    {
        st[id].mx=a[left];
        st[id].val=a[left];
        return ;
    }
    ll mid=(left+right)/2;
    build(id*2,left,mid);
    build(id*2+1,mid+1,right);
    st[id]=mer(st[id*2],st[id*2+1]);
}
void dosth(ll id,ll left,ll right)
{
   if (st[id].la==0) return ;
   st[id*2].la=max(st[id*2].la,st[id].la);
   st[id*2+1].la=max(st[id*2+1].la,st[id].la);
   st[id*2].mx=max(st[id*2].mx,st[id].la+st[id*2].val);
   st[id*2+1].mx=max(st[id*2+1].mx,st[id].la+st[id*2+1].val);
   st[id].la=0;
}
void update(ll id,ll left,ll right,ll x,ll y,ll diff)
{
    if (x>right||y<left) return ;
    if (x<=left&&y>=right)
    {
        st[id].la=max(st[id].la,diff);
        st[id].mx=max(st[id].mx,st[id].val+diff);
        return ;
    }
    dosth(id,left,right);
    ll mid=(left+right)/2;
    update(id*2,left,mid,x,y,diff);
    update(id*2+1,mid+1,right,x,y,diff);
    st[id]=mer(st[id*2],st[id*2+1]);
}
tk get(ll id,ll left,ll right,ll x,ll y)
{
    tk a;
    a.mx=-base;
    if (x>right||y<left) return a;
    if (x<=left&&y>=right) return st[id];
    dosth(id,left,right);
    ll mid=(left+right)/2;
    return mer(get(id*2,left,mid,x,y),get(id*2+1,mid+1,right,x,y));
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("t.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    cin>> n;
    for (int i=1;i<=n;i++)
    {
        cin>> a[i];
    }
    stack<ll> st;
    for (int i=n;i>=1;i--)
    {
        while (!st.empty())
        {
            auto p=st.top();
            adj1[i].pb(p);
            if (a[i]<a[p]) break;
            else st.pop();
        }
        st.push(i);
    }
    build(1,1,n);
    ll q;
    cin>> q;
    for (int i=1;i<=q;i++)
    {
        ll x , y;
        cin>>x>> y;
        adj[x].pb(make_pair(y,i));
    }
    for (int i=n;i>=1;i--)
    {
        for (auto to:adj1[i])
        {
          //  cout <<i<<" "<<to<<" chk"<<endl;
            ll nxt=2*to-i;
            update(1,1,n,nxt,n,a[i]+a[to]);
        }
        for (auto to:adj[i])
        {
            res[to.ss]=get(1,1,n,i,to.ff).mx;
        }
    }
    for (int i=1;i<=q;i++)
    {
        cout <<res[i]<<endl;
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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

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