QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#423147 | #8179. 2D Parentheses | complexor | WA | 170ms | 39256kb | C++23 | 2.9kb | 2024-05-27 21:18:08 | 2024-05-27 21:18:08 |
Judging History
answer
#include <bits/stdc++.h>
typedef long long LL;
typedef std::pair<int, int> pii;
#define MP std::make_pair
#define fi first
#define se second
int read()
{
int s = 0, f = 1;
char c = getchar();
while (!(c >= '0' && c <= '9'))
f ^= (c == '-'), c = getchar();
while (c >= '0' && c <= '9')
s = s * 10 + (c ^ 48), c = getchar();
return f ? s : -s;
}
const int MAXN = 400005;
struct Tuple
{
int x, y, z;
Tuple(int _x = 0, int _y = 0, int _z = 0)
: x(_x), y(_y), z(_z){}
friend bool operator<(Tuple t1, Tuple t2)
{ return t1.x != t2.x ? t1.x < t2.x : t1.y != t2.y ? t1.y < t2.y : t1.z < t2.z; }
} ;
struct Segment
{
int x, yl, yr, v;
Segment(){}
Segment(int _x, int _yl, int _yr, int _v)
: x(_x), yl(_yl), yr(_yr), v(_v) {}
} sg[MAXN << 1];
std::set<Tuple> rec;
int n, ans[MAXN], m = 0, yy[MAXN << 1], V;
int ida[MAXN], idb[MAXN];
pii a[MAXN], b[MAXN];
namespace BIT
{
int c[MAXN << 1] = {0};
void modify(int x, int v)
{
for (; x <= V; x += x & -x)
c[x] += v;
}
int query(int x)
{
int res = 0;
for (; x; x -= x & -x)
res += c[x];
return res;
}
int query(int l, int r) { return query(r) - query(l - 1); }
}
int getId(int y){ return std::lower_bound(yy + 1, yy + V + 1, y) - yy; }
int main()
{
n = read();
for (int i = 1; i <= n; i++) a[i].fi = read(), a[i].se = read();
for (int i = 1; i <= n; i++) b[i].fi = read(), b[i].se = read();
std::iota(ida + 1, ida + n + 1, 1);
std::iota(idb + 1, idb + n + 1, 1);
if (n <= 2) return printf("NO"), 0;
std::sort(ida + 1, ida + n + 1, [](int i, int j){ return a[i] > a[j]; });
std::sort(idb + 1, idb + n + 1, [](int i, int j){ return b[i] > b[j]; });
for (int i = 1, j = 1; i <= n; i++)
{
for (; j <= n && b[idb[j]].fi > a[ida[i]].fi; j++)
rec.emplace(b[idb[j]].se, b[idb[j]].fi, idb[j]);
auto it = rec.lower_bound(Tuple(a[ida[i]].se + 1, -1e9 - 1, 0));
if (it == rec.end()) return printf("No\n"), 0;
ans[ida[i]] = it->z;
yy[++V] = a[ida[i]].se, yy[++V] = it->x;
sg[++m] = Segment(a[ida[i]].fi, a[ida[i]].se, it->x, 1);
sg[++m] = Segment(it->y, a[ida[i]].se, it->x, -1);
rec.erase(it);
}
V = std::unique(yy + 1, yy + n * 2 + 1) - yy - 1;
std::sort(sg + 1, sg + m + 1, [](Segment a, Segment b){
if (a.x == b.x && a.v == b.v)
return a.v == -1 ? a.yr - a.yl < b.yr - b.yl : a.yr - a.yl > b.yr - b.yl;
return a.x == b.x ? a.v < b.v : a.x < b.x;
});
for (int i = 1; i <= m; i++)
{
int l = getId(sg[i].yl), r = getId(sg[i].yr);
// printf("%d: %d %d %d %d %d\n", i, sg[i].x, sg[i].yl, sg[i].yr, sg[i].v, BIT::query(l + 1, r - 1));
if (sg[i].v == 1 && l < r && BIT::query(l + 1, r - 1) > 0)
return printf("No"), 0;
if (sg[i].v == -1 && l < r && BIT::query(l + 1, r - 1) > 0)
return printf("No\n"), 0;
BIT::modify(l, sg[i].v), BIT::modify(r, sg[i].v);
}
printf("Yes\n");
for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 12032kb
input:
3 0 0 2 -2 1 1 2 2 3 1 2 3
output:
Yes 3 2 1
result:
ok answer is YES, 3 tokens
Test #2:
score: 0
Accepted
time: 0ms
memory: 14032kb
input:
2 1 0 0 1 2 3 3 2
output:
NO
result:
ok answer is NO
Test #3:
score: 0
Accepted
time: 0ms
memory: 13984kb
input:
1 1 1 0 0
output:
NO
result:
ok answer is NO
Test #4:
score: 0
Accepted
time: 155ms
memory: 28652kb
input:
199996 94702923 895749121 -830347683 823853414 -638337012 -528381915 774504965 -903560893 465975432 931026841 47062323 901390864 539345338 830099354 278774201 896803047 -445303873 568413124 80473317 828648317 804283391 -307873779 543648687 893783688 814084625 -664894626 169476937 -999435847 -8232728...
output:
Yes 21701 88398 59327 146960 29196 103293 198434 198023 157367 48765 157321 148908 80650 112519 196489 172199 173973 5551 141927 136548 134111 182366 59175 165032 163355 57765 5843 31857 130090 185365 76890 97333 133685 142517 167272 4006 171963 1988 107334 183071 65560 70618 199137 151179 183975 10...
result:
ok answer is YES, 199996 tokens
Test #5:
score: 0
Accepted
time: 150ms
memory: 26152kb
input:
199989 -185038489 939943355 404432727 -854751373 554853823 193640691 301504969 -998071590 274900356 938454158 -432464517 285421885 405518801 -987371480 571222708 909692099 -759427030 -999520045 869336666 847296633 -622724138 -999895334 -54035108 -876650516 453457981 -842759465 892363710 -794270574 1...
output:
Yes 29051 42308 37337 84855 166499 109338 34862 199409 32310 182823 20620 177599 116234 29219 168881 98498 20908 64603 145113 95741 106479 41666 136146 57568 153800 159627 73275 187439 74915 2272 25123 152755 131852 155786 59824 193752 26923 55748 13026 132594 87769 26528 189799 148030 136086 143680...
result:
ok answer is YES, 199989 tokens
Test #6:
score: 0
Accepted
time: 160ms
memory: 26100kb
input:
199991 -900159443 -671207779 -114175529 -885513466 -57386301 392144414 623068349 -990207451 -466916252 -379159070 -390577839 868367620 -142964637 -583431492 -288979694 -899596387 -357113786 867092775 833205097 992058046 -885274285 951889875 -406261261 872434960 -99080436 889619788 -37516399 -2293017...
output:
Yes 3275 63270 93912 127141 22479 165152 198171 26948 80966 36189 160851 192441 14819 41768 118467 117142 19608 136232 104951 109409 47223 99091 151706 110331 54762 66016 16120 166582 89823 77684 49744 74404 47622 182252 83554 97967 190281 111679 20281 17322 79190 103090 116209 40445 137659 13013 24...
result:
ok answer is YES, 199991 tokens
Test #7:
score: 0
Accepted
time: 151ms
memory: 26544kb
input:
199987 -46649274 139363612 803504473 -487067218 -231304341 961630672 807256898 -256192650 -473216529 -412520640 387331113 961360032 -718008950 -1000000000 156200839 95571209 981893716 -29439313 -470730442 -783533869 799296462 104576693 -553698761 -906790634 807374303 -24023479 309903544 968199523 32...
output:
Yes 108253 39856 69761 52978 95487 52526 165960 5834 154779 176120 98055 116863 185474 199758 158834 7618 59391 94556 148087 135584 103212 46150 11774 57061 193721 73508 53857 107232 28635 11110 92043 112059 176064 91995 182180 157770 164760 94634 170392 57167 64585 147769 177684 141597 196364 5163 ...
result:
ok answer is YES, 199987 tokens
Test #8:
score: 0
Accepted
time: 152ms
memory: 26556kb
input:
199998 520404957 315206955 589123511 -430859516 376860728 -987316121 614664700 -301663049 978007244 -969619964 636107820 259251657 137671843 -958442271 549117430 -935982467 341044573 -957188402 920491566 768041266 584917074 -822386658 170473403 -165076605 528955497 239159653 608627148 -761435336 294...
output:
Yes 82347 108348 69489 26272 38797 5634 171949 36739 168135 91411 33031 55676 52141 104041 168253 25828 64027 133931 106943 41392 145594 100287 149043 92143 168786 81236 24112 157854 150937 77525 2953 98374 15882 5118 86665 187254 96225 44878 26976 116891 140926 67595 136505 12406 158887 133562 1802...
result:
ok answer is YES, 199998 tokens
Test #9:
score: 0
Accepted
time: 162ms
memory: 30440kb
input:
199993 -751151977 -533994506 -927773836 -32372872 56850331 -243441225 327514682 -361038889 247003430 -838950588 -981662694 -566754857 -57613101 -102410474 857750386 -993733474 184906291 -664905204 -479853877 -891755682 851112690 -967524478 -597827988 -230528151 -782058930 -309016717 684473363 -93368...
output:
No
result:
ok answer is NO
Test #10:
score: 0
Accepted
time: 168ms
memory: 28824kb
input:
199995 -88045160 -754166053 537999118 -600975136 507992830 -518080636 39365554 -358691055 -758317392 512499723 881007532 -962828746 -572412035 175565135 968490041 -994664833 709978672 -804735716 -303634784 -694082713 -59130173 -558086683 134566179 -468537576 -559886570 -13279147 956873077 -987380660...
output:
No
result:
ok answer is NO
Test #11:
score: 0
Accepted
time: 170ms
memory: 30900kb
input:
199995 751877273 -902803580 -438283469 -133229905 -457924536 -954675359 838836144 -929871820 -239512796 222101817 563268330 -660190100 556870083 -946184789 -985201972 66353356 -216346975 -313862155 559918674 -947158712 192980719 -961438929 -811651008 -161707407 284585611 -661800796 -414734311 360692...
output:
No
result:
ok answer is NO
Test #12:
score: 0
Accepted
time: 151ms
memory: 30508kb
input:
199992 467672870 -996993001 241650219 -493925971 849648842 -892593087 -326147502 -692396432 -866805696 -775049492 -380985862 -92370469 -362825862 -317436226 830242906 -846790011 -40608016 -941933328 144908937 -471622120 -396018063 -236727104 47294885 -81681580 698568506 -862960919 447264189 -5301740...
output:
No
result:
ok answer is NO
Test #13:
score: 0
Accepted
time: 126ms
memory: 26464kb
input:
199991 109672170 573860547 546933098 -90570193 928277586 970298066 987599431 968626012 920336525 353233135 454572949 967884727 421362358 995209255 598417779 969960580 106017730 762424678 543974354 -684869086 121816039 648191189 380803651 636788977 -956413035 -999893957 473169616 349122663 406717571 ...
output:
No
result:
ok answer is NO
Test #14:
score: 0
Accepted
time: 138ms
memory: 26536kb
input:
200000 12292352 -455065141 -390181101 -783347162 156602165 802988410 743295114 -667798048 375893047 -358589847 115224102 -483640155 979452678 -186641379 -774888997 600180205 226761733 665391746 993091639 -152845106 -954202769 -389817917 668939766 -197604121 657174588 -454213306 -657711838 122038041 ...
output:
No
result:
ok answer is NO
Test #15:
score: 0
Accepted
time: 159ms
memory: 37140kb
input:
199997 -999879824 -999879824 -999985274 -999985274 -999905148 -999905148 -999992386 -999992387 -999859308 -999859309 -999871546 -999871546 -999805065 -999805065 -999975361 -999975361 -999862311 -999862312 -999801098 -999801098 -999979435 -999979436 -999843402 -999843402 -999949497 -999949496 -999921...
output:
Yes 106277 155047 5259 13342 13281 15642 84131 172847 53049 43993 110374 24134 69229 82585 137484 87547 22101 194260 112249 78479 57485 118277 93747 49494 79728 32881 180798 114485 105611 133291 92516 2059 40150 191984 108774 151002 106618 25201 196204 157334 118866 41981 73562 38499 193789 191176 6...
result:
ok answer is YES, 199997 tokens
Test #16:
score: 0
Accepted
time: 155ms
memory: 38580kb
input:
199981 -999868018 -999868018 -999964060 -999964060 -999895225 -999895226 -999868368 -999868368 -999839616 -999839615 -999873455 -999873455 -999859804 -999859803 -999861087 -999861087 -999940826 -999940826 -999906591 -999906590 -999855890 -999855890 -999978359 -999978359 -999821571 -999821570 -999943...
output:
Yes 97200 167575 94367 147836 84642 186962 186483 97271 60515 10785 92661 159707 122996 89145 61642 185036 111235 182354 172420 180889 137780 196273 68284 68008 195923 134210 136528 70464 52625 101192 146980 109825 77820 168411 163267 26971 163506 38993 174992 166277 126904 98713 175260 187079 11642...
result:
ok answer is YES, 199981 tokens
Test #17:
score: 0
Accepted
time: 154ms
memory: 38592kb
input:
199982 -999912098 -999912098 -999829986 -999829985 -999940273 -999940272 -999970088 -999970089 -999809633 -999809632 -999888323 -999888323 -999904094 -999904095 -999923920 -999923920 -999931411 -999931412 -999880937 -999880936 -999883720 -999883721 -999982089 -999982090 -999820997 -999820998 -999931...
output:
Yes 149529 161836 176627 121589 167251 152322 135802 154990 159242 70441 56257 40831 101222 145107 14227 62671 115393 153960 76112 38412 48671 10743 75279 170041 56890 95495 122455 127520 105472 148556 67955 8183 133209 126551 159409 90942 77523 78648 127222 110208 44715 178187 166612 70744 47447 19...
result:
ok answer is YES, 199982 tokens
Test #18:
score: -100
Wrong Answer
time: 151ms
memory: 39256kb
input:
199998 -999887284 -999887283 -999915363 -999915362 -999823075 -999823075 -999863682 -999863681 -999859733 -999859734 -999956745 -999956744 -999997944 -999997944 -999847489 -999847488 -999857822 -999857823 -999852823 -999852823 -999839707 -999839708 -999930996 -999930996 -999975227 -999975227 -999825...
output:
Yes 142249 91344 45863 164356 71603 122948 168879 95005 6898 50618 137771 183954 87219 114731 56937 198904 70842 127009 183113 148328 14185 97936 188190 197559 8603 30409 158541 101883 193669 1476 4599 5119 135718 196242 133171 13500 146123 36815 108251 88253 40967 137665 185705 146043 136983 37304 ...
result:
wrong answer expected NO, found YES