| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 249442 |
2020-07-15T04:11:54 Z |
tqbfjotld |
Cake 3 (JOI19_cake3) |
C++14 |
|
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);
~~~~~^~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
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 |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
