# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
831247 |
2023-08-20T02:25:22 Z |
79brue |
Meetings (IOI18_meetings) |
C++17 |
|
5086 ms |
742440 KB |
#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MX = 750002;
int n, q;
ll arr[MX];
int ql[MX], qr[MX];
ll ans[MX];
void solve();
vector<ll> minimum_costs(vector<int> H, vector<int> L, vector<int> R){
n = (int)H.size();
for(int i=1; i<=n; i++) arr[i] = H[i-1];
q = (int)L.size();
for(int i=1; i<=q; i++) ql[i] = L[i-1]+1, qr[i] = R[i-1]+1, ans[i] = LLONG_MAX;
solve();
vector<ll> ret;
for(int i=1; i<=q; i++) ret.push_back(ans[i]);
return ret;
}
void makeCartesianTree();
void reformQuery();
void calculateAnswer();
int mult = 1;
void solve(){
makeCartesianTree();
reformQuery();
calculateAnswer();
reverse(arr+1, arr+n+1);
for(int i=1; i<=q; i++) ql[i] = n+1-ql[i], qr[i] = n+1-qr[i], swap(ql[i], qr[i]);
mult = -1;
makeCartesianTree();
reformQuery();
calculateAnswer();
}
struct segTree{
pair<int, int> tree[1<<21];
void init(int i, int l, int r, ll *A){
if(l==r){
tree[i] = make_pair(A[l], l * mult);
return;
}
int m = (l+r)>>1;
init(i*2, l, m, A);
init(i*2+1, m+1, r, A);
tree[i] = max(tree[i*2], tree[i*2+1]);
}
pair<int, int> query(int i, int l, int r, int s, int e){
if(r<s || e<l) return make_pair(0, 0);
if(s<=l && r<=e) return tree[i];
int m = (l+r)>>1;
return max(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
}
} tree;
int par[MX], lc[MX], rc[MX];
int intvL[MX], intvR[MX], root;
int thisL[MX];
int dnc(int l, int r, int p=0){
if(l>r) return 0;
int x = mult * tree.query(1, 1, n, l, r).second;
par[x] = p;
intvL[x] = l, intvR[x] = r;
lc[x] = dnc(l, x-1);
rc[x] = dnc(x+1, r);
thisL[intvL[x]] = x;
// printf("thisL[%d] = %d\n", intvL[x], x);
return x;
}
void makeCartesianTree(){
for(int i=1; i<=n; i++){
par[i] = lc[i] = rc[i] = thisL[i] = 0;
}
tree.init(1, 1, n, arr);
root = dnc(1, n);
}
vector<int> vec[MX];
void reformQuery(){
for(int i=1; i<=n; i++) vec[i].clear();
for(int i=1; i<=q; i++){
if(ql[i] == qr[i]){
ans[i] = arr[ql[i]];
continue;
}
int l = ql[i], r = qr[i], x = mult * tree.query(1, 1, n, l, r).second;
if(x==qr[i]) ans[i] = min(ans[i], arr[x] * (r-l+1));
else vec[thisL[x+1]].push_back(i);
//printf("Pushed %d to %d (x %d)\n", i, thisL[x+1], x);
}
}
ll lazy[MX], rEnd[MX];
ll setA[MX], setB[MX];
deque<ll> dq[MX];
ll backVal(int x){
int t = dq[x].back();
// printf("backVal[%d] = %lld (t=%d)\n", x, setA[t] * rEnd[t] + setB[t] + lazy[x], t);
return setA[t] * rEnd[t] + setB[t] + lazy[x];
}
ll calc(int x, ll v){
if(!(!dq[x].empty() && dq[x][0] <= v)){
printf("calc x: %d, v: %lld\n", x, v);
printf("dq[%d]: ", x); for(int p: dq[x]) printf("%d-%d ", p, rEnd[p]); puts("");
exit(1);
}
int p = *prev(upper_bound(dq[x].begin(), dq[x].end(), v));
return setA[p] * v + setB[p] + lazy[x];
}
void render(int x, ll a, ll b){
if(dq[x].empty() || setA[dq[x].front()] * dq[x].front() + setB[dq[x].front()] + lazy[x] <= a*dq[x].front()+b)
return;
ll L = dq[x].front(), R = L-1;
while(!dq[x].empty()){
int f = dq[x].front();
if(setA[f] * f + setB[f] + lazy[x] < a * f + b) break;
if(setA[f] * rEnd[f] + setB[f] + lazy[x] >= a * rEnd[f] + b){
R = rEnd[f];
dq[x].pop_front();
continue;
}
while(setA[f] * (R+1) + setB[f] + lazy[x] > a * (R+1) + b) R++;
dq[x].front() = R+1;
setA[R+1] = setA[f], setB[R+1] = setB[f], rEnd[R+1] = rEnd[f];
if(R+1 != f) setA[f] = setB[f] = rEnd[f] = 0;
break;
ll ad = a - setA[f], bd = setB[f] + lazy[x] - b;
ll newL = ceil((long double)(bd) / (long double)(ad));
dq[x].front() = newL;
setA[newL] = setA[f], setB[newL] = setB[f], rEnd[newL] = rEnd[f];
if(newL != f) setA[f] = setB[f] = rEnd[f] = 0;
break;
}
//printf("After render, [%d - %d] is formed\n", L, R);
if(L<=R){
dq[x].push_front(L);
rEnd[L] = R;
setA[L] = a, setB[L] = b - lazy[x];
//printf("dq[%d]: ", x); for(int p: dq[x]) printf("%d ", p); puts("");
}
}
void merge(ll a, ll b){
if((int)dq[a].size() > dq[b].size()){
for(int x: dq[b]) dq[a].push_back(x), setB[x] += lazy[b] - lazy[a];
}
else{
for(int i=(int)dq[a].size()-1; i>=0; i--){
dq[b].push_front(dq[a][i]);
setB[dq[b].front()] += lazy[a] - lazy[b];
}
dq[a].swap(dq[b]);
lazy[a] = lazy[b];
}
dq[b].clear();
dq[b].shrink_to_fit();
}
void dnc(int x){
int L = intvL[x], R = intvR[x];
// printf("dnc %d %d %d\n", x, L, R);
/// [L, x]
if(lc[x]){
dnc(lc[x]);
lazy[x] = lazy[lc[x]], dq[x].swap(dq[lc[x]]);
setA[x] = 0, setB[x] = backVal(x) + arr[x] - lazy[x];
dq[x].push_back(x);
}
else{
dq[x].push_back(x);
rEnd[x] = x;
setA[x] = 0, setB[x] = arr[x] - lazy[x];
}
if(rc[x]){
dnc(rc[x]);
/// DP[rc[x]] 앞부분을 다듬는다
ll v = backVal(x), vAll = arr[x] * (x-L+1);
// printf("Added %lld to %d\n", vAll, rc[x]);
lazy[rc[x]] += vAll;
render(rc[x], arr[x], v-arr[x]*x);
merge(x, rc[x]);
}
for(int idx: vec[x]){
ans[idx] = min(ans[idx], calc(x, qr[idx]) + arr[intvL[x]-1] * (intvL[x] - ql[idx]));
//printf("Checking %d: maybe %lld + %lld = %lld\n", idx, calc(x, qr[idx]), arr[intvL[x]-1]*(intvL[x]-ql[idx]),
//calc(x, qr[idx]) + arr[intvL[x]-1] * (intvL[x] - ql[idx]));
}
//printf("Deque of %d\n", x);
//for(int p: dq[x]) printf("[%d-%d] %lldx + %lld, \t", p, rEnd[p], setA[p], setB[p]+lazy[x]); puts("");
}
void calculateAnswer(){
for(int i=1; i<=n; i++){
lazy[i] = 0, rEnd[i] = i, setA[i] = setB[i] = 0;
dq[i].clear();
}
dnc(root);
}
Compilation message
meetings.cpp: In function 'll calc(int, ll)':
meetings.cpp:124:62: warning: format '%d' expects argument of type 'int', but argument 3 has type 'll' {aka 'long long int'} [-Wformat=]
124 | printf("dq[%d]: ", x); for(int p: dq[x]) printf("%d-%d ", p, rEnd[p]); puts("");
| ~^ ~~~~~~~
| | |
| int ll {aka long long int}
| %lld
meetings.cpp: In function 'void merge(ll, ll)':
meetings.cpp:168:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
168 | if((int)dq[a].size() > dq[b].size()){
| ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
meetings.cpp: In function 'void dnc(int)':
meetings.cpp:184:23: warning: unused variable 'R' [-Wunused-variable]
184 | int L = intvL[x], R = intvR[x];
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
269 ms |
522892 KB |
Output is correct |
2 |
Correct |
274 ms |
523116 KB |
Output is correct |
3 |
Correct |
263 ms |
523192 KB |
Output is correct |
4 |
Correct |
271 ms |
523192 KB |
Output is correct |
5 |
Correct |
259 ms |
523092 KB |
Output is correct |
6 |
Correct |
230 ms |
523400 KB |
Output is correct |
7 |
Correct |
271 ms |
523188 KB |
Output is correct |
8 |
Correct |
261 ms |
523420 KB |
Output is correct |
9 |
Correct |
232 ms |
523252 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
269 ms |
522892 KB |
Output is correct |
2 |
Correct |
274 ms |
523116 KB |
Output is correct |
3 |
Correct |
263 ms |
523192 KB |
Output is correct |
4 |
Correct |
271 ms |
523192 KB |
Output is correct |
5 |
Correct |
259 ms |
523092 KB |
Output is correct |
6 |
Correct |
230 ms |
523400 KB |
Output is correct |
7 |
Correct |
271 ms |
523188 KB |
Output is correct |
8 |
Correct |
261 ms |
523420 KB |
Output is correct |
9 |
Correct |
232 ms |
523252 KB |
Output is correct |
10 |
Correct |
307 ms |
523912 KB |
Output is correct |
11 |
Correct |
304 ms |
523788 KB |
Output is correct |
12 |
Correct |
273 ms |
523888 KB |
Output is correct |
13 |
Correct |
278 ms |
523800 KB |
Output is correct |
14 |
Correct |
242 ms |
524056 KB |
Output is correct |
15 |
Correct |
311 ms |
523804 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
245 ms |
522908 KB |
Output is correct |
2 |
Correct |
307 ms |
527164 KB |
Output is correct |
3 |
Correct |
442 ms |
549872 KB |
Output is correct |
4 |
Correct |
478 ms |
538388 KB |
Output is correct |
5 |
Correct |
365 ms |
548128 KB |
Output is correct |
6 |
Correct |
425 ms |
545796 KB |
Output is correct |
7 |
Correct |
438 ms |
546756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
245 ms |
522908 KB |
Output is correct |
2 |
Correct |
307 ms |
527164 KB |
Output is correct |
3 |
Correct |
442 ms |
549872 KB |
Output is correct |
4 |
Correct |
478 ms |
538388 KB |
Output is correct |
5 |
Correct |
365 ms |
548128 KB |
Output is correct |
6 |
Correct |
425 ms |
545796 KB |
Output is correct |
7 |
Correct |
438 ms |
546756 KB |
Output is correct |
8 |
Correct |
424 ms |
540056 KB |
Output is correct |
9 |
Correct |
407 ms |
539764 KB |
Output is correct |
10 |
Correct |
425 ms |
540072 KB |
Output is correct |
11 |
Correct |
430 ms |
537592 KB |
Output is correct |
12 |
Correct |
445 ms |
537284 KB |
Output is correct |
13 |
Correct |
415 ms |
537704 KB |
Output is correct |
14 |
Correct |
431 ms |
544084 KB |
Output is correct |
15 |
Correct |
461 ms |
537396 KB |
Output is correct |
16 |
Correct |
440 ms |
544140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
269 ms |
522892 KB |
Output is correct |
2 |
Correct |
274 ms |
523116 KB |
Output is correct |
3 |
Correct |
263 ms |
523192 KB |
Output is correct |
4 |
Correct |
271 ms |
523192 KB |
Output is correct |
5 |
Correct |
259 ms |
523092 KB |
Output is correct |
6 |
Correct |
230 ms |
523400 KB |
Output is correct |
7 |
Correct |
271 ms |
523188 KB |
Output is correct |
8 |
Correct |
261 ms |
523420 KB |
Output is correct |
9 |
Correct |
232 ms |
523252 KB |
Output is correct |
10 |
Correct |
307 ms |
523912 KB |
Output is correct |
11 |
Correct |
304 ms |
523788 KB |
Output is correct |
12 |
Correct |
273 ms |
523888 KB |
Output is correct |
13 |
Correct |
278 ms |
523800 KB |
Output is correct |
14 |
Correct |
242 ms |
524056 KB |
Output is correct |
15 |
Correct |
311 ms |
523804 KB |
Output is correct |
16 |
Correct |
245 ms |
522908 KB |
Output is correct |
17 |
Correct |
307 ms |
527164 KB |
Output is correct |
18 |
Correct |
442 ms |
549872 KB |
Output is correct |
19 |
Correct |
478 ms |
538388 KB |
Output is correct |
20 |
Correct |
365 ms |
548128 KB |
Output is correct |
21 |
Correct |
425 ms |
545796 KB |
Output is correct |
22 |
Correct |
438 ms |
546756 KB |
Output is correct |
23 |
Correct |
424 ms |
540056 KB |
Output is correct |
24 |
Correct |
407 ms |
539764 KB |
Output is correct |
25 |
Correct |
425 ms |
540072 KB |
Output is correct |
26 |
Correct |
430 ms |
537592 KB |
Output is correct |
27 |
Correct |
445 ms |
537284 KB |
Output is correct |
28 |
Correct |
415 ms |
537704 KB |
Output is correct |
29 |
Correct |
431 ms |
544084 KB |
Output is correct |
30 |
Correct |
461 ms |
537396 KB |
Output is correct |
31 |
Correct |
440 ms |
544140 KB |
Output is correct |
32 |
Correct |
1770 ms |
633604 KB |
Output is correct |
33 |
Correct |
1344 ms |
649272 KB |
Output is correct |
34 |
Correct |
1808 ms |
653092 KB |
Output is correct |
35 |
Correct |
1823 ms |
652864 KB |
Output is correct |
36 |
Correct |
1441 ms |
652764 KB |
Output is correct |
37 |
Correct |
1787 ms |
653440 KB |
Output is correct |
38 |
Correct |
2110 ms |
702528 KB |
Output is correct |
39 |
Correct |
2275 ms |
702472 KB |
Output is correct |
40 |
Correct |
5086 ms |
658584 KB |
Output is correct |
41 |
Correct |
2188 ms |
741844 KB |
Output is correct |
42 |
Correct |
2593 ms |
742392 KB |
Output is correct |
43 |
Correct |
2527 ms |
742440 KB |
Output is correct |
44 |
Correct |
2684 ms |
699840 KB |
Output is correct |