oj.uz

Submission #536061

# Submission time Handle Problem Language Result Execution time Memory
536061 2022-03-12T08:56:17 Z browntoad Fire (JOI20_ho_t5) C++14
13 / 100
 156 ms 21896 KB 
#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast", "unroll-loops")
using namespace std;
#define ll long long
#define int ll
#define FOR(i,a,b) for (int i = (a); i<(b); i++)
#define REP(i,n) FOR(i,0,n)
#define REP1(i,n) FOR(i,1,n+1)
#define RREP(i,n) for (int i=(n)-1; i>=0; i--)
#define RREP1(i,n) for (int i=(n); i>=1; i--)
#define f first
#define s second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)(x.size())
#define SQ(x) (x)*(x)
#define pii pair<int, int>
#define pdd pair<double ,double>
#define pcc pair<char, char> 
#define endl '\n'
//#define TOAD
#ifdef TOAD
#define bug(x) cerr<<__LINE__<<": "<<#x<<" is "<<x<<endl
#define IOS()
#else
#define bug(...)
#define IOS() ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#endif
 
const ll inf = 1ll<<60;
const int iinf=2147483647;
const ll mod = 1e9+7;
const ll maxn=2e5+5;
const double PI=acos(-1);
 
ll pw(ll x, ll p, ll m=mod){
    ll ret=1;
    while (p>0){
        if (p&1){
            ret*=x;
            ret%=m;
        }
        x*=x;
        x%=m;
        p>>=1;
    }
    return ret;
}
 
ll inv(ll a, ll m=mod){
    return pw(a,m-2);
}
 
//=======================================================================================
vector<int> seg(4*maxn);
vector<int> vc(maxn);
void build(int l, int r, int x){
    if (l==r){
        seg[x]=vc[l];
        return;
    }
    int mid=(l+r)/2;
    build(l, mid, x+x);
    build(mid+1, r, x+x+1);
    seg[x]=max(seg[x+x], seg[x+x+1]);
}
int query(int l, int r, int nl, int nr, int x){
    if (r<nl||l>nr){
        return 0;
    }
    if (nl>=l&&nr<=r){
        return seg[x];
    }
    int mid=(nl+nr)/2;
    return max(query(l, r, nl, mid, x+x), query(l, r, mid+1, nr, x+x+1));
}
struct typ{
    int l, r;
    int t;
};
signed main (){
    IOS();
    int n, q; cin>>n>>q;
    REP1(i,n) cin>>vc[i];
    vector<typ> vq(q);
    build(1, n, 1);
    bool gg=1;
    REP(i, q){
        cin>>vq[i].t>>vq[i].l>>vq[i].r;
        gg=(gg&(vq[i].l==vq[i].r));
    }
    if (!gg){
        vector<int> pf(n+1);
        REP1(i,n){
            int l=max(i-vq[0].t, 1ll);
            pf[i]=pf[i-1]+query(l, i, 1, n, 1);
        }

        REP(i, q){
            cout<<pf[vq[i].r]-pf[vq[i].l-1]<<endl;
        }
    }
    else {
        REP(i, q){
            int l=max(vq[i].l-vq[i].t, 1ll);
            cout<<query(l, vq[i].r, 1, n, 1)<<endl;
        }
    }

}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Incorrect 4 ms 8148 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 107 ms 17840 KB Output is correct
3 Correct 116 ms 21620 KB Output is correct
4 Correct 128 ms 21836 KB Output is correct
5 Correct 121 ms 21576 KB Output is correct
6 Correct 141 ms 21548 KB Output is correct
7 Correct 120 ms 21896 KB Output is correct
8 Correct 131 ms 21684 KB Output is correct
9 Correct 125 ms 21828 KB Output is correct
10 Correct 123 ms 21636 KB Output is correct
11 Correct 111 ms 21876 KB Output is correct
12 Correct 115 ms 21480 KB Output is correct
13 Correct 141 ms 21612 KB Output is correct
14 Correct 115 ms 21604 KB Output is correct
15 Correct 114 ms 21560 KB Output is correct
16 Correct 130 ms 21708 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Correct 138 ms 15756 KB Output is correct
3 Correct 156 ms 20104 KB Output is correct
4 Correct 140 ms 20384 KB Output is correct
5 Correct 152 ms 20044 KB Output is correct
6 Correct 132 ms 20168 KB Output is correct
7 Correct 152 ms 20104 KB Output is correct
8 Correct 156 ms 20360 KB Output is correct
9 Correct 143 ms 20208 KB Output is correct
10 Correct 148 ms 20012 KB Output is correct
11 Correct 141 ms 20388 KB Output is correct
12 Correct 148 ms 20032 KB Output is correct
13 Correct 146 ms 20356 KB Output is correct
14 Correct 155 ms 20136 KB Output is correct
15 Correct 138 ms 20216 KB Output is correct
16 Correct 139 ms 20020 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 16220 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8148 KB Output is correct
2 Incorrect 4 ms 8148 KB Output isn't correct
3 Halted 0 ms 0 KB -