Submission #686745

#	Time	Username	Problem	Language	Result	Execution time	Memory
686745		qweasdzxc	역사적 조사 (JOI14_historical)	C++14	100 / 100	1327 ms	9736 KiB

historic

#include <bits/stdc++.h>
#define fastio                    \
	ios_base::sync_with_stdio(0); \
	cin.tie(0);
#define vi vector<int>
#define vl vector<long long>
#define vc vector<char>
#define vs vector<string>
#define pi pair<int, int>
#define pl pair<ll, ll>
#define vp vector<pi>
#define vpl vector<pl>
#define ll long long
#define MAX 2147000000
#define MOD 1000000007
using namespace std;

struct st{
    int l, r, idx;
};

int n, q;
const int sz = 1e5 + 10;
vector<st> query(sz);
vi A;

vl maxSeg(sz * 4);
vi vec;

void update(ll p, ll val)
{
    for(maxSeg[p+=n]+=val;p>1;p>>=1) maxSeg[p>>1] = max(maxSeg[p], maxSeg[p^1]);
}

void Plus(int k){
    update(k, A[k]);
}

void Minus(int k){
    update(k, -A[k]);
}


int main() {
	fastio;	
    cin >> n >> q;
    vec.resize(n);
    for(int i{0}; i < n; ++i){
        cin >> vec[i];
    }
    A = vec;
    sort(A.begin(), A.end());
    A.erase(unique(A.begin(), A.end()), A.end());
    for(int i{0}; i < n; ++i){
        vec[i] = lower_bound(A.begin(), A.end(), vec[i]) - A.begin();
    }
    for(int i{0}; i < q; ++i){
        cin >> query[i].l >> query[i].r;
        query[i].l--; query[i].r--;
        query[i].idx = i;
    }
    int sq = sqrt(n);
    sort(query.begin(), query.begin() + q, [&](st& a, st& b){
        if(a.l / sq == b.l / sq) return a.r < b.r;
        else return a.l / sq < b.l / sq;
    });
    int l = query[0].l;
    int r = query[0].r;
    vl ans(q);
    for(int i{l}; i <= r; ++i){
        Plus(vec[i]);
    }
    ans[query[0].idx] = maxSeg[1];
    for(int i{1}; i < q; ++i){
        while(l > query[i].l) Plus(vec[--l]);
        while(r < query[i].r) Plus(vec[++r]);
        while(l < query[i].l) Minus(vec[l++]);        
        while(r > query[i].r) Minus(vec[r--]);
        ans[query[i].idx] = maxSeg[1];
    }
    for(auto& i : ans) cout << i << "\n";
}
	

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