oj.uz

Submission #259331

# Submission time Handle Problem Language Result Execution time Memory
259331 2020-08-07T14:59:17 Z 최은수(#5042) 역사적 조사 (JOI14_historical) C++17
40 / 100
 4000 ms 19880 KB 
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18+7;
const int bk=444;
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,q;
    cin>>n>>q;
    vector<int>v(n),sv;
    for(int&t:v)
        cin>>t,sv.eb(t);
    sort(all(sv));
    sv.erase(unique(all(sv)),sv.end());
    v.insert(v.begin(),v[0]);
    for(int&t:v)
        t=lower_bound(all(sv),t)-sv.begin();
    vector<vector<pair<pi,int> > >qv(500);
    for(int i=0;i<q;i++)
    {
        int s,e;
        cin>>s>>e;
        qv[s/bk].eb(pi(s,e),i);
    }
    vector<ll>ans(q);
    for(auto&qvt:qv)
    {
        if(qvt.empty())
            continue;
        int cl=qvt[0].fi.fi;
        int cr=qvt[0].fi.fi-1;
        vector<ll>cnt((int)sv.size(),0);
        priority_queue<ll>pq,del;
        auto add=[&](int x,int p)->void
        {
            if(cnt[x]!=0)
                del.ep(cnt[x]);
            cnt[x]+=(ll)sv[x]*p;
            if(cnt[x]!=0)
                pq.ep(cnt[x]);
            return;
        };
        pq.ep(0);
        for(auto&t:qvt)
        {
            int l=t.fi.fi;
            int r=t.fi.se;
            while(cl<l)
                add(v[cl++],-1);
            while(cl>l)
                add(v[--cl],1);
            while(cr<r)
                add(v[++cr],1);
            while(cr>r)
                add(v[cr--],-1);
            while(!del.empty()&&pq.top()==del.top())
                pq.pop(),del.pop();
            ans[t.se]=pq.top();
        }
    }
    for(int i=0;i<q;i++)
        cout<<ans[i]<<'\n';
    cout.flush();
    return 0;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 3 ms 640 KB Output is correct
17 Correct 14 ms 1020 KB Output is correct
18 Correct 49 ms 1404 KB Output is correct
19 Correct 172 ms 3640 KB Output is correct
20 Correct 637 ms 3812 KB Output is correct
21 Correct 1536 ms 6176 KB Output is correct
22 Correct 1553 ms 6708 KB Output is correct
23 Correct 1589 ms 2880 KB Output is correct
24 Correct 1537 ms 3876 KB Output is correct
25 Correct 955 ms 18700 KB Output is correct
26 Correct 981 ms 18464 KB Output is correct
27 Correct 1152 ms 19880 KB Output is correct
28 Correct 1028 ms 11120 KB Output is correct
29 Correct 1153 ms 13224 KB Output is correct
30 Correct 1173 ms 11300 KB Output is correct
31 Correct 1553 ms 3824 KB Output is correct
32 Correct 1341 ms 1688 KB Output is correct
33 Correct 1179 ms 10944 KB Output is correct
34 Correct 859 ms 18668 KB Output is correct
35 Correct 716 ms 18524 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 31 ms 1500 KB Output is correct
6 Correct 7 ms 584 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 7 ms 512 KB Output is correct
9 Correct 11 ms 768 KB Output is correct
10 Correct 24 ms 1024 KB Output is correct
11 Correct 2279 ms 6276 KB Output is correct
12 Correct 46 ms 1828 KB Output is correct
13 Correct 228 ms 2468 KB Output is correct
14 Correct 573 ms 3952 KB Output is correct
15 Correct 2151 ms 5264 KB Output is correct
16 Correct 295 ms 4256 KB Output is correct
17 Correct 318 ms 4368 KB Output is correct
18 Correct 311 ms 3628 KB Output is correct
19 Correct 186 ms 4956 KB Output is correct
20 Correct 197 ms 4212 KB Output is correct

Subtask #4
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 3 ms 640 KB Output is correct
17 Correct 14 ms 1020 KB Output is correct
18 Correct 49 ms 1404 KB Output is correct
19 Correct 172 ms 3640 KB Output is correct
20 Correct 637 ms 3812 KB Output is correct
21 Correct 1536 ms 6176 KB Output is correct
22 Correct 1553 ms 6708 KB Output is correct
23 Correct 1589 ms 2880 KB Output is correct
24 Correct 1537 ms 3876 KB Output is correct
25 Correct 955 ms 18700 KB Output is correct
26 Correct 981 ms 18464 KB Output is correct
27 Correct 1152 ms 19880 KB Output is correct
28 Correct 1028 ms 11120 KB Output is correct
29 Correct 1153 ms 13224 KB Output is correct
30 Correct 1173 ms 11300 KB Output is correct
31 Correct 1553 ms 3824 KB Output is correct
32 Correct 1341 ms 1688 KB Output is correct
33 Correct 1179 ms 10944 KB Output is correct
34 Correct 859 ms 18668 KB Output is correct
35 Correct 716 ms 18524 KB Output is correct
36 Correct 1 ms 384 KB Output is correct
37 Correct 1 ms 384 KB Output is correct
38 Correct 2 ms 512 KB Output is correct
39 Correct 3 ms 512 KB Output is correct
40 Correct 31 ms 1500 KB Output is correct
41 Correct 7 ms 584 KB Output is correct
42 Correct 6 ms 512 KB Output is correct
43 Correct 7 ms 512 KB Output is correct
44 Correct 11 ms 768 KB Output is correct
45 Correct 24 ms 1024 KB Output is correct
46 Correct 2279 ms 6276 KB Output is correct
47 Correct 46 ms 1828 KB Output is correct
48 Correct 228 ms 2468 KB Output is correct
49 Correct 573 ms 3952 KB Output is correct
50 Correct 2151 ms 5264 KB Output is correct
51 Correct 295 ms 4256 KB Output is correct
52 Correct 318 ms 4368 KB Output is correct
53 Correct 311 ms 3628 KB Output is correct
54 Correct 186 ms 4956 KB Output is correct
55 Correct 197 ms 4212 KB Output is correct
56 Execution timed out 4080 ms 6172 KB Time limit exceeded
57 Halted 0 ms 0 KB -