QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#736844#9613. 计算几何hos_lyric#20 3449ms209844kbC++143.5kb2024-11-12 13:39:052024-11-12 13:39:06

Judging History

你现在查看的是最新测评结果

  • [2024-11-12 13:39:06]
  • 评测
  • 测评结果:20
  • 用时:3449ms
  • 内存:209844kb
  • [2024-11-12 13:39:05]
  • 提交

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...

output:


result: