QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #44823 | #601. 李超树 | kongziisreallygod# | AC ✓ | 332ms | 36912kb | C++ | 5.1kb | 2022-08-21 21:13:31 | 2022-08-21 21:13:32 |
Judging History
answer
#pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
#define F first
#define S second
#define vec vector
#define pb push_back
#define pll pair<ll, ll>
#define pdd pair<ld, ld>
#define pii pair<int, int>
#define pnn pair<Node*, Node*>
#define all(m) m.begin(), m.end()
#define rall(m) m.rbegin(), m.rend()
#define uid uniform_int_distribution
#define uset(A) unordered_set<A, custom_hash>
#define umap(A, B) unordered_map<A, B, custom_hash>
#define timeStamp() std::chrono::steady_clock::now()
#define unify(m) sort(all(m)); m.erase(unique(all(m)), m.end());
#define duration_nano(a) chrono::duration_cast<chrono::nanoseconds>(a).count()
#define duration_milli(a) chrono::duration_cast<chrono::milliseconds>(a).count()
#define fast cin.tie(0); cout.tie(0); cin.sync_with_stdio(0); cout.sync_with_stdio(0);
using namespace std;
using str = string;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
mt19937 rnd(timeStamp().time_since_epoch().count());
template<typename T> bool chmin(T& a, const T& b) {return b < a ? a = b, 1 : 0;}
template<typename T> bool chmax(T& a, const T& b) {return b > a ? a = b, 1 : 0;}
constexpr inline uint leq_pow2(const uint x) {return 1u << __lg(x);}
constexpr inline ull leq_pow2ll(const ull x) {return 1ull << __lg(x);}
constexpr inline uint geq_pow2(const uint x) {return x & (x - 1) ? 2u << __lg(x) : x;}
constexpr inline ull geq_pow2ll(const ull x) {return x & (x - 1) ? 2ull << __lg(x) : x;}
constexpr inline ll sqd(const pll p1, const pll p2) {return (p1.F - p2.F) * (p1.F - p2.F) + (p1.S - p2.S) * (p1.S - p2.S);}
constexpr inline ll sqd(const ll x1, const ll y1, const ll x2, const ll y2) {return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);}
struct custom_hash {static uint64_t xs(uint64_t x) {x += 0x9e3779b97f4a7c15; x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9; x = (x ^ (x >> 27)) * 0x94d049bb133111eb; return x ^ (x >> 31);} template<typename T> size_t operator()(T x) const {static const uint64_t C = timeStamp().time_since_epoch().count(); return xs(hash<T> {}(x) + C);}};
template<typename T>
struct lichao_on_points {
static constexpr T inf = numeric_limits<T>::max();
uint a, U;
vec<T> bl, br;
vec<T> vk, vb;
lichao_on_points(vec<T> points) {
if (points.empty()) points = {0};
unify(points);
a = points.size();
U = geq_pow2(a);
bl.resize(U * 2);
br.resize(U * 2);
vk.resize(U * 2);
vb = vec<T>(U * 2, inf);
for (uint q = 0; q < a; ++q) bl[U + q] = br[U + q] = points[q];
for (uint q = a; q < U; ++q) bl[U + q] = br[U + q] = points[a - 1];
for (int q = U; --q; ) {
bl[q] = bl[q << 1];
br[q] = br[q << 1 | 1];
}
}
void add_seg(T ql, T qr, T k, T b, uint v) {
const T l = bl[v], r = br[v];
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) {
add_line(k, b, v);
return;
}
add_seg(ql, qr, k, b, v << 1);
add_seg(ql, qr, k, b, v << 1 | 1);
}
void add_seg(T ql, T qr, T k, T b) {add_seg(ql, qr, k, b, 1);}
void add_line(T k, T b, uint v) {
for (;;) {
const T l = bl[v], r = br[v];
T vl_cur = vk[v] * l + vb[v];
T vr_cur = vk[v] * r + vb[v];
T vl_new = k * l + b;
T vr_new = k * r + b;
if ((vl_cur <= vl_new) == (vr_cur <= vr_new)) {
if (vl_new < vl_cur) vk[v] = k, vb[v] = b;
return;
}
T md = br[v << 1];
T vmd_cur = vk[v] * md + vb[v];
T vmd_new = k * md + b;
if (vmd_new < vmd_cur) {
swap(vk[v], k), swap(vb[v], b);
swap(vl_cur, vl_new);
}
v = vl_new < vl_cur ? v << 1 : v << 1 | 1;
}
}
void add_line(T k, T b) {add_line(k, b, 1);}
T get_min(T x) {
uint v = 1;
T o = vk[v] * x + vb[v];
while (v < U) {
v <<= 1;
v += x > br[v];
chmin(o, vk[v] * x + vb[v]);
}
return o;
}
};
int main() {
fast;
int a, z; cin >> a >> z;
vec<array<ll, 4>> segs(a);
for (int q = 0; q < a; ++q) {
for (int w = 0; w < 4; ++w) cin >> segs[q][w];
}
vec<array<ll, 5>> que(z);
ll t, k, b;
vec<ll> pts;
pts.reserve(z);
for (int q = 0; q < z; ++q) {
cin >> que[q][0];
if (que[q][0] == 0) {
cin >> que[q][1] >> que[q][2] >> que[q][3] >> que[q][4];
} else {
cin >> que[q][1];
pts.pb(que[q][1]);
}
}
lichao_on_points<ll> kek(pts);
for (auto& [l, r, k, b] : segs) kek.add_seg(l, r - 1, k, b);
for (int q = 0; q < z; ++q) {
if (que[q][0] == 0) {
kek.add_seg(que[q][1], que[q][2] - 1, que[q][3], que[q][4]);
} else {
ll res = kek.get_min(que[q][1]);
if (res == numeric_limits<ll>::max()) cout << "NO\n";
else cout << res << "\n";
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 281ms
memory: 36912kb
input:
200000 200000 -999998847 -564701 0 0 -999993210 -562917 1 573969 -999989880 -560888 2 1147938 -999978625 -556992 3 1721907 -999976497 -554201 4 2295876 -999970456 -549858 5 2869845 -999961708 -549366 6 3443814 -999955817 -540635 7 4017783 -999950965 -539043 8 4591752 -999948875 -537042 9 5165721 -99...
output:
NO NO -50183563496000 -42956317210716 -49932020483680 3156971371995 -4205699747460 -50012287547303 161201413663722 127620184662654 -38152414490346 -6875394617322 -49441462985560 -10483501086163 -46614758184768 -7756362089800 150282043411500 1349780114496 107332409877630 6247978807520 45244266232880 ...
result:
ok 200000 lines
Test #2:
score: 0
Accepted
time: 303ms
memory: 26928kb
input:
200000 200000 -471243687 508625098 391807640 -342283806983648705 -340210383 47829053 -391880620 240209487116192693 -274545508 770445695 616772252 -144712167052367176 -880188114 -308896220 -693352586 -29355468444432145 381012675 658211153 -277370657 -223335522481190637 -695379495 -366915786 916546493...
output:
-1397453600647334843 -1029976041695367028 -1052910313176684616 -1818408630134327681 -1209457358134828750 -1718397108261908307 -1355662362476717627 -1314910767061006651 -1106268941848967229 -1898224683466047425 -1657509250418930516 -1221436786841522225 -1155460525928842979 -1903550645895237593 -14152...
result:
ok 100335 lines
Test #3:
score: 0
Accepted
time: 332ms
memory: 26932kb
input:
200000 200000 -735295803 194740970 -863012076 -698790457051536473 -561484685 878894370 -765835546 -885917094660675427 -28147679 -16062512 483876049 516657482726369446 -429018489 295071279 131635136 176429380546917807 227945873 812402553 -271742271 840365646909653826 -834426713 586084304 -547529179 9...
output:
-1664569700711813373 -1053333531588024159 -1000491242308628672 -1733677560351050737 -1609398765293517656 -1328984616378576478 -1129160009603686487 -1588136817928450256 -1060123157746468129 -1738321946600932313 -1778468400542602960 -1436283563532364758 -1569612247881992970 -1086963267195631293 -13664...
result:
ok 99748 lines
Test #4:
score: 0
Accepted
time: 322ms
memory: 27312kb
input:
200000 200000 -317847977 525536138 -997971963 128013476466794548 -548036883 337160985 -145974075 -195700861334636300 -724867754 -641003610 -760696431 -359739374654262877 -601681719 -64013647 216235416 -9458860324088657 -869002669 -536458711 -879969477 -267325832619409885 -887381150 -769771700 -32115...
output:
-1791119671831542466 -1562381666739252256 -1454944338598593191 -1100019661714702943 -1358372216736681172 -1196772147857670480 -1031894514403881624 -1446980382657653744 -1184499370667032484 -1123815059406541220 -1444259966996486892 -1076651931585643352 -1429556580885548952 -1910634429451024811 -12333...
result:
ok 100148 lines
Test #5:
score: 0
Accepted
time: 219ms
memory: 22728kb
input:
127669 148779 -471243687 508625098 391807640 -342283806983648705 -340210383 47829053 -391880620 240209487116192693 -274545508 770445695 616772252 -144712167052367176 -880188114 -308896220 -693352586 -29355468444432145 381012675 658211153 -277370657 -223335522481190637 -695379495 -366915786 916546493...
output:
-1116303818668273275 -1122282748919053950 -1833076145009619469 -1735834163503511299 -1154226917746696725 -1201176061522101225 -1419810711107983900 -1001069231171665854 -1865049592010438359 -1784695455689716511 -1902466130932019738 -1644603386432638268 -1213091162572113800 -1640076278676242796 -14316...
result:
ok 74399 lines
Test #6:
score: 0
Accepted
time: 235ms
memory: 23036kb
input:
150763 148757 -16062512 483876049 742203046 65718231886186737 -114582987 468042711 -913913563 484150211974036615 -448333502 614182218 6577596 -769509849750146393 -710428914 -12354532 497635710 -832906464305757785 -535251031 179614260 -876417353 -806315550178417183 273278837 819733107 -16863556 -7702...
output:
-1134246418002297778 -1465564391209986828 -1088160987472810573 -1570526469596326480 -1599782607445546091 -1391396854062745537 -1094227098401654868 -1732581002225039158 -1419213672956631064 -1945542854966153034 -1606933085452044102 -1304099061249812329 -1905766620229885408 -1578925235477621434 -16365...
result:
ok 74372 lines
Test #7:
score: 0
Accepted
time: 115ms
memory: 14716kb
input:
53336 120203 -997971963 362716733 185423412 -591863682353019904 -548036883 337160985 -145974075 -195700861334636300 -724867754 -641003610 -760696431 -359739374654262877 -601681719 -64013647 216235416 -9458860324088657 -869002669 -536458711 -879969477 -267325832619409885 -887381150 -769771700 -321150...
output:
-1345717484828710015 -1726377225131443611 -1277221842319302387 -1007424626087587316 -1071450544923448652 -1817571882869709507 -1343270791876712432 -1185495743769574829 -1602645704311705269 -1894895849331568810 -1200016566648933802 -1737725631579439522 -1882471460149418657 -1648128295693233892 -17306...
result:
ok 60105 lines
Test #8:
score: 0
Accepted
time: 0ms
memory: 3720kb
input:
11 1 -735559617 -340210383 47829053 240209487116192693 -274545508 770445695 616772252 -144712167052367176 -880188114 -308896220 -693352586 -29355468444432145 381012675 658211153 -277370657 -223335522481190637 -695379495 -366915786 916546493 655754885105439646 -992781513 -138210814 218118434 -3668951...
output:
result:
ok 0 lines
Test #9:
score: 0
Accepted
time: 2ms
memory: 3692kb
input:
6 11 -863012076 114022823 -561484685 -657406391247853790 -765835546 202841757 -28147679 -46121383578455600 483876049 742203046 648085233 -186557943001226187 -429018489 295071279 131635136 176429380546917807 227945873 812402553 -271742271 840365646909653826 -834426713 586084304 -547529179 97833598029...
output:
-637969271526783450 205210645209839855 -51177108112758140 754353035458004034 212402477421334639 -841298371968942545 -911432331322952525 204584401844401007 203868492836643311 -679313538246707630
result:
ok 10 lines
Extra Test:
score: 0
Extra Test Passed