Submission #786384

#	Time	Username	Problem	Language	Result	Execution time	Memory
786384		PenguinsAreCute	역사적 조사 (JOI14_historical)	C++17	100 / 100	2974 ms	14760 KiB

historic

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL_MAX LONG_LONG_MAX
#define LL_MIN LONG_LONG_MIN
#define speed ios_base::sync_with_stdio(false); cin.tie(0)
#define stMx(a,b) a = max(a,b)
#define stMn(a,b) a = min(a,b)
struct qry{int l, r, idx;};
#define REP(i, a, b) for(int i = a; i < b; i++)
#define lb(v,x) (lower_bound(v,v+N,x)-v)
#define BSIZE 400
bool comp(qry a, qry b) {
    if(a.l/BSIZE==b.l/BSIZE) return a.r<b.r;
    return a.l<b.l;
}
int vec[121010];
#define MAXN 131072
int s[2*MAXN], e[2*MAXN], val[2*MAXN];
void init(int st, int en) {
    s[1]=st; e[1]=en;
    REP(i,1,131072) if(s[i]!=e[i]) {
        //printf("%lld %lld %lld\n", i, s[i], e[i]);
        int mid = (s[i] + e[i]) >> 1;
        s[i<<1]=s[i];
        e[i<<1]=mid;
        s[i<<1|1]=mid+1,
        e[i<<1|1]=e[i];
    }
}

void update(int x, int u) {
    int i = x + 131072;
    val[i] += u;
    while(i) {
        i /= 2;
        if(i) val[i] = max(val[i<<1],val[i<<1|1]);
    }
}
int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int N, Q, l=1,r=0; cin >> N >> Q;
    ll ans[Q]; int arr[N+1], v[N+1];
    init(0,131071);
    REP(i,1,N+1) {cin>>arr[i]; vec[i-1]=arr[i];}
    sort(vec,vec+N);
    REP(i,1,N+1) v[i]=lb(vec,arr[i]);
    qry query[Q];
    REP(i,0,Q) {cin>>query[i].l>>query[i].r; query[i].idx=i;}
    sort(query,query+Q,comp);
    REP(i,0,Q) {
        while(l>query[i].l) {l--;update(v[l],vec[v[l]]);}
        while(l<query[i].l) {update(v[l],-vec[v[l]]);l++;}
        while(r>query[i].r) {update(v[r],-vec[v[r]]);r--;}
        while(r<query[i].r) {r++;update(v[r],vec[v[r]]);}
        ans[query[i].idx]=val[1];
    }
    REP(i,0,Q) cout<<ans[i]<<"\n";
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 25 / 25
• Subtask 4: 60 / 60