oj.uz

Submission #13780

# Submission time Handle Problem Language Result Execution time Memory
13780 2015-04-01T09:53:00 Z Namnamseo 역사적 조사 (JOI14_historical) C++
0 / 100
 3089 ms 4868 KB 
#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;

int tree[262144];

void add(int val){
    int ind=lower_bound(imp,imp+in,val)-imp;
    ind+=131072;
    tree[ind]+=val;
    ind/=2;
    while(ind) tree[ind]=max(tree[ind*2],tree[ind*2+1]), ind/=2;
}

void rem(int val){
    int ind=lower_bound(imp,imp+in,val)-imp;
    ind+=131072;
    tree[ind]-=val;
    ind/=2;
    while(ind) tree[ind]=max(tree[ind*2],tree[ind*2+1]), ind/=2;
}

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;
    for(i=l;i<=r;++i) add(data[i]);
    ans[query[0].ind]=tree[1];
    for(i=1;i<q;++i){
        while(query[i].l<=l-1) add(data[--l]);
        while(r+1<=query[i].r) add(data[++r]);
        while(l<query[i].l) rem(data[l++]);
        while(query[i].r<r) rem(data[r--]);
        ans[query[i].ind]=tree[1];
    }
    for(i=0;i<q;++i) printf("%lld\n",ans[i]);
    return 0;
}

Subtask #1
0.0 / 5.0

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

Subtask #2
0.0 / 10.0

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

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4868 KB Output is correct
2 Correct 0 ms 4868 KB Output is correct
3 Correct 0 ms 4868 KB Output is correct
4 Correct 1 ms 4868 KB Output is correct
5 Correct 2 ms 4868 KB Output is correct
6 Correct 0 ms 4868 KB Output is correct
7 Correct 5 ms 4868 KB Output is correct
8 Incorrect 8 ms 4868 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 4868 KB Output is correct
2 Correct 488 ms 4868 KB Output is correct
3 Correct 1081 ms 4868 KB Output is correct
4 Correct 1818 ms 4868 KB Output is correct
5 Correct 2647 ms 4868 KB Output is correct
6 Incorrect 3089 ms 4868 KB Output isn't correct
7 Halted 0 ms 0 KB -