Submission #259029

#	Time	Username	Problem	Language	Result	Execution time	Memory
259029		Namnamseo	역사적 조사 (JOI14_historical)	C++17	100 / 100	3541 ms	7660 KiB

historic

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

using namespace std;

typedef long long ll;
int sqrtN;

struct Query{
    int l, r, idx;
    Query(){}
    Query(int l, int r, int idx): l(l), r(r), idx(idx){}

    bool operator<(const Query &tmp)const{
        if(l/sqrtN != tmp.l/sqrtN) return l < tmp.l;
        return r < tmp.r;
    }
};

int n, q, k;
ll arr[100002];
vector<Query> vec;
ll cnt[100002];
ll ans[100002];
vector<ll> v;

ll tree[400002];
inline void update(int i, ll val){
    tree[i+=131072] += val;
    for(i/=2; i; i/=2) {
        tree[i] = max(tree[i*2], tree[i*2+1]);
    }
}

inline void removeNum(ll x){
    update(x, -v[x]);
}
inline void addNum(ll x){
    update(x, v[x]);
}

void renumber(){
    for(int i=0; i<n; i++) v.push_back(arr[i]);
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for(int i=0; i<n; i++) arr[i] = lower_bound(v.begin(), v.end(), arr[i]) - v.begin();
    k = (int)v.size();
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> q;
    sqrtN = ceil(sqrt(n));
    for(int i=0; i<n; i++) cin >> arr[i];
    renumber();
    for(int i=1; i<=q; i++){
        int l, r;
        cin >> l >> r;
        l--, r--;
        vec.push_back(Query(l, r, i));
    }
    sort(vec.begin(), vec.end());

    int s = 0, e = -1;
    for(int i=0; i<q; i++){
        Query tmp = vec[i];
        int l = tmp.l, r = tmp.r, idx = tmp.idx;
        while(e < r) addNum(arr[++e]);
        while(s > l) addNum(arr[--s]);
        while(e > r) removeNum(arr[e--]);
        while(s < l) removeNum(arr[s++]);
        ans[idx] = tree[1];
    }

    for(int i=1; i<=q; i++){
        cout << ans[i] << '\n';
    }
}

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