oj.uz

Submission #42345

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

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

const int block=300;
data Q[100005];
int n,T,a[100005];
int64_t rs[100005];
map<int,int64_t> Free;
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];
    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[a[r]]>0)
                s.erase(s.find(Free[a[r]]));
            Free[a[r]]+=a[r];
            s.insert(Free[a[r]]);
        }
        while(l>Q[i].l)
        {
            l--;
            if(Free[a[l]]>0)
                s.erase(s.find(Free[a[l]]));
            Free[a[l]]+=a[l];
            s.insert(Free[a[l]]);
        }
        while(r>Q[i].r)
        {
            s.erase(s.find(Free[a[r]]));
            Free[a[r]]-=a[r];
            if(Free[a[r]]>0)
                s.insert(Free[a[r]]);
            r--;
        }
        while(l<Q[i].l)
        {
            s.erase(s.find(Free[a[l]]));
            Free[a[l]]-=a[l];
            if(Free[a[l]]>0)
                s.insert(Free[a[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 248 KB Output is correct
2 Correct 2 ms 352 KB Output is correct
3 Correct 2 ms 424 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 2 ms 532 KB Output is correct
6 Correct 2 ms 548 KB Output is correct
7 Correct 2 ms 548 KB Output is correct
8 Correct 2 ms 552 KB Output is correct
9 Correct 2 ms 552 KB Output is correct
10 Correct 2 ms 552 KB Output is correct
11 Correct 2 ms 600 KB Output is correct
12 Correct 3 ms 604 KB Output is correct
13 Correct 3 ms 604 KB Output is correct
14 Correct 2 ms 604 KB Output is correct
15 Correct 3 ms 604 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 620 KB Output is correct
2 Correct 12 ms 620 KB Output is correct
3 Correct 26 ms 680 KB Output is correct
4 Correct 57 ms 680 KB Output is correct
5 Correct 131 ms 764 KB Output is correct
6 Correct 198 ms 908 KB Output is correct
7 Correct 244 ms 908 KB Output is correct
8 Correct 135 ms 908 KB Output is correct
9 Correct 146 ms 908 KB Output is correct
10 Correct 292 ms 1012 KB Output is correct
11 Correct 293 ms 1012 KB Output is correct
12 Correct 286 ms 1012 KB Output is correct
13 Correct 295 ms 1012 KB Output is correct
14 Correct 295 ms 1012 KB Output is correct
15 Correct 305 ms 1012 KB Output is correct
16 Correct 178 ms 1012 KB Output is correct
17 Correct 53 ms 1012 KB Output is correct
18 Correct 300 ms 1012 KB Output is correct
19 Correct 301 ms 1068 KB Output is correct
20 Correct 293 ms 1068 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1068 KB Output is correct
2 Correct 2 ms 1068 KB Output is correct
3 Correct 2 ms 1068 KB Output is correct
4 Correct 2 ms 1068 KB Output is correct
5 Correct 3 ms 1068 KB Output is correct
6 Correct 4 ms 1068 KB Output is correct
7 Correct 8 ms 1068 KB Output is correct
8 Correct 19 ms 1068 KB Output is correct
9 Correct 35 ms 1324 KB Output is correct
10 Correct 16 ms 1324 KB Output is correct
11 Correct 85 ms 3244 KB Output is correct
12 Correct 100 ms 3244 KB Output is correct
13 Correct 131 ms 3244 KB Output is correct
14 Correct 172 ms 5036 KB Output is correct
15 Correct 186 ms 7656 KB Output is correct
16 Correct 248 ms 11180 KB Output is correct
17 Correct 67 ms 11180 KB Output is correct
18 Correct 110 ms 11180 KB Output is correct
19 Correct 186 ms 11180 KB Output is correct
20 Correct 112 ms 11676 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 411 ms 11676 KB Output is correct
2 Correct 1765 ms 11676 KB Output is correct
3 Execution timed out 4069 ms 11676 KB Time limit exceeded
4 Halted 0 ms 0 KB -