QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#500048 | #6633. Exam Requirements | salvator_noster | AC ✓ | 172ms | 63584kb | C++20 | 6.5kb | 2024-07-31 21:32:39 | 2024-07-31 21:32:43 |
Judging History
answer
#include <bits/stdc++.h>
template <class T>
inline int qlog(T a) {
if (!a) return 0;
double x = a;
return ((*(long long*) & x) >> 52 & 2047) - 1023;
}
#define cin Mizuhashi
#define cout Parsee
#define endl '\n'
class Reader{
private:
static const int BUF_SIZE = 1 << 22;
char BUF_R[BUF_SIZE], *csy1, *csy2;
#ifndef _LOCAL_RUNNING
#define GC (csy1 == csy2 && (csy2 = (csy1 = BUF_R) + fread(BUF_R, 1, BUF_SIZE, stdin), csy1 == csy2) ? EOF : *csy1 ++)
#else
char cur;
#define GC (cur = getchar())
#endif
#define IL inline
public:
IL bool eof() {
#ifndef _LOCAL_RUNNING
return csy1 == csy2 && (csy2 = (csy1 = BUF_R) + fread(BUF_R, 1, BUF_SIZE, stdin), csy1 == csy2);
#else
return cur == EOF;
#endif
}
template <class Ty>
IL Reader& operator >> (Ty &t) {
int u = 0;
char c = GC;
for (t = 0; c < 48 || c > 57; c = GC)
if (c == EOF) break;
else if (c == '-') u = 1;
for ( ; c > 47 && c < 58; c = GC) t = (t << 1) + (t << 3) + (c ^ 48);
t = u ? -t : t; return *this;
}
IL Reader& operator >> (double &t) {
int tmp, u = 0; char c = GC;
for (tmp = 0; c < 48 || c > 57; c = GC)
if (c == EOF) break;
else if (c == '-') u = 1;
for ( ; c > 47 && c < 58; c = GC) tmp = (tmp << 1) + (tmp << 3) + (c ^ 48);
t = (tmp = u ? -tmp : tmp);
if (c == '.') {
double x = 1;
for (c = GC; c > 47 && c < 58; c = GC) t += (x /= 10) * (c ^ 48);
}
return *this;
}
IL Reader& operator >> (char *s) {
char c = GC;
for (*s = 0; c < 33; c = GC) if (c == EOF) return *this;
for ( ; c > 32; c = GC) *s ++ = c;
*s = 0; return *this;
}
IL Reader& operator >> (char &c) {
for (c = GC; c < 33; c = GC) if (c == EOF) return *this;
return *this;
}
}cin;
class Writer{
private:
static const int BUF_SIZE = 1 << 22;
char BUF_W[BUF_SIZE], *csy;
#define IL inline
inline void WC(const char c) {
if (csy - BUF_W == BUF_SIZE) fwrite(BUF_W, 1, BUF_SIZE, stdout), csy = BUF_W;
*csy ++ = c;
}
public:
Writer() : csy(BUF_W) {}
~ Writer() {fwrite(BUF_W, 1, csy - BUF_W, stdout);}
IL void flush() {fwrite(BUF_W, 1, csy - BUF_W, stdout); csy = BUF_W;}
template <class Ty>
IL Writer& operator << (Ty x) {
static int sta[32], top;
if (x < 0) {
WC('-');
do sta[top ++] = - (x % 10); while (x /= 10);
}else do sta[top ++] = x % 10; while (x /= 10);
while (top) WC(sta[-- top] ^ 48);
return *this;
}
IL Writer& operator << (const char &c) {WC(c); return *this;}
IL Writer& operator << (const char *s) {while (*s) WC(*s ++); return *this;}
IL Writer& operator << (char *s) {while (*s) WC(*s ++); return *this;}
}cout;
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef vector <int> vi;
typedef vector <ll> vl;
const int MAX_N = 100000 + 5;
const int MAX_V = 800000 + 5;
const int MAX_E = 8000000 + 5;
const int INF32 = 0x3f3f3f3f;
const ll INF64 = 1e18;
const int P = 998244353;
int N, M, V, S[MAX_N], E[MAX_N], idx[MAX_N];
struct SegmentNode{
int ls, rs;
SegmentNode () {ls = rs = 0;}
}node[MAX_V];
int rt[2], tot;
struct Edge{
int y, prev;
}e[MAX_E];
int elast[MAX_V], ecnt;
int low[MAX_V], dfsn[MAX_V], Tm;
int sta[MAX_V], tp, scc[MAX_V], scc_cnt;
bool vis[MAX_V];
inline bool cmp_by_r(int i, int j) {return E[i] < E[j];}
void Build(int x, int y) {
ecnt ++;
e[ecnt].y = y;
e[ecnt].prev = elast[x];
elast[x] = ecnt;
}
void tarjan(int u) {
dfsn[u] = low[u] = ++ Tm;
sta[++ tp] = u; vis[u] = 1;
for (int i = elast[u]; i; i = e[i].prev) {
int v = e[i].y;
if (!dfsn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
}else if (vis[v]) low[u] = min(low[u], dfsn[v]);
}
if (dfsn[u] == low[u]) {
scc_cnt ++;
while (sta[tp] != u) {
scc[sta[tp]] = scc_cnt;
vis[sta[tp --]] = 0;
}
scc[sta[tp]] = scc_cnt;
vis[sta[tp --]] = 0;
}
}
inline int NewNode() {
tot ++;
node[tot] = SegmentNode();
return tot;
}
void segment_build(int &i, int l, int r, int ty) {
i = NewNode();
if (l == r) {
return ;
}
int mid = l + r >> 1;
segment_build(node[i].ls, l, mid, ty);
segment_build(node[i].rs, mid + 1, r, ty);
if (ty) {
Build(i, node[i].ls);
Build(i, node[i].rs);
}else {
Build(node[i].ls, i);
Build(node[i].rs, i);
}
}
void segment_build2(int i, int l, int r, int ty) {
if (l == r) {
if (ty) Build(i, idx[l] + tot);
else Build(idx[l] + tot + N, i);
return ;
}
int mid = l + r >> 1;
segment_build2(node[i].ls, l, mid, ty);
segment_build2(node[i].rs, mid + 1, r, ty);
}
void segment_modify(int i, int l, int r, int ql, int qr, int x, int ty) {
if (l < ql || r > qr) {
int mid = l + r >> 1;
if (ql <= mid) segment_modify(node[i].ls, l, mid, ql, qr, x, ty);
if (mid < qr) segment_modify(node[i].rs, mid + 1, r, ql, qr, x, ty);
}else {
if (ty) Build(x, i);
else Build(i, x);
}
}
void solve() {
tot = 0; ecnt = 0;
memset(elast, 0, sizeof(int) * (V + 1));
scc_cnt = 0;
memset(dfsn, 0, sizeof(int) * (V + 1));
cin >> N >> M;
for (int i = 1; i <= N; i ++) {
cin >> S[i] >> E[i];
idx[i] = i;
}
sort(idx + 1, idx + N + 1, cmp_by_r);
segment_build(rt[0], 1, N, 0);
segment_build(rt[1], 1, N, 1);
segment_build2(rt[0], 1, N, 0);
segment_build2(rt[1], 1, N, 1);
for (int i = 2; i <= N; i ++) {
int l = 1, r = i, p = S[idx[i]];
while (l < r) {
int mid = l + r >> 1;
if (E[idx[mid]] < p) l = mid + 1;
else r = mid;
}
if (l < i) {
segment_modify(rt[0], 1, N, l, i - 1, idx[i] + tot, 0);
segment_modify(rt[1], 1, N, l, i - 1, idx[i] + N + tot, 1);
}
}
V = tot + N * 2;
for (int i = 1; i <= M; i ++) {
int a, b;
cin >> a >> b;
Build(tot + a, tot + b + N);
Build(tot + b, tot + a + N);
}
for (int i = 1; i <= V; i ++) {
if (!dfsn[i]) tarjan(i);
}
for (int i = 1; i <= N; i ++) {
if (scc[i + tot] == scc[i + tot + N]) {
cout << "NO" << endl;
return ;
}
}
cout << "YES" << endl;
}
int main() {
int T = 1;
cin >> T;
while (T --) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 22076kb
input:
2 3 1 1 5 2 7 10 11 2 1 3 3 1 5 2 7 5 7 1 2 2 3 3 1
output:
YES NO
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 55ms
memory: 39732kb
input:
1 100000 100000 15084647 15220430 217541056 217598054 222963701 223110976 71224450 71340221 320463268 320631387 334861459 334924668 328950591 329083669 178996498 178996584 428529461 428605033 405428435 405504132 197936687 197947412 9058562 9190197 169407597 169474101 297518153 297590927 31471874 316...
output:
NO
result:
ok single line: 'NO'
Test #3:
score: 0
Accepted
time: 49ms
memory: 40252kb
input:
1 100000 100000 14748507 14846251 125029948 125054609 463293218 463377641 198157217 198174486 61816219 61983451 43817835 43922214 146858750 146954988 30320405 30474901 19982332 20115324 118096811 118227915 446543803 446714206 334272499 334330640 334038396 334098710 142811467 142826092 343928730 3441...
output:
YES
result:
ok single line: 'YES'
Test #4:
score: 0
Accepted
time: 51ms
memory: 39836kb
input:
1 100000 100000 14378753 14427960 285902694 286019349 63076522 63199196 123034896 123091554 180956618 180971192 104893331 105077844 42717572 42770533 300075985 300247179 24213843 24240797 183255507 183392441 49921960 50077350 425570312 425743586 159753369 159916921 92930583 93006150 17541601 1766290...
output:
YES
result:
ok single line: 'YES'
Test #5:
score: 0
Accepted
time: 54ms
memory: 39032kb
input:
1 100000 100000 14008999 14009669 95199087 95219736 14436179 14597104 47912575 48008622 300097017 300106580 314204474 314321474 438388394 438398078 421595918 421783810 28445354 28554270 396649850 396832967 301347764 301488141 17056125 17196885 485280342 485399485 43049699 43186208 190966472 19098875...
output:
YES
result:
ok single line: 'YES'
Test #6:
score: 0
Accepted
time: 56ms
memory: 39660kb
input:
1 100000 100000 13605631 13735266 306114981 306163955 473109270 473261902 418782813 418868140 297212864 297253645 375822737 375911188 60621526 60621849 313499877 313647461 297219858 297394925 462722513 462902236 259120962 259259635 226014167 226123040 323655842 323840004 97994617 98082806 225359358 ...
output:
NO
result:
ok single line: 'NO'
Test #7:
score: 0
Accepted
time: 55ms
memory: 41904kb
input:
1 100000 100000 12378720 13625648 465814237 466616175 208691613 209863741 487589042 488474978 34489188 35271208 388644733 390469725 295170077 296291628 26123414 27676512 312050690 313755540 489093309 489538591 237262253 237973586 236118231 236780639 322598076 322794715 218797919 220330870 88459847 8...
output:
NO
result:
ok single line: 'NO'
Test #8:
score: 0
Accepted
time: 62ms
memory: 41924kb
input:
1 100000 100000 12025773 12899766 251831056 252958999 302794200 304237851 15424265 15656468 118197510 119570581 273660669 274814313 324357744 325209060 260709334 261019986 109892881 109901422 378006845 378110922 239114713 240200555 98023753 98835157 164309315 166050125 366410134 367688305 2150887 32...
output:
YES
result:
ok single line: 'YES'
Test #9:
score: 0
Accepted
time: 52ms
memory: 41920kb
input:
1 100000 100000 11672826 13497531 37847875 38695470 396896787 397288314 41329488 41514311 46702185 46736307 158676605 159765254 10679058 11260139 495295254 496293460 405805072 407370951 266920381 268613253 240967173 242427524 302795628 303149675 161224201 161255535 15952349 17582093 71045574 7273405...
output:
YES
result:
ok single line: 'YES'
Test #10:
score: 0
Accepted
time: 52ms
memory: 41224kb
input:
1 100000 100000 11319879 12165296 321934694 322501941 148133021 148796071 67234711 67372154 473276860 474508386 43692541 44109842 39866725 40783924 231811174 233496934 203647263 205446833 155833917 156579231 87615986 88844493 9497503 10000546 158139087 158390945 8360917 9735881 139940261 141601411 4...
output:
NO
result:
ok single line: 'NO'
Test #11:
score: 0
Accepted
time: 54ms
memory: 42412kb
input:
1 100000 100000 10950125 12051005 477581440 479154681 94266678 95909979 490182390 490895222 94347259 95525774 101284037 102455472 432053547 433727469 8722754 9737212 209620774 210562306 217508613 219120110 344267790 344951284 100795316 101617492 485408060 487219509 113683680 115563586 311623132 3122...
output:
YES
result:
ok single line: 'YES'
Test #12:
score: 0
Accepted
time: 4ms
memory: 22140kb
input:
10 1000 0 9084548 212659299 752049685 757793200 161999637 297780621 159218899 511613241 227411331 728832104 27428018 66692999 70254106 230710848 142218079 695911798 706863260 786626002 164254194 896730741 106307919 803778907 251793390 439950319 141699718 573753059 659066161 997295279 269040766 43188...
output:
YES YES YES YES YES YES YES YES YES YES
result:
ok 10 lines
Test #13:
score: 0
Accepted
time: 35ms
memory: 26652kb
input:
10 10000 10000 8076128 8101663 29809420 29847609 370721525 370740253 892411542 892413288 747565478 747585274 5739499 5751302 227883289 227888911 696243800 696274475 209086262 209139782 153701675 153740284 794914 801208 712815424 712841626 488108468 488120604 546898456 546921288 517871533 517891373 1...
output:
YES YES NO YES YES NO YES NO YES NO
result:
ok 10 lines
Test #14:
score: 0
Accepted
time: 20ms
memory: 26168kb
input:
100 691 691 508569640 508673802 208642094 208647922 28027525 28893278 215521571 216082768 432101881 432674036 287707806 288112166 757429741 757751727 729675214 730370857 359025437 359615838 697602408 698131276 443239285 444206285 186833263 187588090 357750289 357756701 552823963 552982349 527211763 ...
output:
YES NO YES NO YES YES YES YES NO NO NO NO YES NO NO YES YES YES YES YES NO YES YES YES YES NO NO NO YES YES YES NO YES YES YES YES YES NO NO YES YES NO NO NO NO NO YES NO YES YES NO YES NO YES YES NO YES NO NO NO NO YES YES YES YES YES NO NO NO NO NO YES NO NO YES YES NO NO NO YES NO NO NO YES YES N...
result:
ok 100 lines
Test #15:
score: 0
Accepted
time: 77ms
memory: 54820kb
input:
1 50000 50000 235239015 627380255 144730978 542058842 550305498 565415835 328800870 680798359 385148497 675077021 362103943 863384846 59798050 589436710 113699937 487373907 557941848 790625291 60531465 592567224 41157560 245376586 825839343 875678662 159266647 695027240 319681713 822890545 247698126...
output:
NO
result:
ok single line: 'NO'
Test #16:
score: 0
Accepted
time: 84ms
memory: 54908kb
input:
1 50000 50000 626892852 633391382 332519095 895980171 583401233 961674476 352795837 693969388 30261670 447241929 226651863 602336203 583872139 849355310 79235608 858959672 78521707 943110748 724798770 952348869 424887625 958660184 703187100 863080259 555964295 685361175 390557968 397742944 529306351...
output:
NO
result:
ok single line: 'NO'
Test #17:
score: 0
Accepted
time: 165ms
memory: 63584kb
input:
1 100000 100000 611316630 629811740 91996695 793205603 205568177 975572692 476141394 984340236 739813611 910022525 212513275 370043741 310441153 445307964 319058023 346679908 670565549 934504580 566150142 993981165 932880384 935485719 680278897 980699546 244485251 927396846 322480796 833496991 34107...
output:
YES
result:
ok single line: 'YES'
Test #18:
score: 0
Accepted
time: 155ms
memory: 61728kb
input:
1 100000 100000 610946876 857807203 599281597 900917088 427496349 598338428 123875625 401019073 847949514 858954010 442677409 578978884 824577876 988838433 63366721 968387841 306867511 438548091 59515861 703179972 536258541 701410706 71997359 819298030 69824224 802640084 4101933 272599912 14689805 7...
output:
YES
result:
ok single line: 'YES'
Test #19:
score: 0
Accepted
time: 172ms
memory: 63436kb
input:
1 100000 100000 85802666 610577122 405357591 562353834 26903653 991108679 263411014 325896752 638392856 978094409 525357896 640430380 338714599 384885255 590095774 660191772 942591602 943169473 272534204 692726155 139636698 467335693 163295172 810833516 530399675 895163197 174706875 222719028 688302...
output:
NO
result:
ok single line: 'NO'
Test #20:
score: 0
Accepted
time: 164ms
memory: 61812kb
input:
1 100000 100000 31322880 610190561 373973574 896107801 482202027 913667658 92579172 149746887 638456885 716565783 25801083 640083865 143931232 778608280 96995720 266977967 5352786 562939706 662173707 686213373 905911158 993954199 99239139 137258923 274071980 903372610 88515186 122828692 616047378 68...
output:
YES
result:
ok single line: 'YES'
Test #21:
score: 0
Accepted
time: 169ms
memory: 60556kb
input:
1 100000 100000 609736772 846942098 34228770 550298572 102865196 803515622 385311112 716970493 53642257 208238815 264397673 588024468 207490182 921529793 292147365 766125091 116583023 745435603 105530143 905781497 409578135 887604888 199435485 837707075 232998371 933911494 85482313 827653326 1178684...
output:
YES
result:
ok single line: 'YES'
Test #22:
score: 0
Accepted
time: 67ms
memory: 30564kb
input:
10 10000 10000 968433817 980345689 103557645 824564023 829074871 997250637 474151154 894114908 716734949 928511820 579435564 960645476 162817 170066 26989283 75787020 330896 456526 312609711 500901739 503200 539839 693994 864159 959375 1027512 482433434 698751890 138723658 154257942 1157115 1278976 ...
output:
YES NO YES YES YES YES NO NO YES YES
result:
ok 10 lines
Test #23:
score: 0
Accepted
time: 73ms
memory: 29868kb
input:
10 10000 10000 55889446 676543761 339486739 512854517 89914 263037 43940346 743378135 474800917 474989262 381945 551085 53729144 521064977 625461 772887 174165490 859237741 895977 913869 122582738 363347004 1002118 1119286 557598499 854847993 1187071 1271634 1342510 1377024 1428419 1571587 1729397 1...
output:
NO YES NO NO NO NO YES NO NO YES
result:
ok 10 lines
Test #24:
score: 0
Accepted
time: 142ms
memory: 55928kb
input:
1 100000 100000 2825612 287187070 999993267 1000000000 94 854 155005964 287573137 9070 21537 26142 34796 44434 45874 56159 63808 991386787 993171553 220122482 731015713 69663 87780 617617555 933500337 169625859 372421698 305623688 808834660 596826732 937822295 100817 108696 649207508 659155127 12219...
output:
YES
result:
ok single line: 'YES'
Test #25:
score: 0
Accepted
time: 143ms
memory: 58996kb
input:
1 100000 100000 3092 15274 19530 26942 33337 41977 627434658 942568814 43029 56667 697630428 961374423 58104 73299 110856530 735851270 82074 88280 141181852 262918400 96630091 650451770 92264 103401 172238029 172249854 388421560 643850618 105442 124096 131664 143119 280179217 333440826 148798 166640...
output:
NO
result:
ok single line: 'NO'
Test #26:
score: 0
Accepted
time: 142ms
memory: 61944kb
input:
1 100000 100000 10871 20950 37967 48437 285223721 594034432 51008 69067 76789 94787 97482 101557 26805305 26817148 115032 116107 387548524 412427666 129659 148344 38643779 237102119 163617 172021 188640 192596 202853 209871 216178 233816 252619 269075 478290210 592268749 853248909 963217231 282903 2...
output:
NO
result:
ok single line: 'NO'
Test #27:
score: 0
Accepted
time: 142ms
memory: 62532kb
input:
1 100000 100000 12795 27793 28468 41752 806312932 872614132 43181 55491 64694 82276 97343 111737 653273873 653281920 121362 135600 152867 169975 170207 170720 68812492 780071607 824067587 981895206 55248817 646910393 33392751 277269763 398950075 812465043 179090 185948 819483157 819498645 144084780 ...
output:
NO
result:
ok single line: 'NO'
Test #28:
score: 0
Accepted
time: 114ms
memory: 54380kb
input:
1 100000 100000 10221 14469 186957342 298058745 18743 36956 92950555 865157656 126663217 672393942 401361439 435570046 32239890 128425695 48937043 392849449 145368241 160614779 239539699 794392360 10826180 366721956 39944 40064 59006 60530 23920020 444334151 92172706 705687920 298764881 317566859 17...
output:
YES
result:
ok single line: 'YES'