This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
using namespace std;
const ll maxn = 500005;
const ll INF = 100000000000000000;
ll tree[maxn*4], tree2[maxn*4];
ll lazy[maxn*4], lazy2[maxn*4];
ll calc(ll k){
return tree[k] + lazy[k];
}
void push(ll k){
lazy[k*2] += lazy[k];
lazy[k*2+1] += lazy[k];
tree[k] += lazy[k];
lazy[k] = 0;
}
void update(ll a, ll b, ll val, ll k=1, ll x=0, ll y=maxn-1){
if (b<x || a>y) return;
if (a<=x && y<=b){
lazy[k] += val;
return;
}
ll mid = (x+y)/2;
push(k);
update(a,b,val,k*2,x,mid);
update(a,b,val,k*2+1,mid+1,y);
tree[k] = min(calc(k*2), calc(k*2+1));
}
ll query(ll a, ll b, ll k=1, ll x = 0, ll y =maxn-1){
if (b<x || a>y) return INF;
if (a<=x && y<=b){
return calc(k);
}
ll mid = (x+y)/2;
push(k);
return min(query(a, b, k*2, x, mid), query(a,b,k*2+1, mid+1, y));
}
ll calc2(ll k){
return tree2[k] + lazy2[k];
}
void push2(ll k){
lazy2[k*2] += lazy2[k];
lazy2[k*2+1] += lazy2[k];
tree2[k] += lazy2[k];
lazy2[k] = 0;
}
void update2(ll a, ll b, ll val, ll k=1, ll x=0, ll y=maxn-1){
if (b<x || a>y) return;
if (a<=x && y<=b){
lazy2[k] += val;
return;
}
ll mid = (x+y)/2;
push2(k);
update2(a,b,val,k*2,x,mid);
update2(a,b,val,k*2+1,mid+1,y);
tree2[k] = min(calc2(k*2), calc2(k*2+1));
}
ll query2(ll a, ll b, ll k=1, ll x = 0, ll y =maxn-1){
if (b<x || a>y) return INF;
if (a<=x && y<=b){
return calc2(k);
}
push2(k);
ll mid = (x+y)/2;
return min(query2(a, b, k*2, x, mid), query2(a,b,k*2+1, mid+1, y));
}
ll a,b,t, n, l;
ll arr[2005];
ll cache[2005][2005][2][2];
ll dp(ll x, ll y, ll pos, ll req){
if (cache[x][y][pos][req] != -1) return cache[x][y][pos][req];
if (x==0 && y==n-1){
if (pos==req) return 0;
else return 100000000000000000;
}
if (pos == 0){
ll idk=INF, idk2 = INF;
if (y<(n-1))idk = dp(x,y+1,1,req) + abs(arr[x]-arr[y+1])*(n-(y-x));
if (x>0) idk2 = dp(x-1,y,0,req) + abs(arr[x]-arr[x-1])*(n-(y-x));
return cache[x][y][pos][req]=min(idk, idk2);
}
else if (pos == 1){
ll idk=INF, idk2 = INF;
if(x>0) idk = dp(x-1,y,0,req) + abs(arr[y]-arr[x-1])*(n-(y-x));
if (y<(n-1)) idk2 = dp(x, y+1, 1,req) + abs(arr[y]-arr[y+1]) * (n-(y-x));
return cache[x][y][pos][req]=min(idk, idk2);
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
FOR(i,0,maxn*4) tree[i] = 0, lazy[i] = 0, tree2[i] = 0, lazy2[i] = 0;
FOR(i,0,2005) FOR(j,0,2005) FOR(k,0,2)FOR(l,0,2) cache[i][j][k][l]=-1;
cin >> n >> l;
FOR(i,0,n) cin >> arr[i];
sort(arr, arr+n);
FOR(i,0,n){
update(i, i, dp(i,i,0,0) + arr[i]*(n+1));
update2(i, i, dp(i,i,0,1) + arr[i]*(n+1));
}
ll q;
cin >> q;
vector<vector<ll>> queries;
FOR(i,0,q){
cin >> a >> b >> t;
queries.push_back({b, a, t, i});
}
sort(queries.begin(), queries.end());
ll prev = 0;
ll pos = 0;
vector<string> ans(q);
for (auto&i : queries){
while (pos < n && arr[pos] <= i[0]){
ll diff = abs(prev-arr[pos]);
update(pos, n-1, -diff*(n+1));
update2(pos, n-1, -diff*(n+1));
if (pos != 0) update(0, pos-1, diff*(n+1));
if (pos != 0) update2(0, pos-1, diff*(n+1));
prev = arr[pos];
pos++;
}
ll diff = abs(prev - i[0]);
prev = i[0];
update(pos, n-1, -diff*(n+1));
update2(pos, n-1, -diff*(n+1));
if (pos != 0) update(0, pos-1, diff*(n+1));
if (pos != 0) update2(0, pos-1, diff*(n+1));
ll temp = INF;
temp = min(temp, query(0, n-1) + abs(i[1]-arr[0]));
temp = min(temp, query2(0, n-1) + abs(i[1]-arr[n-1]));
if (temp+n <= i[2]) ans[i[3]] = "Yes";
else ans[i[3]] = "No";
}
for (auto&i : ans) cout << i << "\n";
}
Compilation message (stderr)
Main.cpp: In function 'll dp(ll, ll, ll, ll)':
Main.cpp:119:1: warning: control reaches end of non-void function [-Wreturn-type]
119 | }
| ^
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |