QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #342036 | #601. 李超树 | orz_z# | AC ✓ | 411ms | 53700kb | C++14 | 3.1kb | 2024-03-01 08:11:03 | 2024-03-01 08:11:05 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define Debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define int long long
#define F(i, l, r) for(int i = (l); i <= (r); ++i)
#define dF(i, r, l) for(int i = (r); i >= (l); --i)
int ri() {
int x = 0, f = 1;
char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
x = x* 10 + c - 48;
c = getchar();
} return x * f;
}
const int _ = 8e5 + 5;
//typedef long double db;
//const db eps = 1e-9;
struct Line {
int k, b;
} a[_ << 1];
int n, m, b[_ * 4], t, L[_], R[_], cnt;
struct qrt {
int op, l, r, a, b;
} qr[_];
int cmp(int a, int b) {
if(a > b) return 1;
else if(a < b) return -1;
return 0;
}
int tg[_ << 2];
int get(int Id, int x) {
return a[Id].k * x + a[Id].b;
}
void upd(int o, int l, int r, int u) {
int mid = (l + r) >> 1;
int &v = tg[o];
int w = cmp(get(u, b[mid]), get(v, b[mid]));
if(w == -1) swap(u, v);
if(l == r) return;
int wl = cmp(get(u, b[l]), get(v, b[l])), wr = cmp(get(u, b[r]), get(v, b[r]));
if(wl == -1) upd(o << 1, l, mid, u);
if(wr == -1) upd(o << 1 | 1, mid + 1, r, u);
}
void update(int o, int l, int r, int L, int R, int Id) {
if(L <= l && r <= R) return upd(o, l, r, Id);
int mid = (l + r) >> 1;
if(L <= mid) update(o << 1, l, mid, L, R, Id);
if(R > mid) update(o << 1 | 1, mid + 1, r, L, R, Id);
}
pair<int, int> pmax(pair<int, int> a, pair<int, int> b) {
if(a.first < b.first) return a;
else if(a.first > b.first) return b;
return a;
}
pair<int, int> qry(int o, int l, int r, int p) {
if(l == r) return make_pair(get(tg[o], b[l]), tg[o]);
int mid = (l + r) >> 1;
// Debug("%d, %d, %d\n", tg[o], a[tg[o]].k, a[tg[o]].b);
return pmax(make_pair(get(tg[o], b[p]), tg[o]), (p <= mid ? qry(o << 1, l, mid, p) : qry(o << 1 | 1, mid + 1, r, p)));
}
signed main() {
Debug("llongmax = %lld\n", LLONG_MAX);
n = ri(), m = ri();
a[0].k = 0, a[0].b = 2000000000000000000ll + 1;
F(i, 1, n) {
L[i] = ri(), R[i] = ri() - 1;
scanf("%lld%lld", &a[i].k, &a[i].b);
b[++t] = L[i], b[++t] = R[i];
}
F(i, 1, m) {
qr[i].op = ri(), qr[i].l = ri();
if(qr[i].op == 0) qr[i].r = ri() - 1, qr[i].a = ri(), qr[i].b = ri(), b[++t] = qr[i].l, b[++t] = qr[i].r;
else b[++t] = qr[i].l;
}
sort(b + 1, b +t + 1);
t = unique(b + 1, b + t + 1) - b - 1;
F(i, 1, n) L[i] = lower_bound(b + 1, b + t + 1, L[i]) - b, R[i] = lower_bound(b + 1, b + t + 1, R[i]) - b;
F(i, 1, m) {
qr[i].l = lower_bound(b + 1, b + t + 1, qr[i].l) - b;
if(!qr[i].op) qr[i].r = lower_bound(b + 1, b + t + 1, qr[i].r) - b;
}
F(i, 1, n) update(1, 1, t, L[i], R[i], i);
cnt = n;
F(i, 1, m) {
if(qr[i].op == 0) {
a[++cnt].k = qr[i].a, a[cnt].b = qr[i].b;
update(1, 1, t, qr[i].l, qr[i].r, cnt);
continue;
}
pair<int, int> w = qry(1, 1, t, qr[i].l);
if(w.first == 2000000000000000000ll + 1) {
puts("NO");
continue;
}
printf("%lld\n", w.first);
}
}
/*
2 8
-3 3 -1 -1
0 7 0 1
1 -1
1 -2
1 0
1 2
0 -4 2 0 -10
1 -2
1 0
1 2
*/
詳細信息
Test #1:
score: 100
Accepted
time: 226ms
memory: 36188kb
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: 389ms
memory: 46480kb
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: 391ms
memory: 53496kb
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: 411ms
memory: 53700kb
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: 245ms
memory: 33664kb
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: 284ms
memory: 36992kb
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: 138ms
memory: 32492kb
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: 12108kb
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: 0ms
memory: 12020kb
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