| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 677430 |
2023-01-03T10:03:07 Z |
qwerasdfzxcl |
None (JOI15_walls) |
C++17 |
|
415 ms |
62640 KB |
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
constexpr ll INF = 1e18;
constexpr int INF2 = 1e9 + 100;
ll a[200200];
int l[200200], r[200200], n, q;
pair<ll, int> operator + (const pair<ll, int> &x, const pair<ll, int> &y) {return make_pair(x.first + y.first, x.second + y.second);}
ll myabs(ll x){return x<0?-x:x;}
struct Edge{
int s, e;
ll x;
Edge(){}
Edge(int _s, int _e, ll _x): s(_s), e(_e), x(_x) {}
bool operator < (const Edge &E) const{
return tie(x, s) > tie(E.x, E.s);
}
};
struct Seg{
pair<ll, int> tree[400400];
ll treemin[400400];
int sz;
void init(int n, pair<ll, int> a[]){
sz = n;
for (int i=sz;i<sz*2;i++){
tree[i] = a[i-sz];
if (a[i-sz].second > 0) treemin[i] = a[i-sz].first;
else treemin[i] = INF2;
}
for (int i=sz-1;i;i--){
tree[i] = tree[i<<1] + tree[i<<1|1];
treemin[i] = std::min(treemin[i<<1], treemin[i<<1|1]);
}
}
void update(int p, pair<ll, int> x){
p += sz;
if (x.second > 0) treemin[p] = x.first;
else treemin[p] = INF2;
tree[p] = x;
for (p>>=1;p;p>>=1){
tree[p] = tree[p<<1] + tree[p<<1|1];
treemin[p] = std::min(treemin[p<<1], treemin[p<<1|1]);
}
}
pair<ll, int> query(int l, int r){
pair<ll, int> ret = make_pair(0LL, 0);
++r;
for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
if (l&1) ret = ret + tree[l++];
if (r&1) ret = ret + tree[--r];
}
return ret;
}
ll min(){return treemin[1];}
};
struct Linked_List{
int nxt[200200], prv[200200];
pair<ll, int> dist[200200]; ///dist[i] = (i -> nxt[i])
priority_queue<Edge> pq;
Seg tree;
ll a[200200];
void init(ll s){
//printf(" a[0] = %lld\n", s);
for (int i=1;i<=n;i++) a[i] = ::a[i];
a[0] = s;
fill(nxt, nxt+n+1, -INF2);
fill(prv, prv+n+1, -INF2);
fill(dist, dist+n+1, make_pair(0LL, 0));
for (int i=0;i<n;){
int j = i+1;
ll dmn = a[j] - a[i], dmx = a[j] - a[i];
while(j<=n){
dmn = min(dmn, a[j] - a[j-1]);
dmx = max(dmx, a[j] - a[j-1]);
if (dmn < 0 && dmx > 0) break;
j++;
}
if (dmn==0 && dmx==0) break;
--j;
//printf(" i = %d / j = %d\n", i, j);
nxt[i] = j, prv[j] = i;
dist[i] = make_pair(myabs(a[j] - a[i]), 1);
pq.emplace(i, j, dist[i].first);
i = j;
}
tree.init(n+1, dist);
}
void process(int L){
while(tree.min() <= L){
auto [s, e, x] = pq.top(); pq.pop();
if (nxt[s]!=e) continue;
//printf("delete: %d %d %lld\n", s, e, x);
int ss = prv[s], ee = nxt[e];
///delete
nxt[s] = -INF2;
prv[e] = -INF2;
dist[s] = make_pair(0LL, 0);
tree.update(s, dist[s]);
///link
assert(ss!=-INF2);
if (ee==-INF2) continue;
prv[s] = -INF2;
nxt[e] = -INF2;
dist[e] = make_pair(0LL, 0);
tree.update(e, dist[e]);
nxt[ss] = ee, prv[ee] = ss;
dist[ss] = make_pair(myabs(a[ee]-a[ss]), 1);
tree.update(ss, dist[ss]);
pq.emplace(ss, ee, dist[ss].first);
}
}
ll query(int s, int L){
//printf("query %d %d (%lld)\n", L, s, a[0]);
process(L);
auto [sum, c] = tree.query(s, n);
//printf(" sum = %lld / c = %d -> %lld\n", sum, c, sum - (ll)(L)*c);
return sum - (ll)(L)*c;
}
}Llist, Rlist;
ll pmn[200200], pmx[200200], pL[200200], pR[200200], iL[200200], iR[200200], ans[200200];
ll calc(int L, int R){
int posL = upper_bound(pmn+1, pmn+n+1, -L) - pmn;
int posR = upper_bound(pmx+1, pmx+n+1, R) - pmx;
if (posL==n+1 && posR==n+1) return 0;
if (posL < posR){
int pos = upper_bound(pL+1, pL+n+1, R-L) - pL - 1;
return Rlist.query(iL[pos], R-L) + (L - a[iL[pos]]);
}
else{
assert(posL > posR);
int pos = upper_bound(pR+1, pR+n+1, R-L) - pR - 1;
return Llist.query(iR[pos], R-L) + (a[iR[pos]] - R);
}
assert(0);
return 0;
}
bool cmp(int i, int j){return r[i] - l[i] < r[j] - l[j];}
int main(){
scanf("%d %d", &q, &n);
for (int i=1;i<=q;i++) scanf("%d %d", l+i, r+i);
for (int i=1;i<=n;i++) scanf("%lld", a+i);
Llist.init(-INF);
Rlist.init(INF);
pmn[0] = -INF2, pmx[0] = -INF2, pL[0] = -INF2, pR[0] = -INF2;
for (int i=1;i<=n;i++){
if (pmn[i-1] < -a[i]) iL[i] = i;
else iL[i] = iL[i-1];
if (pmx[i-1] < a[i]) iR[i] = i;
else iR[i] = iR[i-1];
pmn[i] = max(pmn[i-1], -a[i]);
pmx[i] = max(pmx[i-1], a[i]);
pL[i] = max(pL[i-1], a[i] + pmn[i]);
pR[i] = max(pR[i-1], pmx[i] - a[i]);
}
vector<int> idx;
for (int i=1;i<=q;i++) idx.push_back(i);
sort(idx.begin(), idx.end(), cmp);
for (auto &i:idx) ans[i] = calc(l[i], r[i]);
for (int i=1;i<=q;i++) printf("%lld\n", ans[i]);
return 0;
}
Compilation message
walls.cpp: In function 'int main()':
walls.cpp:164:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
164 | scanf("%d %d", &q, &n);
| ~~~~~^~~~~~~~~~~~~~~~~
walls.cpp:165:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
165 | for (int i=1;i<=q;i++) scanf("%d %d", l+i, r+i);
| ~~~~~^~~~~~~~~~~~~~~~~~~
walls.cpp:166:33: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
166 | for (int i=1;i<=n;i++) scanf("%lld", a+i);
| ~~~~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
20820 KB |
Output is correct |
| 2 |
Correct |
96 ms |
47300 KB |
Output is correct |
| 3 |
Correct |
108 ms |
49504 KB |
Output is correct |
| 4 |
Correct |
88 ms |
49348 KB |
Output is correct |
| 5 |
Correct |
93 ms |
49412 KB |
Output is correct |
| 6 |
Correct |
67 ms |
49432 KB |
Output is correct |
| 7 |
Correct |
60 ms |
42916 KB |
Output is correct |
| 8 |
Correct |
41 ms |
42888 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
23192 KB |
Output is correct |
| 2 |
Correct |
128 ms |
49772 KB |
Output is correct |
| 3 |
Correct |
127 ms |
31176 KB |
Output is correct |
| 4 |
Correct |
259 ms |
60956 KB |
Output is correct |
| 5 |
Correct |
225 ms |
58796 KB |
Output is correct |
| 6 |
Correct |
262 ms |
60864 KB |
Output is correct |
| 7 |
Correct |
226 ms |
58800 KB |
Output is correct |
| 8 |
Correct |
256 ms |
60864 KB |
Output is correct |
| 9 |
Correct |
119 ms |
51672 KB |
Output is correct |
| 10 |
Correct |
216 ms |
60136 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
20820 KB |
Output is correct |
| 2 |
Correct |
96 ms |
47300 KB |
Output is correct |
| 3 |
Correct |
108 ms |
49504 KB |
Output is correct |
| 4 |
Correct |
88 ms |
49348 KB |
Output is correct |
| 5 |
Correct |
93 ms |
49412 KB |
Output is correct |
| 6 |
Correct |
67 ms |
49432 KB |
Output is correct |
| 7 |
Correct |
60 ms |
42916 KB |
Output is correct |
| 8 |
Correct |
41 ms |
42888 KB |
Output is correct |
| 9 |
Correct |
26 ms |
23192 KB |
Output is correct |
| 10 |
Correct |
128 ms |
49772 KB |
Output is correct |
| 11 |
Correct |
127 ms |
31176 KB |
Output is correct |
| 12 |
Correct |
259 ms |
60956 KB |
Output is correct |
| 13 |
Correct |
225 ms |
58796 KB |
Output is correct |
| 14 |
Correct |
262 ms |
60864 KB |
Output is correct |
| 15 |
Correct |
226 ms |
58800 KB |
Output is correct |
| 16 |
Correct |
256 ms |
60864 KB |
Output is correct |
| 17 |
Correct |
119 ms |
51672 KB |
Output is correct |
| 18 |
Correct |
216 ms |
60136 KB |
Output is correct |
| 19 |
Correct |
328 ms |
60496 KB |
Output is correct |
| 20 |
Correct |
415 ms |
62588 KB |
Output is correct |
| 21 |
Correct |
329 ms |
60524 KB |
Output is correct |
| 22 |
Correct |
376 ms |
58488 KB |
Output is correct |
| 23 |
Correct |
323 ms |
60328 KB |
Output is correct |
| 24 |
Correct |
408 ms |
62640 KB |
Output is correct |
| 25 |
Correct |
180 ms |
54092 KB |
Output is correct |
| 26 |
Correct |
178 ms |
54584 KB |
Output is correct |
| 27 |
Correct |
280 ms |
62124 KB |
Output is correct |
