이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
using namespace std;
using ll = long long;
const int MAXN = 2e5+5, base = (1<<18);
int n, m;
ll X, w, t;
ll s[MAXN];
vector<pair<ll, ll>> arr;
ll suf[MAXN];
struct Point {
ll x, y;
Point() {}
Point(ll _x, ll _y) {
x = _x, y = _y;
}
bool operator<(const Point& other) const {
return mp(x, y) < mp(other.x, other.y);
}
};
ll f(Point pt, ll x) {
return pt.x * x + pt.y;
}
Point tree[2*base+1];
map<Point, bool> M;
void ins_line(Point line, int id, int rl, int rr) {
int rm = (rl+rr)/2;
bool check_l = f(line, rl) < f(tree[id], rl);
bool check_m = f(line, rm) < f(tree[id], rm);
if(check_m) {
swap(tree[id], line);
}
if(rl==rr) return;
if(check_l == check_m) {
ins_line(line, id*2+1, rm+1, rr);
}
else {
ins_line(line, id*2, rl, rm);
}
}
ll get(int x, int id, int rl, int rr) {
int rm = (rl+rr)/2;
if(rl==rr) {
return f(tree[id], x);
}
if(x <= rm) {
return min(f(tree[id], x), get(x, id*2, rl, rm));
}
return min(f(tree[id], x), get(x, id*2+1, rm+1, rr));
}
bool cmp(ll item1, ll item2) {
return item1%t < item2%t;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>X>>n>>m>>w>>t;
for(int i=1; i<2*base; ++i) {
tree[i] = Point(1e18/m, 1e18);
}
for(int i=0; i<n; ++i) {
cin>>s[i];
}
s[n] = X;
sort(s, s+n+1, cmp);
arr.resize(m);
for(int i=0; i<m; ++i) {
cin>>arr[i].st>>arr[i].nd;
}
sort(arr.begin(), arr.end());
ll sum_c=0;
int j = n;
for(int i=m-1; i>=0; --i) {
while(j>=0 && s[j]%t > arr[i].st) {
Point line = Point(-(s[j]/t)*w, (s[j]/t)*w*(i+1) - sum_c + suf[i+1]);
if(!M[line]) {
ins_line(line, 1, 0, m-1);
M[line] = 1;
}
//cerr<<' '<<line.x<<' '<<line.y<<" "<<f(line, i)<<'\n';
j--;
}
sum_c += arr[i].nd;
suf[i] = suf[i+1] + ((X-arr[i].st)/t+1) * w;
suf[i] = min(suf[i], sum_c + get(i, 1, 0, m-1));
//cerr<<i<<": "<<suf[i]<<" "<<suf[i+1] + ((X-arr[i].st)/t+1) * w<<' '<<get(i, 1, 0, m-1)<<'\n';
}
cout<<suf[0] + w * (X/t+1)<<'\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |