QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#736844 | #9613. 计算几何 | hos_lyric# | 20 | 3449ms | 209844kb | C++14 | 3.5kb | 2024-11-12 13:39:05 | 2024-11-12 13:39:06 |
Judging History
answer
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using Int = long long;
template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")
constexpr Int INF = 1001001001001001001LL;
void bChmin(vector<Int> &bit, int pos, Int val) {
const int bitN = bit.size();
for (int x = pos; x < bitN; x |= x + 1) chmin(bit[x], val);
}
Int bMin(const vector<Int> &bit, int pos) {
Int ret = INF;
for (int x = pos; x > 0; x &= x - 1) chmin(ret, bit[x - 1]);
return ret;
}
int N, Q;
vector<Int> A, B;
vector<int> L, R;
Int dist(int u, int v) {
return abs(A[u] - A[v]) + abs(B[u] - B[v]);
}
/*
pair<int, int> closest(int l, int r) {
Int mn = INF;
int um = -1, vm = -1;
for (int u = l; u < r; ++u) for (int v = u + 1; v < r; ++v) {
if (chmin(mn, dist(u, v))) {
um = u;
vm = v;
}
}
return make_pair(um, vm);
}
*/
pair<int, int> closest(int l, int r) {
vector<pair<Int, int>> aus(r - l);
for (int u = l; u < r; ++u) aus[u - l] = make_pair(A[u], u);
sort(aus.begin(), aus.end());
Int mn = INF;
int um = -1, vm = -1;
for (int i = 0; i < r - l; ++i) {
const int u = aus[i].second;
for (int j = i; --j >= 0; ) {
const int v = aus[j].second;
if (mn <= A[u] - A[v]) break;
if (chmin(mn, dist(u, v))) {
um = u;
vm = v;
}
}
}
return make_pair(um, vm);
}
vector<vector<int>> vss;
void rec(int l, int r) {
if (r - l >= 2) {
const auto res = closest(l, r);
int u = res.first, v = res.second;
if (u > v) swap(u, v);
vss[u].push_back(v);
rec(l, v);
rec(u + 1, r);
}
}
int main() {
for (; ~scanf("%d%d", &N, &Q); ) {
A.resize(N);
B.resize(N);
for (int u = 0; u < N; ++u) {
scanf("%lld%lld", &A[u], &B[u]);
}
L.resize(Q);
R.resize(Q);
for (int q = 0; q < Q; ++q) {
scanf("%d%d", &L[q], &R[q]);
--L[q];
}
vss.assign(N, {});
rec(0, N);
vector<vector<int>> qss(N);
for (int q = 0; q < Q; ++q) qss[L[q]].push_back(q);
vector<Int> ans(Q, INF);
vector<Int> bit(N, INF);
for (int u = N; --u >= 0; ) {
for (const int v : vss[u]) {
bChmin(bit, v, dist(u, v));
}
for (const int q : qss[u]) {
ans[q] = bMin(bit, R[q]);
}
}
for (int q = 0; q < Q; ++q) {
printf("%lld\n", ans[q]);
}
}
return 0;
}
详细
Pretests
Final Tests
Test #1:
score: 4
Accepted
time: 24ms
memory: 5220kb
input:
2000 2000 983850330 731103020 513263912 234227610 788795134 228585831 -983909940 -814082030 -582261039 729875680 617950974 -259602422 -355311469 355769341 -394119311 -493842356 899026446 -402238603 -300533665 433674923 946553927 26786776 46270288 43713228 -838909861 427788951 863776211 691106038 -93...
output:
511457 511457 1660620 25525096 1660620 511457 9525149 57819607 1660620 1660620 511457 1660620 511457 511457 1660620 7013046 511457 1660620 7013046 1660620 1660620 511457 3297708 1660620 1660620 3297708 1660620 1660620 1660620 3297708 4830700 8953781 511457 511457 1660620 1660620 1660620 8953781 5114...
result:
ok 2000 numbers
Test #2:
score: 4
Accepted
time: 21ms
memory: 6084kb
input:
2000 2000 407439483 0 -924180082 0 534637753 0 -836707453 0 -385278990 0 90204634 0 454360393 0 -895242427 0 -112231538 0 -323497705 0 368203671 0 -124641980 0 183953551 0 596609116 0 666423112 0 706701157 0 988299741 0 -248457324 0 -507127215 0 610030981 0 356918300 0 110156240 0 317203493 0 754544...
output:
1043672 417 1362 417 1362 1362 417 6857 417 2658 90109 1021 417 2658 269047 2241 2241 417 417 2658 2658 417 417 14980 1362 1362 90109 1362 56414 1021 207612 2658 1021 417 417 1362 1362 417 417 1021 1362 40782 417 1362 1021 417 417 417 2241 6857 1021 1021 417 2658 1021 417 1362 417 417 417 417 1362 4...
result:
ok 2000 numbers
Test #3:
score: 0
Time Limit Exceeded
input:
20000 20000 -721847248 671834627 -750033826 -893098471 358123311 740735694 -15749050 352553172 331628828 285387115 -870680297 30680547 747479743 495644671 -24785538 458380663 -49052185 540025540 192115219 694762799 -582891748 -643029079 -356894103 726491498 213744952 457769371 -357728988 745592631 -...
output:
result:
Test #4:
score: 0
Time Limit Exceeded
input:
20000 20000 -856287 613193 884980 313749 -51917 -595036 -515889 732611 768011 201825 685038 -690361 -825296 610210 693313 378198 153998 -220528 -881367 -427847 -762386 726194 -882783 -396975 -585188 -646369 852468 -769564 845740 446417 -272832 806448 -23829 -843528 -290649 -509815 183302 929309 -810...
output:
result:
Test #5:
score: 0
Time Limit Exceeded
input:
20000 20000 272933 -400117 36074 -350576 -180416 245927 -152816 -532917 -815869 -121672 900928 561561 696604 -34106 281988 -30073 37999 -748187 -260504 367199 -254538 984542 -929979 -597816 735632 -731486 -88688 -820300 -180173 516379 319782 -306180 461815 88179 -863913 497662 -972928 920984 670858 ...
output:
result:
Test #6:
score: 0
Time Limit Exceeded
input:
20000 20000 961714 0 -256591 0 858025 0 302536 0 989232 0 921482 0 132252 0 -687494 0 976712 0 584368 0 -379471 0 -368374 0 -421478 0 -269707 0 -840836 0 683604 0 -233785 0 -509259 0 691924 0 -326966 0 699666 0 -602646 0 -394566 0 -762188 0 -721221 0 110375 0 123249 0 -679471 0 476495 0 -247891 0 -6...
output:
result:
Test #7:
score: 4
Accepted
time: 3449ms
memory: 209844kb
input:
20000 20000 931651 0 -193344 0 -459921 0 -208681 0 265915 0 221047 0 -976889 0 836902 0 -128302 0 775194 0 523077 0 -398264 0 296667 0 -324286 0 477274 0 226741 0 -70369 0 627346 0 -81394 0 525865 0 454142 0 708462 0 -629738 0 -171617 0 -745312 0 -647420 0 -249238 0 -911374 0 255729 0 565402 0 -3974...
output:
1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 5 227 0 0 0 0 0 0 1 3 0 0 0 0 0 0 1 41 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 18 0 0 0 0 0 0 0 0 18 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 52 0 0 0 0 0 0 0 0 0 0 0 306 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 ...
result:
ok 20000 numbers
Test #8:
score: 0
Time Limit Exceeded
input:
20000 20000 286328653 0 -436132873 0 -950502327 0 62507734 0 410183824 0 -244422860 0 -89619254 0 -36224025 0 987264815 0 -366170043 0 789288990 0 595133547 0 129243363 0 480765515 0 -367270251 0 85317458 0 -717834130 0 990039646 0 601945059 0 979377776 0 487802144 0 -543661591 0 -649863532 0 530289...
output:
result:
Test #9:
score: 0
Time Limit Exceeded
input:
200000 200000 -412960500 577830338 99802584 -136950865 -950307156 -859369040 793568959 -565815756 411737945 -479377622 569675957 -601905445 -417176412 -729638186 200119881 -430545998 -86043427 969867029 64175162 -427861527 83451953 -756750354 -748032722 43908052 418515829 494502750 346664686 9215021...
output:
result:
Test #10:
score: 0
Time Limit Exceeded
input:
200000 200000 215020 -29462 152216 -199822 -604632 -191567 10263 -830451 -89159 -121408 -881329 -921244 -809798 -903639 29060 -438373 -393896 -438778 79484 803288 646060 323407 -150152 23631 -509647 -88435 -772163 923612 -832132 -270978 650123 -731403 997559 -457855 797171 863407 366847 -915734 -700...
output:
result:
Test #11:
score: 0
Time Limit Exceeded
input:
200000 200000 -814016 -440530 -988229 -214220 -825745 -268031 808279 -507843 -365671 559807 -823503 84191 685041 -755331 -379355 -288337 -730097 156308 -49982 -920817 135131 710420 786978 14054 -877243 607279 -61488 -541803 839910 -778520 498514 -990675 408344 758599 -596998 201097 -711216 615872 60...
output:
result:
Test #12:
score: 0
Time Limit Exceeded
input:
200000 200000 492262 0 767261 0 -49558 0 763447 0 -766015 0 305219 0 216950 0 309815 0 -563799 0 -576993 0 807708 0 -28765 0 805496 0 -792510 0 452313 0 636912 0 251743 0 367464 0 460580 0 731290 0 -899643 0 35424 0 900164 0 -627830 0 -200278 0 -364485 0 85580 0 348513 0 -445170 0 782325 0 867546 0 ...
output:
result:
Test #13:
score: 0
Time Limit Exceeded
input:
200000 200000 547911 0 477311 0 650541 0 -105453 0 626756 0 -374148 0 -185598 0 -740854 0 845506 0 692548 0 -87545 0 -338111 0 -672163 0 348336 0 790086 0 588112 0 874537 0 -165894 0 602594 0 -951962 0 121709 0 597190 0 -231436 0 954727 0 874009 0 923477 0 176425 0 -953583 0 107836 0 -354119 0 80494...
output:
result:
Test #14:
score: 0
Time Limit Exceeded
input:
200000 200000 -317746997 0 -151278487 0 231239102 0 -333682162 0 817071806 0 778079717 0 -29317929 0 -796844681 0 -969298078 0 -290624098 0 -687507332 0 967855359 0 -200682268 0 446953365 0 829160344 0 431722814 0 -321478842 0 500793767 0 -958916933 0 -993173724 0 -583938136 0 -621654506 0 540155031...
output:
result:
Test #15:
score: 4
Accepted
time: 250ms
memory: 30056kb
input:
2000 1000000 600102029 78163345 623529642 -781629210 -194743627 856505922 132730843 -866898111 496967234 357290802 424803615 -817449125 326888043 973054140 682875209 743038131 659124372 893679753 -415512262 835204413 -753019068 -821982592 650486625 656222368 765610921 -158965479 -131326155 454415998...
output:
3681425 3248740 8287314 3248740 2994042 2591533 10623830 2994042 55536188 3248740 2591533 181013291 2591533 2591533 3248740 9585148 4922188 4587911 2591533 3248740 2994042 2994042 8443551 681466 21601433 2591533 2994042 2994042 2591533 2591533 681466 2591533 681466 3248740 681466 23886441 2994042 45...
result:
ok 1000000 numbers
Test #16:
score: 4
Accepted
time: 298ms
memory: 34612kb
input:
2000 1000000 172304227 0 104292738 0 -257051223 0 -21999534 0 -574879748 0 -574439539 0 -947027598 0 765205348 0 195088335 0 406074782 0 75136395 0 227990070 0 900067610 0 675451839 0 804606264 0 556516588 0 -511265459 0 510580926 0 863647316 0 807267358 0 -778168632 0 127848817 0 255183075 0 -60073...
output:
169 993 169 98 12442 10743 736 10743 736 12442 12442 993 993 2714 736 98 27403 736 12442 1624037 98 993 10743 736 12442 10743 98 19028 736 736 2714 12442 173 993 2714 169 2714 76324 116236 736 2714 173 993 993 993 10743 10743 10743 993 307731 993 98 98 2714 993 99994 72535 98 736 736 12442 736 13587...
result:
ok 1000000 numbers
Test #17:
score: 0
Time Limit Exceeded
input:
1000000 10 156999516 -24390575 -347759760 638897014 -102812461 325031686 668597244 262829264 678216489 165516603 621656879 -412885032 233438419 931865318 709921083 -313209071 389603839 76036576 -769757796 359645480 -100357260 928717563 709905946 839359128 233518030 -695740543 524417586 -804059937 -4...
output:
result:
Test #18:
score: 0
Time Limit Exceeded
input:
1000000 10 281115 207197 -791397 227390 -769663 849805 -689936 477469 -251524 174662 189816 721806 -579178 -339234 993809 -705268 -690664 35222 -298116 -663820 -321165 -327572 -609151 166540 799070 -156124 -305786 89239 53446 -399972 845917 137485 316083 266638 -720291 -915315 -706115 135108 -161326...
output:
result:
Test #19:
score: 0
Time Limit Exceeded
input:
1000000 10 370517413 0 607064501 0 198217472 0 143369676 0 627031881 0 -242777381 0 -122948696 0 334651705 0 754835147 0 -975826131 0 -3570204 0 136544599 0 519231560 0 -21309928 0 -647797468 0 728822996 0 -239842256 0 854368498 0 -555223024 0 -177243458 0 -606866771 0 867321201 0 983555681 0 753390...
output:
result:
Test #20:
score: 0
Time Limit Exceeded
input:
1000000 1000000 -565158168 192228664 -60734026 -876227887 169956757 458933534 415705153 359751682 706646043 -267237804 -785235125 -286053701 -810363619 -883277015 -917766646 796218920 568429513 157525175 652148934 -563141041 101229780 387951397 138582181 234580165 989042915 303473055 848403115 67207...
output:
result:
Test #21:
score: 0
Time Limit Exceeded
input:
1000000 1000000 937028 -142721 470057 -596447 805603 -653737 422827 -146839 -134461 -284129 -740611 -822073 129788 -760939 189012 76048 -649576 825583 376935 955180 -675052 -614100 217445 -951905 463589 -489265 309830 -722532 510085 591599 -961137 67299 -817170 188112 338633 -558591 -571501 -205785 ...
output:
result:
Test #22:
score: 0
Time Limit Exceeded
input:
1000000 1000000 556639 -726845 488045 -320786 907001 -483744 941440 533716 -722534 856343 -338618 616639 491388 733720 -416677 107094 108121 465292 -123127 350855 657412 326868 -943626 -335813 -502533 257525 56288 -494808 -248448 -317412 463444 -822305 686331 178764 -255923 18808 -520494 -446761 624...
output:
result:
Test #23:
score: 0
Time Limit Exceeded
input:
1000000 1000000 -542377 0 80556 0 -734137 0 -588964 0 255112 0 598605 0 -363464 0 -703421 0 157594 0 -98285 0 799038 0 897889 0 -518690 0 -303647 0 -503359 0 166055 0 -173378 0 568761 0 -839895 0 -125384 0 -113615 0 -926581 0 -597497 0 865459 0 271137 0 779200 0 -589752 0 695449 0 -633220 0 477974 0...
output:
result:
Test #24:
score: 0
Time Limit Exceeded
input:
1000000 1000000 475716 0 733854 0 -670602 0 -495883 0 879413 0 -549166 0 395637 0 -922358 0 -95497 0 261093 0 -855001 0 -232761 0 839785 0 415412 0 456189 0 487755 0 951642 0 68750 0 -207887 0 108335 0 73919 0 -829879 0 -521857 0 -235996 0 -474559 0 50128 0 599195 0 -72168 0 454461 0 384522 0 -27507...
output:
result:
Test #25:
score: 0
Time Limit Exceeded
input:
1000000 1000000 -647194312 0 923266193 0 311967052 0 26202656 0 145325407 0 -363221031 0 322109698 0 400374410 0 -666477923 0 -803868087 0 -739610118 0 941620833 0 335162000 0 -343764277 0 -854360295 0 354763517 0 -559596318 0 -857042621 0 638986823 0 -794261929 0 137855671 0 317157550 0 942335473 0...