oj.uz

Submission #42352

# Submission time Handle Problem Language Result Execution time Memory
42352 2018-02-26T11:33:59 Z dqhungdl 역사적 조사 (JOI14_historical) C++14
5 / 100
 4 ms 1068 KB 
#include <bits/stdc++.h>
using namespace std;

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

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

bool cmp(data x1,data x2)
{
    return x1.r<x2.r;
}

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 l,r,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>>l>>r;
        Q[(l-1)/block+1].push_back({l,r,i});
    }
    for(int i=1;i<=(n-1)/block+1;i++)
    {
        sort(Q[i].begin(),Q[i].end(),cmp);
        for(int j=1;j<=Count;j++)
            Free[j]=0;
        int tmp=i*block+1;
        int64_t res=0;
        for(int j=0;j<Q[i].size();j++)
        {
            int l=Q[i][j].l;
            int r=Q[i][j].r;
            int id=Q[i][j].id;
            if(r<=i*block)
            {
                for(int t=l;t<=r;t++)
                {
                    Free[Pre[t]]+=a[t];
                    rs[id]=max(rs[id],Free[Pre[t]]);
                }
                for(int t=l;t<=r;t++)
                    Free[Pre[t]]-=a[t];
            }
            else
            {
                while(tmp<=r)
                {
                    Free[Pre[tmp]]+=a[tmp];
                    res=max(res,Free[Pre[tmp]]);
                    tmp++;
                }
                rs[id]=res;
                for(int t=l;t<=i*block;t++)
                {
                    Free[Pre[t]]+=a[t];
                    rs[id]=max(rs[id],Free[Pre[t]]);
                }
                for(int t=l;t<=i*block;t++)
                    Free[Pre[t]]-=a[t];
            }
        }
    }
    for(int i=1;i<=T;i++)
        cout<<rs[i]<<"\n";
}

Compilation message

historic.cpp: In function 'int main()':
historic.cpp:51:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j=0;j<Q[i].size();j++)
                      ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 376 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 2 ms 556 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 1 ms 588 KB Output is correct
6 Correct 2 ms 588 KB Output is correct
7 Correct 2 ms 588 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 616 KB Output is correct
12 Correct 1 ms 700 KB Output is correct
13 Correct 1 ms 700 KB Output is correct
14 Correct 1 ms 700 KB Output is correct
15 Correct 2 ms 700 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 700 KB Output is correct
2 Correct 2 ms 700 KB Output is correct
3 Runtime error 2 ms 876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 876 KB Output is correct
2 Correct 1 ms 876 KB Output is correct
3 Correct 1 ms 876 KB Output is correct
4 Runtime error 2 ms 876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 1068 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -