oj.uz

Submission #18648

# Submission time Handle Problem Language Result Execution time Memory
18648 2016-02-13T09:46:55 Z mindol 역사적 조사 (JOI14_historical) C++14
100 / 100
 3156 ms 6768 KB 
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> cpr;
int a[100001];
struct Query{ int s,e,index; long long ans; } d[100001];
int sq=316;
bool comp_sqd(Query a,Query b)
{
    if(a.s/sq==b.s/sq) return a.e<b.e;
    else return a.s<b.s;
}
bool comp_ind(Query a,Query b){ return a.index<b.index; }
long long tree[1<<18]; int base=1<<17;
void add(int place,int value)
{
    place+=base-1;
    tree[place]+=value;
    for(place>>=1;place>=1;place>>=1)
        tree[place]=max(tree[place*2],tree[place*2+1]);
}
int main()
{
    int n,q;
    scanf("%d %d",&n,&q);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]), cpr.push_back(a[i]);
    sort(cpr.begin(),cpr.end());
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(cpr.begin(),cpr.end(),a[i])-cpr.begin()+1;
    for(int i=1;i<=q;i++)
        scanf("%d %d",&d[i].s,&d[i].e),d[i].index=i;
    sort(d+1,d+1+q,comp_sqd);
    int s=1,e=0; // [s,e]
    for(int i=1;i<=q;i++)
    {
        while(e<d[i].e)
        {
            e++;
            add(a[e],cpr[a[e]-1]);
        }
        while(e>d[i].e)
        {
            add(a[e],-cpr[a[e]-1]);
            e--;
        }
        while(s>d[i].s)
        {
            s--;
            add(a[s],cpr[a[s]-1]);
        }
        while(s<d[i].s)
        {
            add(a[s],-cpr[a[s]-1]);
            s++;
        }
        d[i].ans=tree[1];
    }
    sort(d+1,d+1+q,comp_ind);
    for(int i=1;i<=q;i++)
        printf("%lld\n",d[i].ans);
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5996 KB Output is correct
2 Correct 0 ms 5996 KB Output is correct
3 Correct 0 ms 5996 KB Output is correct
4 Correct 0 ms 5996 KB Output is correct
5 Correct 0 ms 5996 KB Output is correct
6 Correct 0 ms 5996 KB Output is correct
7 Correct 0 ms 5996 KB Output is correct
8 Correct 0 ms 5996 KB Output is correct
9 Correct 1 ms 5996 KB Output is correct
10 Correct 0 ms 5996 KB Output is correct
11 Correct 0 ms 5996 KB Output is correct
12 Correct 0 ms 5996 KB Output is correct
13 Correct 0 ms 5996 KB Output is correct
14 Correct 0 ms 5996 KB Output is correct
15 Correct 0 ms 5996 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 5996 KB Output is correct
2 Correct 3 ms 5996 KB Output is correct
3 Correct 3 ms 5996 KB Output is correct
4 Correct 11 ms 5996 KB Output is correct
5 Correct 24 ms 5996 KB Output is correct
6 Correct 36 ms 5996 KB Output is correct
7 Correct 39 ms 5996 KB Output is correct
8 Correct 39 ms 5996 KB Output is correct
9 Correct 39 ms 5996 KB Output is correct
10 Correct 39 ms 5996 KB Output is correct
11 Correct 41 ms 5996 KB Output is correct
12 Correct 37 ms 5996 KB Output is correct
13 Correct 40 ms 5996 KB Output is correct
14 Correct 37 ms 5996 KB Output is correct
15 Correct 40 ms 5996 KB Output is correct
16 Correct 40 ms 5996 KB Output is correct
17 Correct 41 ms 5996 KB Output is correct
18 Correct 40 ms 5996 KB Output is correct
19 Correct 40 ms 5996 KB Output is correct
20 Correct 37 ms 5996 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 5996 KB Output is correct
2 Correct 0 ms 5996 KB Output is correct
3 Correct 0 ms 5996 KB Output is correct
4 Correct 0 ms 5996 KB Output is correct
5 Correct 2 ms 5996 KB Output is correct
6 Correct 2 ms 5996 KB Output is correct
7 Correct 0 ms 5996 KB Output is correct
8 Correct 7 ms 5996 KB Output is correct
9 Correct 14 ms 6128 KB Output is correct
10 Correct 7 ms 6384 KB Output is correct
11 Correct 114 ms 6768 KB Output is correct
12 Correct 52 ms 6768 KB Output is correct
13 Correct 65 ms 6768 KB Output is correct
14 Correct 101 ms 6768 KB Output is correct
15 Correct 170 ms 6768 KB Output is correct
16 Correct 86 ms 6768 KB Output is correct
17 Correct 57 ms 6768 KB Output is correct
18 Correct 91 ms 6768 KB Output is correct
19 Correct 105 ms 6768 KB Output is correct
20 Correct 59 ms 6768 KB Output is correct

Subtask #4
60.0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 5996 KB Output is correct
2 Correct 225 ms 6128 KB Output is correct
3 Correct 423 ms 6128 KB Output is correct
4 Correct 675 ms 6384 KB Output is correct
5 Correct 968 ms 6384 KB Output is correct
6 Correct 1286 ms 6384 KB Output is correct
7 Correct 1508 ms 6768 KB Output is correct
8 Correct 1694 ms 6768 KB Output is correct
9 Correct 2074 ms 6768 KB Output is correct
10 Correct 2981 ms 6768 KB Output is correct
11 Correct 2421 ms 6768 KB Output is correct
12 Correct 2687 ms 6768 KB Output is correct
13 Correct 3121 ms 6768 KB Output is correct
14 Correct 3093 ms 6768 KB Output is correct
15 Correct 3134 ms 6768 KB Output is correct
16 Correct 3146 ms 6768 KB Output is correct
17 Correct 3145 ms 6768 KB Output is correct
18 Correct 3156 ms 6768 KB Output is correct
19 Correct 3152 ms 6768 KB Output is correct
20 Correct 3144 ms 6768 KB Output is correct
21 Correct 3156 ms 6768 KB Output is correct
22 Correct 3137 ms 6768 KB Output is correct
23 Correct 3137 ms 6768 KB Output is correct
24 Correct 3116 ms 6768 KB Output is correct
25 Correct 2989 ms 6768 KB Output is correct