oj.uz

답안 #249442

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
249442 2020-07-15T04:11:54 Z tqbfjotld Cake 3 (JOI19_cake3) C++14
5 / 100
 4000 ms 1280 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long

int n,m;
vector<pair<int,int> > cake;

struct node{
    int s,e;
    vector<int> v;
    vector<int> pref;
    node *l,*r;
    node (int _s, int _e){
        //printf("new nd %lld %lld\n",_s,_e);
        s = _s;
        e = _e;
        for (int x = s; x<=e; x++){
            v.push_back(-cake[x].second);
        }
        sort(v.begin(),v.end());
        pref.push_back(v[0]);
        for (int x = 1; x<v.size(); x++){
            pref.push_back(pref[x-1]+v[x]);
        }
        if (s!=e){
            l = new node(s,(s+e)/2);
            r = new node((s+e)/2+1,e);
        }
    }
    int numBigger(int a, int b, int num){ ///number of elements >= num
        //printf("qu %lld %lld %lld\n",a,b,num);
        if (a<=s && e<=b){
            return upper_bound(v.begin(),v.end(),-num)-v.begin();
        }
        if (b<=(s+e)/2) return l->numBigger(a,b,num);
        if (a>(s+e)/2) return r->numBigger(a,b,num);
        return l->numBigger(a,b,num)+r->numBigger(a,b,num);
    }
    int sumBigger(int a, int b, int num){
        if (a<=s && e<=b){
            int t = upper_bound(v.begin(),v.end(),-num)-v.begin()-1;
            return t<=-1?0:-pref[t];
        }
        if (b<=(s+e)/2) return l->sumBigger(a,b,num);
        if (a>(s+e)/2) return r->sumBigger(a,b,num);
        return l->sumBigger(a,b,num)+r->sumBigger(a,b,num);
    }

}*root;

 main(){
    scanf("%lld%lld",&n,&m);
    for (int x = 0; x<n; x++){
        int a,b;
        scanf("%lld%lld",&a,&b);
        cake.push_back({b,a});
    }
    sort(cake.begin(),cake.end());
    root = new node(0,n-1);
    int ans = -999999999999999999LL;
    for (int x = 0; x<n; x++){
        for (int y = x+m-1; y<n; y++){
            ///find m-th largest element in range
            int l = 0;
            int r = 10000000001LL;
            while (l+1<r){
                int mid = (l+r)/2;
                if (root->numBigger(x,y,mid)>=m){
                    l = mid;
                }
                else r = mid;
            }
            //printf("l = %lld\n",l);
            //printf("numbigger x,y,l %lld\n",root->numBigger(x,y,l));
            int opt = root->sumBigger(x,y,l);
            opt -= (root->numBigger(x,y,l)-m)*l;
            opt -= 2*(cake[y].first-cake[x].first);
            //printf("try %lld-%lld, got %lld\n",x,y,opt);
            ans = max(ans,opt);
        }
    }
    printf("%lld",ans);

}

Compilation message

cake3.cpp: In constructor 'node::node(long long int, long long int)':
cake3.cpp:22:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int x = 1; x<v.size(); x++){
                         ~^~~~~~~~~
cake3.cpp: At global scope:
cake3.cpp:51:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  main(){
       ^
cake3.cpp: In function 'int main()':
cake3.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld",&n,&m);
     ~~~~~^~~~~~~~~~~~~~~~~~
cake3.cpp:55:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld%lld",&a,&b);
         ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 384 KB Output is correct
2 Correct 8 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 8 ms 384 KB Output is correct
9 Correct 10 ms 384 KB Output is correct
10 Correct 7 ms 384 KB Output is correct
11 Correct 8 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 6 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 6 ms 512 KB Output is correct
16 Correct 8 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 8 ms 384 KB Output is correct
23 Correct 10 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 6 ms 384 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 9 ms 384 KB Output is correct
29 Correct 7 ms 384 KB Output is correct
30 Correct 12 ms 384 KB Output is correct
31 Correct 4 ms 384 KB Output is correct
32 Correct 6 ms 384 KB Output is correct
33 Correct 5 ms 384 KB Output is correct
34 Correct 4 ms 384 KB Output is correct
35 Correct 8 ms 384 KB Output is correct
36 Correct 13 ms 384 KB Output is correct
37 Correct 0 ms 384 KB Output is correct

Subtask #2
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 384 KB Output is correct
2 Correct 8 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 8 ms 384 KB Output is correct
9 Correct 10 ms 384 KB Output is correct
10 Correct 7 ms 384 KB Output is correct
11 Correct 8 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 6 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 6 ms 512 KB Output is correct
16 Correct 8 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 8 ms 384 KB Output is correct
23 Correct 10 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 6 ms 384 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 9 ms 384 KB Output is correct
29 Correct 7 ms 384 KB Output is correct
30 Correct 12 ms 384 KB Output is correct
31 Correct 4 ms 384 KB Output is correct
32 Correct 6 ms 384 KB Output is correct
33 Correct 5 ms 384 KB Output is correct
34 Correct 4 ms 384 KB Output is correct
35 Correct 8 ms 384 KB Output is correct
36 Correct 13 ms 384 KB Output is correct
37 Correct 0 ms 384 KB Output is correct
38 Execution timed out 4057 ms 1280 KB Time limit exceeded
39 Halted 0 ms 0 KB -

Subtask #3
0 / 76.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 384 KB Output is correct
2 Correct 8 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 8 ms 384 KB Output is correct
9 Correct 10 ms 384 KB Output is correct
10 Correct 7 ms 384 KB Output is correct
11 Correct 8 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 6 ms 384 KB Output is correct
14 Correct 5 ms 384 KB Output is correct
15 Correct 6 ms 512 KB Output is correct
16 Correct 8 ms 384 KB Output is correct
17 Correct 3 ms 384 KB Output is correct
18 Correct 2 ms 384 KB Output is correct
19 Correct 2 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 2 ms 384 KB Output is correct
22 Correct 8 ms 384 KB Output is correct
23 Correct 10 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 6 ms 384 KB Output is correct
26 Correct 5 ms 384 KB Output is correct
27 Correct 5 ms 384 KB Output is correct
28 Correct 9 ms 384 KB Output is correct
29 Correct 7 ms 384 KB Output is correct
30 Correct 12 ms 384 KB Output is correct
31 Correct 4 ms 384 KB Output is correct
32 Correct 6 ms 384 KB Output is correct
33 Correct 5 ms 384 KB Output is correct
34 Correct 4 ms 384 KB Output is correct
35 Correct 8 ms 384 KB Output is correct
36 Correct 13 ms 384 KB Output is correct
37 Correct 0 ms 384 KB Output is correct
38 Execution timed out 4057 ms 1280 KB Time limit exceeded
39 Halted 0 ms 0 KB -