oj.uz

Submission #24876

# Submission time Handle Problem Language Result Execution time Memory
24876 2017-06-16T15:00:28 Z evenharder 역사적 조사 (JOI14_historical) C++11
40 / 100
 4000 ms 10528 KB 
#include <cstdio>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <utility>
#include <cmath>
#include <functional>

struct query{
    int l,r,n;
    long long int ans;
    query(int l=0, int r=0, int n=0) : l(l), r(r), n(n) {ans=0LL;}
};

std::multiset<long long int, std::greater<long long int> > s;
std::vector<query> vq;
const int MAX_N=100000;
int x[MAX_N+1];
int n,q;
int root[MAX_N+1];
long long int cnt[MAX_N+1];
void setRoot()
{
    std::map<int, int> m;
    for(int i=1;i<=n;i++)
    {
        if(m[x[i]]==0)
        {
            root[i]=i;
            m[x[i]]=i;
        }
        else root[i]=m[x[i]];
    }
}
void calc()
{
    int sq=(int)(ceil(sqrt(n+1)));
    std::sort(vq.begin(), vq.end(), [&] (query A, query B) {
        return A.l/sq == B.l/sq ? A.r < B.r : A.l < B.l;
    });

    int l=1;
    int r=0;
    for(int i=0;i<n;i++) s.insert(0);

    for(int i=0;i<q;i++)
    {
        while(r<vq[i].r)
        {
            r++;
            long long int prev = cnt[root[r]] * x[r];
            auto it = s.find(prev);
            s.erase(it);
            cnt[root[r]]++;
            s.insert(prev+x[r]);
        }
        while(r>vq[i].r)
        {
            long long int prev = cnt[root[r]] * x[r];
            auto it = s.find(prev);
            s.erase(it);
            cnt[root[r]]--;
            s.insert(prev-x[r]);
            r--;
        }
        while(l<vq[i].l)
        {
            long long int prev = cnt[root[l]] * x[l];
            auto it = s.find(prev);
            s.erase(it);
            cnt[root[l]]--;
            s.insert(prev-x[l]);
            l++;
        }
        while(l>vq[i].l)
        {
            l--;
            long long int prev = cnt[root[l]] * x[l];
            auto it = s.find(prev);
            s.erase(it);
            cnt[root[l]]++;
            s.insert(prev+x[l]);
        }
        vq[i].ans=*s.begin();
    }

    std::sort(vq.begin(), vq.end(), [&] (query A, query B) {
        return A.n < B.n;
    });

    for(int i=0;i<q;i++) printf("%lld\n", vq[i].ans);
}
int main()
{

    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x[i]);
    }
    for(int i=0;i<q;i++)
    {
        static int l,r;
        scanf("%d%d",&l,&r);
        vq.push_back(query(l,r,i));
    }
    setRoot();
    calc();
}

Compilation message

historic.cpp: In function 'int main()':
historic.cpp:97:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&q);
                        ^
historic.cpp:100:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&x[i]);
                          ^
historic.cpp:105:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&l,&r);
                            ^

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2756 KB Output is correct
2 Correct 3 ms 2756 KB Output is correct
3 Correct 6 ms 2888 KB Output is correct
4 Correct 16 ms 2928 KB Output is correct
5 Correct 53 ms 3060 KB Output is correct
6 Correct 109 ms 3160 KB Output is correct
7 Correct 116 ms 3160 KB Output is correct
8 Correct 93 ms 3160 KB Output is correct
9 Correct 93 ms 3160 KB Output is correct
10 Correct 143 ms 3160 KB Output is correct
11 Correct 136 ms 3160 KB Output is correct
12 Correct 139 ms 3160 KB Output is correct
13 Correct 133 ms 3160 KB Output is correct
14 Correct 143 ms 3160 KB Output is correct
15 Correct 149 ms 3160 KB Output is correct
16 Correct 96 ms 3160 KB Output is correct
17 Correct 49 ms 3160 KB Output is correct
18 Correct 153 ms 3160 KB Output is correct
19 Correct 143 ms 3160 KB Output is correct
20 Correct 149 ms 3160 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2756 KB Output is correct
2 Correct 0 ms 2756 KB Output is correct
3 Correct 0 ms 2756 KB Output is correct
4 Correct 0 ms 2756 KB Output is correct
5 Correct 0 ms 2888 KB Output is correct
6 Correct 3 ms 2888 KB Output is correct
7 Correct 6 ms 3020 KB Output is correct
8 Correct 13 ms 3416 KB Output is correct
9 Correct 33 ms 3944 KB Output is correct
10 Correct 46 ms 5132 KB Output is correct
11 Correct 179 ms 10528 KB Output is correct
12 Correct 126 ms 7508 KB Output is correct
13 Correct 146 ms 8224 KB Output is correct
14 Correct 236 ms 8992 KB Output is correct
15 Correct 283 ms 10528 KB Output is correct
16 Correct 206 ms 8992 KB Output is correct
17 Correct 113 ms 8224 KB Output is correct
18 Correct 173 ms 10528 KB Output is correct
19 Correct 206 ms 10528 KB Output is correct
20 Correct 153 ms 8224 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 296 ms 3616 KB Output is correct
2 Correct 1109 ms 4528 KB Output is correct
3 Correct 3079 ms 4924 KB Output is correct
4 Execution timed out 4000 ms 6220 KB Execution timed out
5 Halted 0 ms 0 KB -