Submission #13783

#	Time	Username	Problem	Language	Result	Execution time	Memory
13783		Namnamseo	역사적 조사 (JOI14_historical)	C++98	15 / 100	4000 ms	5892 KiB

historic

#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

int imp[100010];
typedef long long ll;
ll  ans[100010];
int in;
int data[100010];
int bck;

struct qr{int ind,l,r; bool operator<(const qr& other) const { return l/bck==other.l/bck?r<other.r:l<other.l; }; } query[100010];

int n,q;

ll tree[262144];

int main()
{
    scanf("%d%d",&n,&q); int i; for(i=1;i<=n;++i) scanf("%d",data+i),imp[i]=data[i];
    bck=n/sqrt(q);
    sort(imp,imp+n);in=unique(imp,imp+n)-imp;
    int a,b;
    for(i=0;i<q;++i) scanf("%d%d",&a,&b),query[i].ind=i,query[i].l=a,query[i].r=b;
    sort(query,query+q);
    int l=query[0].l, r=query[0].r;
    int tmp,ind;
    for(i=l;i<=r;++i) {
        tmp=data[i];
        ind=lower_bound(imp,imp+in,tmp)-imp;
        ind+=131072;
        tree[ind]+=tmp;
        ind/=2;
        while(ind) tree[ind]=max(tree[ind*2],tree[ind*2+1]), ind/=2;
    }
    ans[query[0].ind]=tree[1];
    int ql,qr;
    for(i=1;i<q;++i){
        ql=query[i].l; qr=query[i].r;
        while(ql<=l-1) {
            tmp=data[--l];
            ind=lower_bound(imp,imp+in,tmp)-imp;
            ind+=131072;
            tree[ind]+=tmp;
            ind/=2;
            while(ind) tree[ind]=max(tree[ind*2],tree[ind*2+1]), ind/=2;
        }
        while(r+1<=qr) {
            tmp=data[++r];
            ind=lower_bound(imp,imp+in,tmp)-imp;
            ind+=131072;
            tree[ind]+=tmp;
            ind/=2;
            while(ind) tree[ind]=max(tree[ind*2],tree[ind*2+1]), ind/=2;
        }
        while(l<ql) {
            tmp=data[l++];
            ind=lower_bound(imp,imp+in,tmp)-imp;
            ind+=131072;
            tree[ind]-=tmp;
            ind/=2;
            while(ind) tree[ind]=max(tree[ind*2],tree[ind*2+1]), ind/=2;
        }
        while(qr<r) {
            tmp=data[r--];
            ind=lower_bound(imp,imp+in,tmp)-imp;
            ind+=131072;
            tree[ind]-=tmp;
            ind/=2;
            while(ind) tree[ind]=max(tree[ind*2],tree[ind*2+1]), ind/=2;
        }
        ans[query[i].ind]=tree[1];
    }
    for(i=0;i<q;++i) printf("%lld\n",ans[i]);
    return 0;
}

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