이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define read() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define day() time_t now = time(0);char* x = ctime(&now);cerr<<"Right Now Is : "<<x<<"\n"
#define int long long
#define ii pair<int,int>
#define X first
#define Y second
const long long MAX = (int)2e5 + 5;
const long long INF = (int)1e18;
const long long MOD = (int)1e9 + 7;
int n,m;
struct node{
int v,c;
};
node a[MAX];
int s = 0;
ii st[MAX << 2];
vector<int> rt;
int siz = 0;
int res = 0;
int L = 1,R = 1;
ii operator + (const ii &a,const ii &b){
return {a.X + b.X,a.Y + b.Y};
}
void update(int u,int val,int id = 1,int l = 1,int r = siz){
if(l == r){
//cout << u << " " << val << " : ";
//cout << st[id].X << "," << st[id].Y << " ";
st[id].X += val;
st[id].Y += val * rt[l - 1];
//cout << st[id].X << "," << st[id].Y << "\n";
return;
}
int m = l + r >> 1;
if(u <= m)update(u,val,id << 1,l,m);
else update(u,val,id << 1 | 1,m + 1,r);
st[id] = st[id << 1] + st[id << 1 | 1];
}
bool ok = 0;
int get(int val,int id = 1,int l = 1,int r = siz){
//if(ok)cout << val << " " << id << " " << l << " " << r << " " << st[id].X << " " << st[id].Y << '\n';
if(val == 0)return 0;
if(st[id].X <= val)return st[id].Y;
if(l == r){
int sum = st[id].Y;
if(st[id].X > val)sum -= (st[id].X - val) * rt[l - 1];
return sum;
}
int m = l + r >> 1;
if(st[id << 1 | 1].X > val)return get(val,id << 1 | 1,m + 1,r);
return st[id << 1 | 1].Y + get(val - st[id << 1 | 1].X,id << 1,l,m);
}
void add(int id){
update(a[id].v,1);
}
void del(int id){
update(a[id].v,-1);
}
int cost(int l,int r){
while(L > l)add(--L);
while(R < r)add(++R);
while(L < l)del(L++);
while(R > r)del(R--);
//if(ok)cout << l << " " << r << " : \n";
return get(m);
}
void solve(int l,int r,int u,int v){
//cout << l << " " << r << " " << u << " " << v << '\n';
if(l > r)return;
int mid = l + r >> 1;
ii best = {-INF,-1};
for(int i = max(u,mid);i <= v;i++){
int cnt = (a[i].c - a[mid].c) * 2;
if(i - mid + 1 < m)continue;
if(mid == 2 && i == 4)ok = 1;
best = max(best,{cost(mid,i) - cnt,i});
ok = 0;
}
//cout << "---- " << mid << " " << best.X << " " << best.Y << " " << v << "\n";
if(best.Y == -1){
solve(l,mid - 1,u,v);
return;
}
res = max(res,best.X);
solve(l,mid - 1,u,best.Y);
solve(mid + 1,r,best.Y,v);
}
signed main(){
read();
cin >> n >> m;
for(int i = 1;i <= n;i++){
cin >> a[i].v >> a[i].c;
rt.push_back(a[i].v);
}
sort(rt.begin(),rt.end());
rt.erase(unique(rt.begin(),rt.end()),rt.end());
siz = rt.size();
sort(a + 1,a + 1 + n,[&](const node &a,const node &b){
return a.c < b.c;
});
for(int i = 1;i <= n;i++){
a[i].v = lower_bound(rt.begin(),rt.end(),a[i].v) - rt.begin() + 1;
}
//cout << "\n";
add(1);
solve(1,n,1,n);
cout << res;
}
컴파일 시 표준 에러 (stderr) 메시지
cake3.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int)':
cake3.cpp:45:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
45 | int m = l + r >> 1;
| ~~^~~
cake3.cpp: In function 'long long int get(long long int, long long int, long long int, long long int)':
cake3.cpp:60:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
60 | int m = l + r >> 1;
| ~~^~~
cake3.cpp: In function 'void solve(long long int, long long int, long long int, long long int)':
cake3.cpp:83:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
83 | int mid = l + r >> 1;
| ~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |