# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
82830 |
2018-11-02T01:20:33 Z |
Benq |
Meetings (IOI18_meetings) |
C++14 |
|
2786 ms |
325460 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() {
assert(size());
line l = d[s]; l.b += lazy;
return l;
}
line back() {
assert(size());
line l = d[e]; l.b += lazy;
return l;
}
line pop_front() {
assert(size());
line l = front(); s ++;
return l;
}
line pop_back() {
assert(size());
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) {
assert(size());
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;
}
void print() {
FOR(i,s,e+1) {
cout << d[i].s << " " << d[i].e << " " << d[i].m << " " << d[i].b+lazy << "\n";
}
cout << "----\n";
}
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]) {
// cout << "ZZ " << (ll)(x-y[0]+1)*hei[x].f << "\n";
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();
//cout << "AH " << lo << " " << x << " " << hi << " " << lst << "\n";
// r.print();
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 |
106 ms |
79740 KB |
Output is correct |
2 |
Correct |
109 ms |
80140 KB |
Output is correct |
3 |
Correct |
107 ms |
80136 KB |
Output is correct |
4 |
Correct |
108 ms |
80176 KB |
Output is correct |
5 |
Correct |
107 ms |
80188 KB |
Output is correct |
6 |
Correct |
109 ms |
80336 KB |
Output is correct |
7 |
Correct |
110 ms |
80120 KB |
Output is correct |
8 |
Correct |
110 ms |
80388 KB |
Output is correct |
9 |
Correct |
109 ms |
80256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
106 ms |
79740 KB |
Output is correct |
2 |
Correct |
109 ms |
80140 KB |
Output is correct |
3 |
Correct |
107 ms |
80136 KB |
Output is correct |
4 |
Correct |
108 ms |
80176 KB |
Output is correct |
5 |
Correct |
107 ms |
80188 KB |
Output is correct |
6 |
Correct |
109 ms |
80336 KB |
Output is correct |
7 |
Correct |
110 ms |
80120 KB |
Output is correct |
8 |
Correct |
110 ms |
80388 KB |
Output is correct |
9 |
Correct |
109 ms |
80256 KB |
Output is correct |
10 |
Correct |
115 ms |
80812 KB |
Output is correct |
11 |
Correct |
113 ms |
80804 KB |
Output is correct |
12 |
Correct |
115 ms |
80856 KB |
Output is correct |
13 |
Correct |
114 ms |
80844 KB |
Output is correct |
14 |
Correct |
115 ms |
81092 KB |
Output is correct |
15 |
Correct |
115 ms |
80756 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
106 ms |
79708 KB |
Output is correct |
2 |
Correct |
149 ms |
84828 KB |
Output is correct |
3 |
Correct |
306 ms |
106076 KB |
Output is correct |
4 |
Correct |
269 ms |
99668 KB |
Output is correct |
5 |
Correct |
311 ms |
106372 KB |
Output is correct |
6 |
Correct |
307 ms |
107008 KB |
Output is correct |
7 |
Correct |
302 ms |
109124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
106 ms |
79708 KB |
Output is correct |
2 |
Correct |
149 ms |
84828 KB |
Output is correct |
3 |
Correct |
306 ms |
106076 KB |
Output is correct |
4 |
Correct |
269 ms |
99668 KB |
Output is correct |
5 |
Correct |
311 ms |
106372 KB |
Output is correct |
6 |
Correct |
307 ms |
107008 KB |
Output is correct |
7 |
Correct |
302 ms |
109124 KB |
Output is correct |
8 |
Correct |
282 ms |
100440 KB |
Output is correct |
9 |
Correct |
247 ms |
100208 KB |
Output is correct |
10 |
Correct |
287 ms |
100432 KB |
Output is correct |
11 |
Correct |
271 ms |
99500 KB |
Output is correct |
12 |
Correct |
244 ms |
99424 KB |
Output is correct |
13 |
Correct |
282 ms |
99848 KB |
Output is correct |
14 |
Correct |
305 ms |
106520 KB |
Output is correct |
15 |
Correct |
258 ms |
99580 KB |
Output is correct |
16 |
Correct |
296 ms |
106456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
106 ms |
79740 KB |
Output is correct |
2 |
Correct |
109 ms |
80140 KB |
Output is correct |
3 |
Correct |
107 ms |
80136 KB |
Output is correct |
4 |
Correct |
108 ms |
80176 KB |
Output is correct |
5 |
Correct |
107 ms |
80188 KB |
Output is correct |
6 |
Correct |
109 ms |
80336 KB |
Output is correct |
7 |
Correct |
110 ms |
80120 KB |
Output is correct |
8 |
Correct |
110 ms |
80388 KB |
Output is correct |
9 |
Correct |
109 ms |
80256 KB |
Output is correct |
10 |
Correct |
115 ms |
80812 KB |
Output is correct |
11 |
Correct |
113 ms |
80804 KB |
Output is correct |
12 |
Correct |
115 ms |
80856 KB |
Output is correct |
13 |
Correct |
114 ms |
80844 KB |
Output is correct |
14 |
Correct |
115 ms |
81092 KB |
Output is correct |
15 |
Correct |
115 ms |
80756 KB |
Output is correct |
16 |
Correct |
106 ms |
79708 KB |
Output is correct |
17 |
Correct |
149 ms |
84828 KB |
Output is correct |
18 |
Correct |
306 ms |
106076 KB |
Output is correct |
19 |
Correct |
269 ms |
99668 KB |
Output is correct |
20 |
Correct |
311 ms |
106372 KB |
Output is correct |
21 |
Correct |
307 ms |
107008 KB |
Output is correct |
22 |
Correct |
302 ms |
109124 KB |
Output is correct |
23 |
Correct |
282 ms |
100440 KB |
Output is correct |
24 |
Correct |
247 ms |
100208 KB |
Output is correct |
25 |
Correct |
287 ms |
100432 KB |
Output is correct |
26 |
Correct |
271 ms |
99500 KB |
Output is correct |
27 |
Correct |
244 ms |
99424 KB |
Output is correct |
28 |
Correct |
282 ms |
99848 KB |
Output is correct |
29 |
Correct |
305 ms |
106520 KB |
Output is correct |
30 |
Correct |
258 ms |
99580 KB |
Output is correct |
31 |
Correct |
296 ms |
106456 KB |
Output is correct |
32 |
Correct |
1765 ms |
231488 KB |
Output is correct |
33 |
Correct |
1511 ms |
228584 KB |
Output is correct |
34 |
Correct |
1853 ms |
234320 KB |
Output is correct |
35 |
Correct |
1805 ms |
232404 KB |
Output is correct |
36 |
Correct |
1505 ms |
234656 KB |
Output is correct |
37 |
Correct |
1843 ms |
234832 KB |
Output is correct |
38 |
Correct |
2234 ms |
284360 KB |
Output is correct |
39 |
Correct |
2204 ms |
284736 KB |
Output is correct |
40 |
Correct |
1857 ms |
241420 KB |
Output is correct |
41 |
Correct |
2549 ms |
325460 KB |
Output is correct |
42 |
Correct |
2786 ms |
324388 KB |
Output is correct |
43 |
Correct |
2740 ms |
324260 KB |
Output is correct |
44 |
Correct |
2520 ms |
284200 KB |
Output is correct |