# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
82831 |
2018-11-02T01:22:28 Z |
Benq |
Meetings (IOI18_meetings) |
C++14 |
|
2763 ms |
324788 KB |
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 1<<20;
const int SZ = 750001;
#include "meetings.h"
pl operator*(const pl& l, const ll& r) { return {l.f*r,l.s*r}; }
pl operator+(const pl& l, const pl& r) { return {l.f+r.f,l.s+r.s}; }
pl operator+=(pl& l, const pl& r) { return l = {l.f+r.f,l.s+r.s}; }
int N;
vpi hei;
void checkmn(ll& x, ll y) { x = min(x,y); }
struct RMQ {
int mx[SZ][21];
int bet(int a, int b) {
return hei[a] > hei[b] ? a : b;
}
RMQ() {
F0R(i,N) mx[i][0] = i;
FOR(j,1,21) F0R(i,N-(1<<j)+1)
mx[i][j] = bet(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);
}
int query(int L, int R) {
int x = 31-__builtin_clz(R-L+1);
return bet(mx[L][x],mx[R-(1<<x)+1][x]);
}
};
RMQ RM;
ll ans[SZ];
vector<array<int,3>> tmp[SZ];
struct line {
int s,e;
ll m,b;
line() {}
line(int _s, int _e, ll _m, ll _b) { s = _s, e = _e, m = _m, b = _b; }
ll eval(int x) { return m*x+b; }
};
line d[SZ];
struct lineContain {
int s,e;
ll lazy = 0;
lineContain(int _s, int _e) {
s = _s, e = _e;
}
ll evalBack() {
if (!size()) return 0;
return d[e].eval(d[e].e)+lazy;
}
line front() {
line l = d[s]; l.b += lazy;
return l;
}
line back() {
line l = d[e]; l.b += lazy;
return l;
}
line pop_front() {
line l = front(); s ++;
return l;
}
line pop_back() {
line l = back(); e --;
return l;
}
ll get(int m) {
if (size() == 0 || m < d[s].s) return 0;
int lo = s, hi = e;
while (lo < hi) {
int mid = (lo+hi+1)/2;
if (d[mid].s <= m) lo = mid;
else hi = mid-1;
}
return d[lo].eval(m)+lazy;
}
ll evalFront(ll x) {
return d[s].eval(x)+lazy;
}
void push_back(line l) {
l.b -= lazy;
d[++e] = l;
}
void push_front(line l) {
l.b -= lazy;
d[--s] = l;
}
int size() { return e-s+1; }
};
lineContain divi(int lo, int hi) {
if (lo > hi) return lineContain(lo,lo-1);
ll x = RM.query(lo,hi);
auto l = divi(lo,x-1); auto r = divi(x+1,hi);
for (auto y: tmp[x]) checkmn(ans[y[2]],(ll)(x-y[0]+1)*hei[x].f+r.get(y[1]));
r.lazy += (x-lo+1)*hei[x].f;
int right = x;
ll lst = l.evalBack();
while (sz(r)) {
ll e = r.front().e;
ll a = lst+(e-x+1)*hei[x].f;
ll b = r.evalFront(e);
if (a <= b) {
right = e; r.pop_front();
continue;
} else {
ll s = r.front().s;
while (s < e) {
ll m = (s+e)/2;
a = lst+(m-x+1)*hei[x].f;
b = r.evalFront(m);
if (a <= b) s = m+1;
else e = m;
}
right = s-1;
auto a = r.pop_front(); a.s = s; r.push_front(a);
break;
// binary search
}
}
l.pb(line(x,right,hei[x].f,lst-hei[x].f*(x-1)));
if (sz(l) > sz(r)) {
while (sz(r)) l.pb(r.pop_front());
return l;
} else {
while (sz(l)) r.push_front(l.pop_back());
return r;
}
}
void solve(vi L, vi R) {
RM = RMQ();
vi h; F0R(i,N) h.pb(i);
sort(all(h),[](int a, int b) { return hei[a] < hei[b]; });
F0R(i,SZ) tmp[i].clear();
F0R(i,sz(L)) tmp[RM.query(L[i],R[i])].pb({L[i],R[i],i});
divi(0,N-1);
}
std::vector<long long> minimum_costs(std::vector<int> H, std::vector<int> L,
std::vector<int> R) {
N = sz(H);
F0R(i,N) hei.pb({H[i],i});
F0R(i,sz(L)) ans[i] = INF;
solve(L,R);
reverse(all(hei));
F0R(i,sz(L)) {
L[i] = sz(H)-1-L[i];
R[i] = sz(H)-1-R[i];
swap(L[i],R[i]);
}
// cout << "\n";
solve(L,R);
vl ret; F0R(i,sz(L)) ret.pb(ans[i]);
return ret;
}
/*
int main() {
int N,Q; cin >> N >> Q;// N = Q = 750000;
vi H(N), L(Q), R(Q);
F0R(i,N) {
// H[i] = rand() % 1000000000;
cin >> H[i];
}
F0R(i,Q) {
L[i] = rand() % N, R[i] = rand() % N;
if (L[i] > R[i]) swap(L[i],R[i]);
cin >> L[i] >> R[i];
}
vl C = minimum_costs(H, L, R);
for (auto a: C) cout << a << " ";
}*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
108 ms |
79752 KB |
Output is correct |
2 |
Correct |
109 ms |
80120 KB |
Output is correct |
3 |
Correct |
109 ms |
80056 KB |
Output is correct |
4 |
Correct |
109 ms |
80148 KB |
Output is correct |
5 |
Correct |
110 ms |
80152 KB |
Output is correct |
6 |
Correct |
108 ms |
80364 KB |
Output is correct |
7 |
Correct |
110 ms |
80108 KB |
Output is correct |
8 |
Correct |
107 ms |
80332 KB |
Output is correct |
9 |
Correct |
107 ms |
80236 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
108 ms |
79752 KB |
Output is correct |
2 |
Correct |
109 ms |
80120 KB |
Output is correct |
3 |
Correct |
109 ms |
80056 KB |
Output is correct |
4 |
Correct |
109 ms |
80148 KB |
Output is correct |
5 |
Correct |
110 ms |
80152 KB |
Output is correct |
6 |
Correct |
108 ms |
80364 KB |
Output is correct |
7 |
Correct |
110 ms |
80108 KB |
Output is correct |
8 |
Correct |
107 ms |
80332 KB |
Output is correct |
9 |
Correct |
107 ms |
80236 KB |
Output is correct |
10 |
Correct |
113 ms |
80784 KB |
Output is correct |
11 |
Correct |
112 ms |
80760 KB |
Output is correct |
12 |
Correct |
114 ms |
80736 KB |
Output is correct |
13 |
Correct |
113 ms |
80860 KB |
Output is correct |
14 |
Correct |
115 ms |
81056 KB |
Output is correct |
15 |
Correct |
114 ms |
80760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
107 ms |
79764 KB |
Output is correct |
2 |
Correct |
149 ms |
84844 KB |
Output is correct |
3 |
Correct |
311 ms |
106128 KB |
Output is correct |
4 |
Correct |
264 ms |
99664 KB |
Output is correct |
5 |
Correct |
311 ms |
106320 KB |
Output is correct |
6 |
Correct |
295 ms |
106964 KB |
Output is correct |
7 |
Correct |
289 ms |
109136 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
107 ms |
79764 KB |
Output is correct |
2 |
Correct |
149 ms |
84844 KB |
Output is correct |
3 |
Correct |
311 ms |
106128 KB |
Output is correct |
4 |
Correct |
264 ms |
99664 KB |
Output is correct |
5 |
Correct |
311 ms |
106320 KB |
Output is correct |
6 |
Correct |
295 ms |
106964 KB |
Output is correct |
7 |
Correct |
289 ms |
109136 KB |
Output is correct |
8 |
Correct |
289 ms |
100376 KB |
Output is correct |
9 |
Correct |
245 ms |
100204 KB |
Output is correct |
10 |
Correct |
289 ms |
100464 KB |
Output is correct |
11 |
Correct |
270 ms |
99528 KB |
Output is correct |
12 |
Correct |
254 ms |
99480 KB |
Output is correct |
13 |
Correct |
280 ms |
99928 KB |
Output is correct |
14 |
Correct |
294 ms |
106460 KB |
Output is correct |
15 |
Correct |
249 ms |
99620 KB |
Output is correct |
16 |
Correct |
288 ms |
106396 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
108 ms |
79752 KB |
Output is correct |
2 |
Correct |
109 ms |
80120 KB |
Output is correct |
3 |
Correct |
109 ms |
80056 KB |
Output is correct |
4 |
Correct |
109 ms |
80148 KB |
Output is correct |
5 |
Correct |
110 ms |
80152 KB |
Output is correct |
6 |
Correct |
108 ms |
80364 KB |
Output is correct |
7 |
Correct |
110 ms |
80108 KB |
Output is correct |
8 |
Correct |
107 ms |
80332 KB |
Output is correct |
9 |
Correct |
107 ms |
80236 KB |
Output is correct |
10 |
Correct |
113 ms |
80784 KB |
Output is correct |
11 |
Correct |
112 ms |
80760 KB |
Output is correct |
12 |
Correct |
114 ms |
80736 KB |
Output is correct |
13 |
Correct |
113 ms |
80860 KB |
Output is correct |
14 |
Correct |
115 ms |
81056 KB |
Output is correct |
15 |
Correct |
114 ms |
80760 KB |
Output is correct |
16 |
Correct |
107 ms |
79764 KB |
Output is correct |
17 |
Correct |
149 ms |
84844 KB |
Output is correct |
18 |
Correct |
311 ms |
106128 KB |
Output is correct |
19 |
Correct |
264 ms |
99664 KB |
Output is correct |
20 |
Correct |
311 ms |
106320 KB |
Output is correct |
21 |
Correct |
295 ms |
106964 KB |
Output is correct |
22 |
Correct |
289 ms |
109136 KB |
Output is correct |
23 |
Correct |
289 ms |
100376 KB |
Output is correct |
24 |
Correct |
245 ms |
100204 KB |
Output is correct |
25 |
Correct |
289 ms |
100464 KB |
Output is correct |
26 |
Correct |
270 ms |
99528 KB |
Output is correct |
27 |
Correct |
254 ms |
99480 KB |
Output is correct |
28 |
Correct |
280 ms |
99928 KB |
Output is correct |
29 |
Correct |
294 ms |
106460 KB |
Output is correct |
30 |
Correct |
249 ms |
99620 KB |
Output is correct |
31 |
Correct |
288 ms |
106396 KB |
Output is correct |
32 |
Correct |
1729 ms |
231472 KB |
Output is correct |
33 |
Correct |
1498 ms |
227972 KB |
Output is correct |
34 |
Correct |
1926 ms |
233652 KB |
Output is correct |
35 |
Correct |
1862 ms |
231736 KB |
Output is correct |
36 |
Correct |
1504 ms |
233904 KB |
Output is correct |
37 |
Correct |
1863 ms |
234168 KB |
Output is correct |
38 |
Correct |
2267 ms |
283956 KB |
Output is correct |
39 |
Correct |
2216 ms |
284036 KB |
Output is correct |
40 |
Correct |
1862 ms |
240552 KB |
Output is correct |
41 |
Correct |
2593 ms |
324788 KB |
Output is correct |
42 |
Correct |
2701 ms |
323880 KB |
Output is correct |
43 |
Correct |
2763 ms |
323772 KB |
Output is correct |
44 |
Correct |
2569 ms |
283636 KB |
Output is correct |