oj.uz

답안 #13791

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
13791 2015-04-01T10:42:54 Z gs14004 역사적 조사 (JOI14_historical) C++14
15 / 100
 4000 ms 5868 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;
  
ll tree[262144];
  
void add(int val){
    int ind=lower_bound(imp,imp+in,val)-imp;
    ind+=131072+1;
    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+1;
    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=300;
    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
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 5868 KB Output is correct
2 Correct 0 ms 5868 KB Output is correct
3 Correct 0 ms 5868 KB Output is correct
4 Correct 0 ms 5868 KB Output is correct
5 Correct 0 ms 5868 KB Output is correct
6 Correct 0 ms 5868 KB Output is correct
7 Correct 0 ms 5868 KB Output is correct
8 Correct 0 ms 5868 KB Output is correct
9 Correct 0 ms 5868 KB Output is correct
10 Correct 0 ms 5868 KB Output is correct
11 Correct 0 ms 5868 KB Output is correct
12 Correct 0 ms 5868 KB Output is correct
13 Correct 0 ms 5868 KB Output is correct
14 Correct 0 ms 5868 KB Output is correct
15 Correct 0 ms 5868 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 5868 KB Output is correct
2 Correct 4 ms 5868 KB Output is correct
3 Correct 8 ms 5868 KB Output is correct
4 Correct 14 ms 5868 KB Output is correct
5 Correct 39 ms 5868 KB Output is correct
6 Correct 60 ms 5868 KB Output is correct
7 Correct 72 ms 5868 KB Output is correct
8 Correct 53 ms 5868 KB Output is correct
9 Correct 55 ms 5868 KB Output is correct
10 Correct 83 ms 5868 KB Output is correct
11 Correct 80 ms 5868 KB Output is correct
12 Correct 80 ms 5868 KB Output is correct
13 Correct 81 ms 5868 KB Output is correct
14 Correct 80 ms 5868 KB Output is correct
15 Correct 83 ms 5868 KB Output is correct
16 Correct 58 ms 5868 KB Output is correct
17 Correct 54 ms 5868 KB Output is correct
18 Correct 76 ms 5868 KB Output is correct
19 Correct 86 ms 5868 KB Output is correct
20 Correct 88 ms 5868 KB Output is correct

Subtask #3
0.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 5868 KB Output is correct
2 Correct 0 ms 5868 KB Output is correct
3 Correct 0 ms 5868 KB Output is correct
4 Correct 0 ms 5868 KB Output is correct
5 Correct 0 ms 5868 KB Output is correct
6 Correct 2 ms 5868 KB Output is correct
7 Correct 4 ms 5868 KB Output is correct
8 Correct 4 ms 5868 KB Output is correct
9 Correct 13 ms 5868 KB Output is correct
10 Correct 19 ms 5868 KB Output is correct
11 Correct 84 ms 5868 KB Output is correct
12 Correct 47 ms 5868 KB Output is correct
13 Correct 71 ms 5868 KB Output is correct
14 Correct 98 ms 5868 KB Output is correct
15 Correct 148 ms 5868 KB Output is correct
16 Incorrect 90 ms 5868 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 141 ms 5868 KB Output is correct
2 Correct 457 ms 5868 KB Output is correct
3 Correct 983 ms 5868 KB Output is correct
4 Correct 1673 ms 5868 KB Output is correct
5 Correct 2479 ms 5868 KB Output is correct
6 Correct 2953 ms 5868 KB Output is correct
7 Correct 3061 ms 5868 KB Output is correct
8 Correct 2974 ms 5868 KB Output is correct
9 Correct 3331 ms 5868 KB Output is correct
10 Correct 3440 ms 5868 KB Output is correct
11 Correct 3948 ms 5868 KB Output is correct
12 Execution timed out 4000 ms 5864 KB Program timed out
13 Halted 0 ms 0 KB -