oj.uz

Submission #42347

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

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

typedef pair<int,int> ii;
const int block=300;
data Q[100005];
int n,T,a[100005],Pre[100005];
int64_t rs[100005],Free[100005];
ii b[100005];
multiset<int64_t> s;

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;
}

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++;
            if(Free[Pre[r]]>0)
                s.erase(s.find(Free[Pre[r]]));
            Free[Pre[r]]+=a[r];
            s.insert(Free[Pre[r]]);
        }
        while(l>Q[i].l)
        {
            l--;
            if(Free[Pre[l]]>0)
                s.erase(s.find(Free[Pre[l]]));
            Free[Pre[l]]+=a[l];
            s.insert(Free[Pre[l]]);
        }
        while(r>Q[i].r)
        {
            s.erase(s.find(Free[Pre[r]]));
            Free[Pre[r]]-=a[r];
            if(Free[Pre[r]]>0)
                s.insert(Free[Pre[r]]);
            r--;
        }
        while(l<Q[i].l)
        {
            s.erase(s.find(Free[Pre[l]]));
            Free[Pre[l]]-=a[l];
            if(Free[Pre[l]]>0)
                s.insert(Free[Pre[l]]);
            l++;
        }
        rs[Q[i].id]=*s.rbegin();
    }
    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 1 ms 480 KB Output is correct
3 Correct 2 ms 480 KB Output is correct
4 Correct 2 ms 480 KB Output is correct
5 Correct 2 ms 480 KB Output is correct
6 Correct 2 ms 540 KB Output is correct
7 Correct 2 ms 540 KB Output is correct
8 Correct 2 ms 540 KB Output is correct
9 Correct 2 ms 560 KB Output is correct
10 Correct 2 ms 688 KB Output is correct
11 Correct 2 ms 688 KB Output is correct
12 Correct 2 ms 688 KB Output is correct
13 Correct 2 ms 688 KB Output is correct
14 Correct 2 ms 688 KB Output is correct
15 Correct 2 ms 688 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 688 KB Output is correct
2 Correct 7 ms 688 KB Output is correct
3 Correct 14 ms 688 KB Output is correct
4 Correct 30 ms 748 KB Output is correct
5 Correct 70 ms 792 KB Output is correct
6 Correct 105 ms 912 KB Output is correct
7 Correct 111 ms 912 KB Output is correct
8 Correct 86 ms 912 KB Output is correct
9 Correct 88 ms 912 KB Output is correct
10 Correct 110 ms 924 KB Output is correct
11 Correct 108 ms 928 KB Output is correct
12 Correct 114 ms 1068 KB Output is correct
13 Correct 125 ms 1068 KB Output is correct
14 Correct 118 ms 1068 KB Output is correct
15 Correct 114 ms 1068 KB Output is correct
16 Correct 96 ms 1068 KB Output is correct
17 Correct 41 ms 1068 KB Output is correct
18 Correct 115 ms 1072 KB Output is correct
19 Correct 108 ms 1072 KB Output is correct
20 Correct 103 ms 1072 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1072 KB Output is correct
2 Correct 1 ms 1072 KB Output is correct
3 Correct 1 ms 1072 KB Output is correct
4 Correct 2 ms 1072 KB Output is correct
5 Correct 2 ms 1072 KB Output is correct
6 Correct 3 ms 1072 KB Output is correct
7 Correct 4 ms 1072 KB Output is correct
8 Correct 9 ms 1072 KB Output is correct
9 Correct 16 ms 1196 KB Output is correct
10 Correct 16 ms 1452 KB Output is correct
11 Correct 83 ms 4444 KB Output is correct
12 Correct 65 ms 4444 KB Output is correct
13 Correct 61 ms 4444 KB Output is correct
14 Correct 72 ms 4444 KB Output is correct
15 Correct 78 ms 5548 KB Output is correct
16 Correct 106 ms 6828 KB Output is correct
17 Correct 55 ms 6828 KB Output is correct
18 Correct 82 ms 6828 KB Output is correct
19 Correct 68 ms 6828 KB Output is correct
20 Correct 59 ms 7340 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 7340 KB Output is correct
2 Correct 767 ms 7340 KB Output is correct
3 Correct 1668 ms 7340 KB Output is correct
4 Correct 3206 ms 7340 KB Output is correct
5 Execution timed out 4016 ms 7340 KB Time limit exceeded
6 Halted 0 ms 0 KB -