QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#603340 | #9433. Trails | karito# | TL | 1084ms | 48804kb | C++17 | 2.9kb | 2024-10-01 16:00:39 | 2024-11-08 13:39:32 |
Judging History
answer
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
class xds {
private:
struct node {
node* lc, * rc;
int mx;
~node()
{
delete lc;
delete rc;
}
};
node* _build(int l, int r)
{
if (r == l + 1)
return new node{ nullptr,nullptr,0 };
int mid = (l + r) / 2;
return new node{ _build(l,mid),_build(mid,r),0 };
}
void chg(node* rt,int l, int r, int p, int x)
{
if (r <= x || l > x)
return;
if (r == l + 1)
{
rt->mx = x;
return;
}
int mid = (l + r) / 2;
chg(rt->lc, l, mid, p, x), chg(rt->rc, mid, r, p, x);
rt->mx = max(rt->lc->mx, rt->rc->mx);
}
int query(node* rt, int l, int r, int left, int right)
{
if (l >= right || r <= left)
return 0;
if (l <= left && r >= right)
return rt->mx;
int mid = (l + r) / 2;
return max(query(rt->lc, l, mid, left, right), query(rt->rc, mid, r, left, right));
}
node* root;
int left, right;
public:
void build(int l, int r)
{
left = l, right = r;
root = _build(l, r);
}
void chg(int p, int x)
{
chg(root, left, right, p, x);
}
int query(int l, int r)
{
return query(root, left, right, l, r);
}
~xds()
{
delete root;
}
};
int lowbit(int x)
{
return x & -x;
}
const int N = 1e6 + 10;
int tr[N];
void update(int x, int c,int siz)
{
x++;
for (int i = x; i <= siz; i += lowbit(i))
tr[i] = max(tr[i], c);
}
int query(int x)
{
int ans = 0;
x++;
if (x <= 0) return 0;
for(int i=x;i;i-=lowbit(i))
ans=max(ans,tr[i]);
return ans;
}
void clear(int siz)
{
for(int i=1;i<=siz;i++) tr[i]=0;
}
void work();
int main()
{
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--)
work();
return 0;
}
vector<int> pos[1000010];
bool cmp(const pair<int, int>& x, const pair<int, int>& y)
{
if (x.first == y.first)
return x.second > y.second;
return x.first < y.first;
}
void work()
{
long long n, p, q;
cin >> n >> p >> q;
vector<pair<int, int>> nod;
for (int i = 0; i < n; i++)
{
pair<int, int>x;
cin >> x.first >> x.second;
if (x.first < 0 || x.first >= p || x.second < 0 || x.second >= q)
continue;
nod.push_back(x);
}
sort(nod.begin(), nod.end(),cmp);
//xds tr;
clear(q + 5);
vector<int> ct;
int mxt = 0;
//vector<pair<int, int>> tmp;
for (auto i:nod)
{
int t = query(i.second-1) + 1;
ct.push_back(t);
update(i.second, t, q + 5);
mxt = max(mxt, t);
}
for (int i = 0; i <= mxt; i++)
pos[i].clear();
for (int i = 0; i < nod.size(); i++)
pos[ct[i]].push_back(i);
long long sm = 0;
for (int i = 0; i <= mxt; i++)
{
long long bef = q;
for (auto j : pos[i])
{
if (nod[j].second >= bef)
continue;
sm += (p - nod[j].first) * (bef - nod[j].second);
bef = nod[j].second;
}
}
cout << (p + q) * (p + 1) * (q + 1) / 2 - sm << '\n';
}
詳細信息
Test #1:
score: 100
Accepted
time: 6ms
memory: 27848kb
input:
2 3 2 4 1 1 0 2 0 0 1 100 100 1000 1000
output:
34 1020100
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 530ms
memory: 31076kb
input:
6116 19 403875 4598 244446 658406 439472 600614 831502 516732 471917 520839 453020 604310 42306 699481 376843 270708 67164 501987 534254 381735 584472 43380 425780 946800 208487 272200 737998 300759 454500 397309 837634 156713 293648 671302 597485 524248 698078 141688 389057 265668 10 268299 760142 ...
output:
379354128879726 104873326525021424 105606787645824723 708210768663783512 132912961393461646 202868704323232157 142763396656757487 31220157133721509 183522976883097753 60792387857469878 54087773825760948 13028977926188800 397834145111696233 64443345446763396 102402202407373004 24578007805918476 22181...
result:
ok 6116 lines
Test #3:
score: 0
Accepted
time: 839ms
memory: 34740kb
input:
6116 19 712953 722736 5686 60810 377083 350609 535028 763626 550340 834947 993495 995201 989872 934913 314598 292101 362688 320197 805489 860814 194143 73963 832924 870115 498063 456534 603643 839328 249060 131022 740139 845556 865334 928800 504864 499431 472982 433077 852053 894291 2 830795 685574 ...
output:
369887957086041723 431841334366294875 308477305320984605 613664386014754638 357826753561485272 338658347975033029 426142209172666186 759666649386109551 378494587050071809 306219137754076618 607898503543409988 743634628947627450 223491301887405615 360966639876096830 398616574824535225 504497791642527...
result:
ok 6116 lines
Test #4:
score: 0
Accepted
time: 1084ms
memory: 33284kb
input:
6116 7 1000000 1000000 412334 537125 550637 537125 846976 462055 130053 462055 263751 537125 274893 462055 48620 537125 13 1000000 1000000 564915 923124 203670 765136 621916 339636 331226 448765 396601 765136 255282 50583 429851 339636 654810 339636 138494 448765 186497 448765 282100 50583 233299 50...
output:
1000001153532805335 1000000582954982857 1000001615181949269 1000001997185373760 1000001544547212292 1000001400049627238 1000000981793279458 1000000923184555598 1000001037042229556 1000001839767792582 1000001053880830252 1000000549232039823 1000000783602725738 1000001955176278477 1000000400154228860 ...
result:
ok 6116 lines
Test #5:
score: 0
Accepted
time: 150ms
memory: 36632kb
input:
1 1000000 342269 953012 473985 235501 917204 100230 756706 510618 768364 407348 931604 127659 853933 179476 909155 968310 769785 680886 622841 228543 239160 97618 294588 675503 571602 81210 676816 615217 367042 405009 284074 735031 900597 770465 994923 433364 468269 645505 595488 277488 52201 87303 ...
output:
211091849789153155
result:
ok single line: '211091849789153155'
Test #6:
score: 0
Accepted
time: 163ms
memory: 42984kb
input:
1 865193 617749 536531 577306 577305 334144 333316 218524 217512 409600 408899 924088 923692 510522 510309 722200 721676 872779 872541 292233 291306 501418 501237 893308 892862 972243 972077 37933 37174 848551 848469 977272 977132 443974 443592 639095 638462 333157 332325 961099 960942 828150 828081...
output:
158737140297421602
result:
ok single line: '158737140297421602'
Test #7:
score: 0
Accepted
time: 164ms
memory: 44736kb
input:
1 864322 865792 550280 959602 959616 758897 759684 150506 150749 418888 419528 804075 804410 65213 65455 212385 213207 486540 486928 484647 485135 811196 811450 893947 894330 863384 863748 475776 476396 500216 500597 396442 396999 582180 582559 730649 731072 481286 481826 230484 231253 775303 775991...
output:
283982082132780416
result:
ok single line: '283982082132780416'
Test #8:
score: 0
Accepted
time: 261ms
memory: 48428kb
input:
1 1000000 1000000 1000000 623164 107113 623164 948418 667542 261951 667542 516385 667542 586519 667542 330574 667542 496932 667542 11259 623164 188794 623164 598328 667542 860430 623164 909263 667542 134671 667542 241963 667542 130855 667542 639700 623164 237591 623164 835427 623164 492063 667542 40...
output:
1000001290708086130
result:
ok single line: '1000001290708086130'
Test #9:
score: 0
Accepted
time: 232ms
memory: 48804kb
input:
1 1000000 1000000 1000000 148005 130246 22954 694549 701374 844290 273280 844290 819874 615667 258850 844290 740006 615667 755675 844290 437784 694549 927035 615667 240736 694549 969223 694549 928325 662804 52986 130246 395176 694549 717785 694549 859887 615667 648063 130246 910409 130246 863155 662...
output:
999999947571940219
result:
ok single line: '999999947571940219'
Extra Test:
score: -3
Extra Test Failed : Time Limit Exceeded on 2
input:
1000000 1 1000000 1000000 814907 135507 1 1000000 1000000 905995 835196 1 1000000 1000000 127015 969086 1 1000000 1000000 913581 221083 1 1000000 1000000 632501 308236 1 1000000 1000000 97562 547343 1 1000000 1000000 278560 188424 1 1000000 1000000 547004 993104 1 1000000 1000000 957722 996685 1 100...
output:
1000001839989397151 1000001984508599980 1000001973013541710 1000001932687771777 1000001745778421764 1000001591506122234 1000001414497610560 1000001996877139584 1000001999860848430 1000001998881289240 1000001769198236704 1000001999456041370 1000001962066121548 1000001896215405060 1000001859743535840 ...