oj.uz

Submission #515465

# Submission time Handle Problem Language Result Execution time Memory
515465 2022-01-19T07:57:38 Z fcmalkcin Triple Jump (JOI19_jumps) C++17
100 / 100
 1244 ms 107244 KB 
/*#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;
    }
}

Compilation message

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23808 KB Output is correct
2 Correct 12 ms 23784 KB Output is correct
3 Correct 12 ms 23792 KB Output is correct
4 Correct 12 ms 23756 KB Output is correct
5 Correct 12 ms 23756 KB Output is correct
6 Correct 12 ms 23756 KB Output is correct
7 Correct 12 ms 23724 KB Output is correct
8 Correct 17 ms 23828 KB Output is correct
9 Correct 13 ms 23756 KB Output is correct
10 Correct 13 ms 23756 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23808 KB Output is correct
2 Correct 12 ms 23784 KB Output is correct
3 Correct 12 ms 23792 KB Output is correct
4 Correct 12 ms 23756 KB Output is correct
5 Correct 12 ms 23756 KB Output is correct
6 Correct 12 ms 23756 KB Output is correct
7 Correct 12 ms 23724 KB Output is correct
8 Correct 17 ms 23828 KB Output is correct
9 Correct 13 ms 23756 KB Output is correct
10 Correct 13 ms 23756 KB Output is correct
11 Correct 344 ms 51392 KB Output is correct
12 Correct 373 ms 51452 KB Output is correct
13 Correct 352 ms 51432 KB Output is correct
14 Correct 376 ms 51416 KB Output is correct
15 Correct 353 ms 51456 KB Output is correct
16 Correct 344 ms 50884 KB Output is correct
17 Correct 418 ms 50796 KB Output is correct
18 Correct 367 ms 50600 KB Output is correct
19 Correct 350 ms 51332 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 203 ms 45164 KB Output is correct
2 Correct 149 ms 47332 KB Output is correct
3 Correct 114 ms 45680 KB Output is correct
4 Correct 239 ms 46920 KB Output is correct
5 Correct 206 ms 46924 KB Output is correct
6 Correct 212 ms 46384 KB Output is correct
7 Correct 192 ms 46144 KB Output is correct
8 Correct 199 ms 46060 KB Output is correct
9 Correct 198 ms 46476 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23808 KB Output is correct
2 Correct 12 ms 23784 KB Output is correct
3 Correct 12 ms 23792 KB Output is correct
4 Correct 12 ms 23756 KB Output is correct
5 Correct 12 ms 23756 KB Output is correct
6 Correct 12 ms 23756 KB Output is correct
7 Correct 12 ms 23724 KB Output is correct
8 Correct 17 ms 23828 KB Output is correct
9 Correct 13 ms 23756 KB Output is correct
10 Correct 13 ms 23756 KB Output is correct
11 Correct 344 ms 51392 KB Output is correct
12 Correct 373 ms 51452 KB Output is correct
13 Correct 352 ms 51432 KB Output is correct
14 Correct 376 ms 51416 KB Output is correct
15 Correct 353 ms 51456 KB Output is correct
16 Correct 344 ms 50884 KB Output is correct
17 Correct 418 ms 50796 KB Output is correct
18 Correct 367 ms 50600 KB Output is correct
19 Correct 350 ms 51332 KB Output is correct
20 Correct 203 ms 45164 KB Output is correct
21 Correct 149 ms 47332 KB Output is correct
22 Correct 114 ms 45680 KB Output is correct
23 Correct 239 ms 46920 KB Output is correct
24 Correct 206 ms 46924 KB Output is correct
25 Correct 212 ms 46384 KB Output is correct
26 Correct 192 ms 46144 KB Output is correct
27 Correct 199 ms 46060 KB Output is correct
28 Correct 198 ms 46476 KB Output is correct
29 Correct 1234 ms 103980 KB Output is correct
30 Correct 986 ms 104964 KB Output is correct
31 Correct 1166 ms 100836 KB Output is correct
32 Correct 1242 ms 104144 KB Output is correct
33 Correct 1244 ms 104088 KB Output is correct
34 Correct 1233 ms 101744 KB Output is correct
35 Correct 1242 ms 101516 KB Output is correct
36 Correct 1198 ms 101368 KB Output is correct
37 Correct 1226 ms 102968 KB Output is correct
38 Correct 906 ms 106604 KB Output is correct
39 Correct 909 ms 106564 KB Output is correct
40 Correct 900 ms 103304 KB Output is correct
41 Correct 884 ms 102844 KB Output is correct
42 Correct 905 ms 102892 KB Output is correct
43 Correct 955 ms 104644 KB Output is correct
44 Correct 994 ms 106912 KB Output is correct
45 Correct 969 ms 107076 KB Output is correct
46 Correct 946 ms 103784 KB Output is correct
47 Correct 926 ms 103344 KB Output is correct
48 Correct 924 ms 103316 KB Output is correct
49 Correct 929 ms 105356 KB Output is correct
50 Correct 1032 ms 107172 KB Output is correct
51 Correct 1026 ms 107244 KB Output is correct
52 Correct 999 ms 104816 KB Output is correct
53 Correct 991 ms 104324 KB Output is correct
54 Correct 985 ms 104384 KB Output is correct
55 Correct 998 ms 106052 KB Output is correct