oj.uz

Submission #42349

# Submission time Handle Problem Language Result Execution time Memory
42349 2018-02-26T09:33:27 Z dqhungdl 역사적 조사 (JOI14_historical) C++14
40 / 100
 4000 ms 6700 KB 
#include <bits/stdc++.h>
using namespace std;

struct data
{
    int l,r,id;
};

typedef pair<int,int> ii;
const int block=350;
data Q[100005];
int n,T,a[100005],Pre[100005];
int64_t rs[100005],tree[400005];
ii b[100005];

bool cmp(data x1,data x2)
{
    if(x1.l/block==x2.l/block)
        return x1.r<x2.r;
    return x1.l/block<x2.l/block;
}

void Update(int k,int l,int r,int pos,int val)
{
    if(l==r)
    {
        tree[k]+=val;
        return;
    }
    int mid=(l+r)/2;
    if(pos<=mid)
        Update(2*k,l,mid,pos,val);
    else
        Update(2*k+1,mid+1,r,pos,val);
    tree[k]=max(tree[2*k],tree[2*k+1]);
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("TEST.INP","r",stdin);
    cin>>n>>T;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        b[i]=ii(a[i],i);
    }
    sort(b+1,b+n+1);
    Pre[b[1].second]=1;
    int Count=1;
    for(int i=2;i<=n;i++)
        if(b[i].first>b[i-1].first)
            Pre[b[i].second]=++Count;
        else
            Pre[b[i].second]=Count;
    for(int i=1;i<=T;i++)
    {
        cin>>Q[i].l>>Q[i].r;
        Q[i].id=i;
    }
    sort(Q+1,Q+T+1,cmp);
    int l=1,r=0;
    for(int i=1;i<=T;i++)
    {
        while(r<Q[i].r)
        {
            r++;
            Update(1,1,Count,Pre[r],a[r]);
        }
        while(l>Q[i].l)
        {
            l--;
            Update(1,1,Count,Pre[l],a[l]);
        }
        while(r>Q[i].r)
        {
            Update(1,1,Count,Pre[r],-a[r]);
            r--;
        }
        while(l<Q[i].l)
        {
            Update(1,1,Count,Pre[l],-a[l]);
            l++;
        }
        rs[Q[i].id]=tree[1];
    }
    for(int i=1;i<=T;i++)
        cout<<rs[i]<<"\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 552 KB Output is correct
4 Correct 2 ms 552 KB Output is correct
5 Correct 2 ms 552 KB Output is correct
6 Correct 2 ms 552 KB Output is correct
7 Correct 2 ms 584 KB Output is correct
8 Correct 2 ms 584 KB Output is correct
9 Correct 2 ms 604 KB Output is correct
10 Correct 2 ms 604 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 2 ms 620 KB Output is correct
13 Correct 2 ms 620 KB Output is correct
14 Correct 2 ms 620 KB Output is correct
15 Correct 2 ms 708 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 708 KB Output is correct
2 Correct 4 ms 708 KB Output is correct
3 Correct 6 ms 708 KB Output is correct
4 Correct 12 ms 748 KB Output is correct
5 Correct 25 ms 764 KB Output is correct
6 Correct 37 ms 876 KB Output is correct
7 Correct 44 ms 908 KB Output is correct
8 Correct 28 ms 908 KB Output is correct
9 Correct 30 ms 908 KB Output is correct
10 Correct 60 ms 908 KB Output is correct
11 Correct 59 ms 908 KB Output is correct
12 Correct 59 ms 916 KB Output is correct
13 Correct 58 ms 924 KB Output is correct
14 Correct 53 ms 924 KB Output is correct
15 Correct 55 ms 924 KB Output is correct
16 Correct 30 ms 924 KB Output is correct
17 Correct 15 ms 924 KB Output is correct
18 Correct 56 ms 924 KB Output is correct
19 Correct 76 ms 924 KB Output is correct
20 Correct 66 ms 924 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 924 KB Output is correct
2 Correct 2 ms 924 KB Output is correct
3 Correct 1 ms 924 KB Output is correct
4 Correct 2 ms 924 KB Output is correct
5 Correct 2 ms 924 KB Output is correct
6 Correct 3 ms 924 KB Output is correct
7 Correct 5 ms 924 KB Output is correct
8 Correct 7 ms 924 KB Output is correct
9 Correct 14 ms 1180 KB Output is correct
10 Correct 13 ms 1420 KB Output is correct
11 Correct 70 ms 4432 KB Output is correct
12 Correct 47 ms 4432 KB Output is correct
13 Correct 58 ms 4432 KB Output is correct
14 Correct 85 ms 4772 KB Output is correct
15 Correct 109 ms 6228 KB Output is correct
16 Correct 106 ms 6228 KB Output is correct
17 Correct 44 ms 6228 KB Output is correct
18 Correct 73 ms 6228 KB Output is correct
19 Correct 72 ms 6700 KB Output is correct
20 Correct 40 ms 6700 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 6700 KB Output is correct
2 Correct 303 ms 6700 KB Output is correct
3 Correct 706 ms 6700 KB Output is correct
4 Correct 1236 ms 6700 KB Output is correct
5 Correct 1730 ms 6700 KB Output is correct
6 Correct 2004 ms 6700 KB Output is correct
7 Correct 1926 ms 6700 KB Output is correct
8 Correct 1449 ms 6700 KB Output is correct
9 Correct 1053 ms 6700 KB Output is correct
10 Correct 388 ms 6700 KB Output is correct
11 Correct 1474 ms 6700 KB Output is correct
12 Correct 3304 ms 6700 KB Output is correct
13 Execution timed out 4085 ms 6700 KB Time limit exceeded
14 Halted 0 ms 0 KB -