QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#659935#9492. 树上简单求和zlxFTH100 ✓4614ms85464kbC++174.2kb2024-10-19 23:40:512024-10-19 23:40:57

Judging History

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

  • [2024-10-19 23:40:57]
  • 评测
  • 测评结果:100
  • 用时:4614ms
  • 内存:85464kb
  • [2024-10-19 23:40:51]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using ULL = unsigned long long;

mt19937 rnd(random_device{}());

constexpr int N = 2e5 + 5;
constexpr int B = 400;

int n, m;
int key[N];
struct QQ {
  int u, v;
  ULL k;
  QQ(int u = 0, int v = 0, ULL k = 0) : u(u), v(v), k(k) {}
} q[N];
ULL A[N], ans[N];

struct Tree {
  vector<int> G[N];
  int dfn[N], siz[N], fa[N], rev[N];
  int ti, st[20][N], dep[N];
  void dfs(int u, int f) {
    dep[u] = dep[f] + 1, dfn[u] = ++ti, rev[ti] = u, siz[u] = 1;
    st[0][ti] = f, fa[u] = f;
    for (auto v : G[u]) if (v != f) {
      dfs(v, u);
      siz[u] += siz[v];
    }
  }
  #define get(u, v) (dep[u] < dep[v] ? u : v)
  void init() {
    for (int j = 1; j < 20; ++j) {
      for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
        st[j][i] = get(st[j - 1][i], st[j - 1][i + (1 << j - 1)]);
      }
    }
  }
  int LCA(int u, int v) {
    if (u == v) return u;
    if ((u = dfn[u]) > (v = dfn[v])) swap(u, v);
    int h = __lg(v - u++);
    return get(st[h][u], st[h][v - (1 << h) + 1]);
  }
} T1, T2;

ULL num[N];

struct DS {
  ULL sum1[N], sum2[N];
  void add(int x, ULL y) {
    sum1[x] += y;
    sum2[x / B] += y;
  }
  ULL qry(int x) {
    ULL res = 0;
    // for (int i = x; i >= 0; --i) res += sum1[i];
    for (int i = x; i >= 0 && (i / B) == (x / B); --i) res += sum1[i];
    for (int i = (x / B) - 1; i >= 0; --i) res += sum2[i];
    return res;
  }
} ds;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    cin >> A[i];
  }
  for (int i = 0; i < n - 1; ++i) {
    int u, v;
    cin >> u >> v;
    T1.G[u].emplace_back(v);
    T1.G[v].emplace_back(u);
  }
  for (int i = 0; i < n - 1; ++i) {
    int u, v;
    cin >> u >> v;
    T2.G[u].emplace_back(v);
    T2.G[v].emplace_back(u);
  }
  T1.dfs(1, 0), T1.init();
  T2.dfs(1, 0), T2.init();
  for (int i = 0; i < m; ++i) {
    auto &[u, v, k] = q[i];
    cin >> u >> v >> k;
  }
  vector<int> o(n);
  {
    iota(o.begin(), o.end(), 1);
    sort(o.begin(), o.end(), [&](int u, int v) {
      return T1.dep[u] > T1.dep[v];
    });
    for (auto u : o) if (!key[u]) {
      bool f = true;
      int v = u;
      for (int j = 1; T1.fa[v] && j < B; ++j) {
        v = T1.fa[v];
        if (key[v]) {f = false; break;}
      }
      if (f) key[v] = true;
    }
    sort(o.begin(), o.end(), [&](int u, int v) {
      return key[u] > key[v];
    });
  }
  for (int u = 1; u <= n; ++u) {
    ds.add(T2.dfn[u], A[u]);
    ds.add(T2.dfn[u] + T2.siz[u], -A[u]);
  }
  auto addS = [&](int u, ULL k) {
    while (u && !key[u]) {
      ds.add(T2.dfn[u], k);
      ds.add(T2.dfn[u] + T2.siz[u], -k);
      u = T1.fa[u];
    }
  };
  vector<int> L1(m), L2(m);
  for (int i = 0; i < m; ++i) {
    auto [u, v, k] = q[i];
    {
      int x = T1.LCA(u, v); L1[i] = x;
      addS(u, k);
      addS(v, k);
      addS(x, -k);
      addS(T1.fa[x], -k);
    }
    {
      int x = T2.LCA(u, v); L2[i] = x;
      ans[i] += ds.qry(T2.dfn[u]) + ds.qry(T2.dfn[v]) - ds.qry(T2.dfn[x]);
      if (T2.fa[x]) ans[i] -= ds.qry(T2.dfn[T2.fa[x]]);
    }
  }
  // fprintf(stderr, "%.2f\n", double(clock()) / CLOCKS_PER_SEC);
  // for (int i = 0; i < m; ++i) {
  //   cerr << ans[i] << " \n";
  // }
  for (int i = 0; i < n; ++i) {
    int s = o[i];
    if (!key[s]) break;
    fill(num + 1, num + n + 1, 0);
    {
      int u = s;
      do {
        num[u]++;
        u = T1.fa[u];
      } while (u && !key[u]);
      for (int j = 1; j <= n; ++j) {
        u = T2.rev[j];
        num[u] += num[T2.fa[u]];
      }
    }
    ULL res = 0;
    auto addB = [&](int u, ULL k) {
      if (T1.dfn[s] <= T1.dfn[u] && T1.dfn[u] < T1.dfn[s] + T1.siz[s]) {
        res += k;
      }
    };
    auto qry = [&](int u) {
      return res * num[u];
    };
    for (int j = 0; j < m; ++j) {
      auto [u, v, k] = q[j];
      {
        int x = L1[j];
        addB(u, k);
        addB(v, k);
        addB(x, -k);
        addB(T1.fa[x], -k);  
      }
      {
        int x = L2[j];
        ans[j] += qry(u) + qry(v) - qry(x);
        if (T2.fa[x]) ans[j] -= qry(T2.fa[x]);
      }
    }
  }
  for (int i = 0; i < m; ++i) {
    cout << ans[i] << " \n";
  }
  return 0;
}

详细

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 7ms
memory: 44252kb

input:

3000 3000
7236742292501328495 17973811477309806363 16075782662531676171 17971236571771878676 11392080645527132110 3685563455925680459 9773593720088356683 8313828403245053795 7736401634567449043 1634817828009987181 6951124933529719486 12775126714635387213 15460977209223753216 397573676785925632 31372...

output:

12105153858659381124 
18367442707572066757 
11668241962484097878 
11288238120352358472 
1742468310074622166 
9942835997686093671 
3305677510569607477 
17741602000425004088 
14984128302052618266 
1075081718074605786 
6509217537832509095 
16750513627843273113 
8569443169249732820 
14475184194298579044...

result:

ok 3000 lines

Test #2:

score: 5
Accepted
time: 3ms
memory: 43992kb

input:

3000 3000
1612333876155866602 8538417838700679227 6080765231437578796 17905224638340228394 12270907925903144224 17944105326358594564 17302041033966840611 1006351124625222126 496336153231744288 9393087977687876980 9553975238547373621 9361882717200384390 15051881329169144319 9757999873162420435 882725...

output:

11133131376095771981 
7909873024850695144 
16250639243139481926 
14562550655578101207 
8274205996508264973 
178549413271904466 
2368406276743327913 
7464009386554813982 
9439464815411774627 
1471756740732097060 
15201641099137019227 
6774030298556871576 
18156105511913219667 
1553508745644446823 
42...

result:

ok 3000 lines

Test #3:

score: 5
Accepted
time: 16ms
memory: 44300kb

input:

3000 3000
9709246061666095435 1861649101703072889 10620139893353930613 17635186539135419482 710209455559527146 6075101384669982511 1120305006358459674 9703156967435388252 1397046737759839382 5259056712870179169 8253156305433022999 710199693203327302 15130650033641744675 10720111924616886955 15543351...

output:

7834604406305153073 
5037061270969117785 
16481572776620825702 
15177894197606565804 
3120320619896892806 
18008650876379132344 
7417108723176816402 
13515164814425439399 
3299769942258542105 
15897528270699011770 
11642805469843844638 
16764682282380318054 
4824039114054405772 
4859834102876213962 ...

result:

ok 3000 lines

Test #4:

score: 5
Accepted
time: 14ms
memory: 46968kb

input:

3000 3000
16538965545220923528 18062192327708400751 10422465150728338588 3471522151129113073 1236650672072793692 1942240200040301168 13090729759591037952 15335798523677372669 9912100622761466753 11177948788405690381 3710859061697501523 4984944638666762977 17278589713462878008 6371292801024547050 868...

output:

8182453933067329108 
13535217473847106938 
17067385337010269798 
3806121648880466130 
11322569288575153037 
11079197311131660121 
9670138330007803226 
6554062218199796758 
965954569567598779 
18055887214749050688 
6142620503089407421 
8690117812667761187 
9547139298346295115 
8890987597519353054 
17...

result:

ok 3000 lines

Test #5:

score: 5
Accepted
time: 10ms
memory: 47284kb

input:

3000 3000
17759588706587888497 10550000524636484378 11601004513528075994 7150322911283804521 4459707248078569712 10692395730842402625 8940418793863522991 12967068928670540447 9954278250450015940 13702413838608801301 10598390500439869870 15110245227553613794 490862872212325709 15164980555660957366 94...

output:

9743736929788175512 
16812303667256960040 
14694223512340829897 
550204232580650311 
1175342872438242313 
17622261358285047637 
7413682703975031220 
12643066512274062227 
1868985217436232595 
5471830334855681322 
8070132260376389587 
3970361922096052085 
218281824643752746 
991917103472727104 
29602...

result:

ok 3000 lines

Subtask #2:

score: 12
Accepted

Dependency #1:

100%
Accepted

Test #6:

score: 12
Accepted
time: 3ms
memory: 32252kb

input:

5 7
0 3 2 6 4
1 2
2 4
1 5
5 3
3 4
4 2
2 5
5 1
5 3 0
3 2 5
4 4 4
4 4 3
5 2 0
3 4 3
5 5 6

output:

15 
21 
10 
13 
17 
26 
18 

result:

ok 7 lines

Test #7:

score: 12
Accepted
time: 397ms
memory: 60184kb

input:

70000 70000
3805295436278888199 9842309351516174725 1566744796319231180 2206519284152256579 2715928675931950447 6346821976624501261 16020972671480798719 14702021753902144915 17127828773798978442 15779168055669690475 4964561323934614661 9395102787554964450 6377076753365184543 15167378195767668817 288...

output:

5971729064136092190 
6457394048987305727 
13604212649915736394 
8639973959364892219 
437861319070967556 
16133076880026962355 
5384937395694479961 
4591478439775690843 
16071919565966962790 
15485626634068969082 
10235993901046758372 
3449528613427081475 
8064280362779764074 
12784984512326434905 
4...

result:

ok 70000 lines

Test #8:

score: 12
Accepted
time: 301ms
memory: 61120kb

input:

70000 70000
17769190865915081913 3772925482507158804 10559962993069063712 16307277356502651642 12014171661057147061 1923543107882042577 13408785599350410314 17786178374951015816 2038922879833426794 2540043772647346461 15419977514837351390 5175974305273838292 16815288359165841441 6295059675346852046 ...

output:

16215781699519408534 
17067966839552063165 
1639359200259068228 
1157756671621253300 
12850966537933214537 
13917563606289473282 
11146906493479190751 
869141055866285398 
529460535280965984 
11437720548737856517 
12321579881011015953 
4005153170897692243 
10217866116994297464 
8892403813874757974 
...

result:

ok 70000 lines

Test #9:

score: 12
Accepted
time: 370ms
memory: 62092kb

input:

70000 70000
1322605819855709761 1534349070722535975 3956030287626175223 12996546673549161162 7258680666490714729 15591023033141410544 11626890152249303179 7745771567168540351 5535931029756133379 11840793767439557739 6286106656048048381 9490665709724541446 4561258384162386434 2460318488748442222 1303...

output:

7565012138645637258 
1080785033897684285 
4000254219257999844 
8727142139647715419 
1784876728989450460 
2474052717732723820 
5108017366064709316 
5232698473118606856 
7893212823648229982 
6449010654774296779 
16571818815110297674 
603759348329356530 
7364528294111530037 
4667545362378304836 
303972...

result:

ok 70000 lines

Test #10:

score: 12
Accepted
time: 493ms
memory: 61060kb

input:

70000 70000
2918414982140182939 1004760492603077644 7526656799259998488 6665485253854847449 7752199419154649757 12763267823077347079 11745132191692540338 6726116817426709990 15550876907005962464 9760509858122842638 684733892856965421 10077915441058780247 8380400329996723109 16920573433866702239 3069...

output:

8230389499860859172 
16425656898047941538 
107743004356580170 
9778122844868660722 
11068387722102791183 
13252614309136720348 
15937842372230698728 
12777338070107774364 
17974062134369145560 
3740400391792770609 
7367804332878038809 
14236246024207211797 
5659238205278608512 
10550373456364765526 ...

result:

ok 70000 lines

Test #11:

score: 12
Accepted
time: 722ms
memory: 62636kb

input:

70000 70000
14167059704556856337 16190708842842354431 16763990539754009056 7631426709261583690 16701377874952853623 13128000186728267818 13668914249103068169 11444044591715948726 461080622438520919 15327533341012334586 15905150558482528923 18113008235210277231 18273290154232335325 871461822812191943...

output:

5416890687002400795 
15434184693210288436 
14994504916760087024 
2057026449542829151 
14782289435774270062 
5375237679514404106 
6242405047854012647 
13176621545709355733 
14860610197328732602 
2320525143444929350 
4955538191022622551 
16072981679771537209 
16493487770453132249 
7457010288198365370 ...

result:

ok 70000 lines

Test #12:

score: 12
Accepted
time: 498ms
memory: 60776kb

input:

70000 70000
6512290618577097706 2307104154841663907 18099814251235047570 8297332016606109910 6979819983598849680 18022671181330012408 7003320957516774041 10765303713874539785 15263207007138552812 11713955610641877995 9084887894280210904 3653718255996209121 14197591595561260765 2937670413926210256 43...

output:

5372775214253596890 
927985558228810546 
3829815088328182672 
17496384540548895622 
2541458359607440535 
9685902106698191409 
13649653134779075960 
2952563488513208867 
3457470079648848247 
11542323450217419837 
6576344363223624061 
12316990756988470568 
17923006133291073450 
13069551524451668138 
6...

result:

ok 70000 lines

Test #13:

score: 12
Accepted
time: 489ms
memory: 59800kb

input:

70000 70000
13665984219894847790 9458613748861462697 7467746948118990839 10855454155004540952 10025433108785732161 15816172836312183738 2834129139700401667 221649423184372325 8409217794427284711 16119623676185869010 12488380095384700010 3049877130176336551 5805665682633632307 13224802542929355280 18...

output:

7934210059911784858 
14305091721658406168 
5803801684631217062 
8806866881905382618 
14997911434771439753 
7006465422324293550 
15394754861139766679 
8377831978907312075 
12227086919743533414 
8784212755151945751 
17039860679476902214 
6474495685436520748 
11136139762939837997 
16869294577244011226 ...

result:

ok 70000 lines

Subtask #3:

score: 13
Accepted

Dependency #2:

100%
Accepted

Test #14:

score: 13
Accepted
time: 1303ms
memory: 68456kb

input:

120000 120000
4056283459929576306 2264755903151268173 1157390036441353969 5734735320959854923 6025999163810189446 3972481234804681969 4746636248696530169 6716674455256322787 6407347371842702902 7463142557880503801 208361219405474896 512530621977574257 6488145455921761864 6595856237657889728 95997703...

output:

11686658894480913739 
10283716998652647869 
7469817527336516079 
9879285786875030762 
4982549977394044949 
16564334076086174008 
6433057925981833441 
7460470339844352254 
9945354316570680900 
18377735143728853940 
15872286040534058104 
8507347369923543553 
308747406436979607 
18218197459972943141 
1...

result:

ok 120000 lines

Test #15:

score: 13
Accepted
time: 2067ms
memory: 69968kb

input:

120000 120000
5867632904403891095 7734115005912544376 13901514937742085110 17141033381317351710 17988246451665298411 17540600012243810041 15190868862458266725 15454563456231559301 8740470882859091311 17882360629171437337 12095218884748126199 17817518168343018595 7112391591378197276 65538601378146110...

output:

13420129597746517056 
18337642296188485079 
4380067206814687930 
5525410739012465159 
1979575298167242590 
10855827974711636510 
9874020479466690595 
17720000790164899934 
16724816545805525287 
15594891417371432986 
14655386085151616523 
11435247647009150363 
7635358811289719984 
1460973550003664383...

result:

ok 120000 lines

Test #16:

score: 13
Accepted
time: 832ms
memory: 67700kb

input:

120000 120000
12590795589408290093 11275909154009220197 10996087245163181988 287253987689120747 522028471439816976 5251098397309018220 9466903789635983479 12562504698210775380 14359608006525868271 12860739587215060171 6110493152041264342 8941951597283806533 7247902667356706183 13908919237133011991 1...

output:

12568574963997891813 
9761481874717599084 
9748193662109666281 
17759229044598540251 
9232146611495947992 
16451851566322082145 
10163587939420717881 
11939061140179225100 
13555756814075457024 
15331444302135124578 
12404089960631589833 
10914316315261843243 
3330610810849167077 
430867386137238424...

result:

ok 120000 lines

Test #17:

score: 13
Accepted
time: 993ms
memory: 67736kb

input:

120000 120000
16014732670888203993 17003360764706956461 4309217563402934767 12155136955819956058 9472943536135969437 8619903067520668384 8532935983471178458 840596314384730622 8808409849265669508 16268252642839060126 8703458878963184072 14133056030074803107 16125379684339605436 13795196609771489642 ...

output:

14157083647705042191 
9626539498588941455 
12672590587667741319 
7637586779842324001 
17945793757619266709 
6486513804042528016 
17128439522931715545 
14506773931432125656 
10149598925465005229 
8493513931817247270 
9843224754697262936 
17563138715401598781 
5251652421620155711 
16347886781065131205...

result:

ok 120000 lines

Test #18:

score: 13
Accepted
time: 1232ms
memory: 65944kb

input:

120000 120000
3799726989717681598 2540658873004706851 6999377479951345208 4574847538261052797 1388764904624490347 797597442974571877 12049698136986117426 1334073669070317189 11812534794423707083 12910806883079537898 8919907966949030320 3609251437048437267 6955259073591432492 1913761510032208708 1536...

output:

16410218753178084291 
3452125570141203996 
12637348475870430626 
939828522750114530 
6181904502892064992 
7530673907543931274 
11125835388154440123 
1132493328298594689 
6540415366631312545 
10171022468601061874 
10785984448364782773 
15132462728937914062 
13894055239781007518 
14553135357399426810 ...

result:

ok 120000 lines

Test #19:

score: 13
Accepted
time: 844ms
memory: 67000kb

input:

120000 120000
523123731336918243 4097858622836674571 1961367823237386001 2725250184116707092 15256083167104925470 8826573328357841773 14551942275839683916 4676612813711946771 16866097649532049020 16028370234860808559 16550040875881081238 13114506992715113111 18223636920754369434 4711187061384408363 ...

output:

13171866584326858355 
7378923635054867195 
4676544939953182559 
8211313138413629930 
3762100382261198154 
17376905504590956432 
11575432112253285846 
6651270238220236939 
7296214239679292747 
3921715204635211841 
13514446212830941534 
14681462832343839777 
9394758474079991863 
2039117273115115478 
1...

result:

ok 120000 lines

Test #20:

score: 13
Accepted
time: 937ms
memory: 67852kb

input:

120000 120000
16563527794956746492 3507607345845239151 6704373347302736722 4366660651585002614 17477711326324414919 14064904073416411127 1886265819461820151 1530962154006256458 3386801749967932412 10176358119958383434 14136333004424650089 18047845530334381646 14290290829566494165 1979382774616512004...

output:

2687063429907612648 
7246290134975359576 
451523845887078136 
6787443537167049842 
11742387638116508426 
9452080235999660003 
1640133015384348445 
9479626460563956802 
8536081354965239985 
14886879078945984440 
5977814891978138604 
16811290642393481835 
2319291536056800936 
4327858711873466013 
5082...

result:

ok 120000 lines

Subtask #4:

score: 14
Accepted

Test #21:

score: 14
Accepted
time: 2050ms
memory: 77584kb

input:

200000 200000
622783158027686223 2242697872372232537 8481648430436878777 10092474834140799044 15403999682625301609 12614289513474949582 9180944589267018841 7823784919308285798 8257785171198951273 5134508521895120821 8041682272181381093 3835432206618893170 2653803171409877650 5589823419153460372 1007...

output:

9042998055336671259 
11611293489264521142 
5835924579879681322 
9187084356907537870 
17810346410706951073 
565636160725988981 
837626748701483168 
16059573289829807099 
7246210357888652619 
7725251776483176497 
17088098442183693937 
9042305714006927228 
10907378739216215456 
6526772063609981609 
515...

result:

ok 200000 lines

Test #22:

score: 14
Accepted
time: 2906ms
memory: 78124kb

input:

200000 200000
13175752638648662841 17926176333479943540 18069418271192836667 7662981418770774166 17432280672869071045 9361466030141569604 17336291298429915451 758279154724011577 10229986883918215412 16695796270233481895 1104033984864960726 9768530369533627193 7121962912997584423 8574667967472399164 ...

output:

761007177180158471 
99932139211644879 
9085452500188024811 
10579196290428182519 
9823187704909577710 
18023302821814112676 
12490017484705421441 
12628966555486388857 
14265121989865566834 
6520346880672680237 
13101459183526308131 
999924043939340162 
18263995506773932901 
5204528109864295202 
125...

result:

ok 200000 lines

Test #23:

score: 14
Accepted
time: 4219ms
memory: 83772kb

input:

200000 200000
7686280868723494190 956703982700755675 9999621735507690021 16173863373498393354 13710049849600478540 17103229081434028663 17565545023679367555 2828484246894512005 1583487132574088302 6282276626784421099 11842426946394217784 3255349046251970557 9837219010639574935 8803965402777990679 10...

output:

9027980728293426417 
390552393210324231 
11163738403290403569 
7251051512011369232 
11710945043516484177 
8385783841330898676 
10540689232459717148 
13494924758898800208 
10783463309429788767 
15497109458285729613 
3973164643641949159 
16591368938886703497 
17545967451093599325 
7502098747509618204 ...

result:

ok 200000 lines

Test #24:

score: 14
Accepted
time: 2019ms
memory: 79692kb

input:

200000 200000
3398335727711776744 2517912491303558304 9944108242783740552 11465445588414101188 8918103911029611319 6248803476150904656 13839544089125989886 11613304797643373734 2743278001758631252 5880657146483100262 17520221750013284250 3574310479117269847 17332054826892442501 4186477155186295241 7...

output:

11201243883635739649 
5642768912062346910 
14237324928813743475 
17949858083662777758 
7007085524141292752 
16431646654432642924 
9544485471385114348 
17223214017002242047 
6358064993672703329 
7126356965173878837 
10226578739676773239 
17581948280120185856 
7547085902091221485 
2256786006467014785 ...

result:

ok 200000 lines

Test #25:

score: 14
Accepted
time: 3630ms
memory: 80532kb

input:

200000 200000
16389428600328688123 13285293781493429938 16272776262151288852 2788638121841944928 840590085080737028 472104557233550161 2950757076856426026 884621482021485766 4656207248358869553 4325985129321868698 15439653714414044259 8869605634233383357 2875651646205284961 18315661660942366682 3209...

output:

11670281421082997569 
13170194106693978241 
4379481616026191349 
1374955090149450188 
16981223657037354332 
15581757479756062245 
964815911596550839 
14653197660590615612 
1244503873454847903 
12992317503104122180 
8922002840354854569 
9883361056075385805 
4661992164326801469 
5993972796274466263 
4...

result:

ok 200000 lines

Test #26:

score: 14
Accepted
time: 2007ms
memory: 77880kb

input:

200000 200000
8926134977558578929 14277420964906340273 14017501029945049702 16291239250458096854 5699993893720160591 1404316482439341580 6509187990544574711 3321495986616857673 9576515208059172862 16437943937474607467 3444518963957979419 17039197068804123693 9035882298315219046 10231648064038856650 ...

output:

11394865482866208122 
4540012560447567167 
14181315197904653108 
1138165850159307501 
4403319165822720694 
3554076031362588972 
4848001086504005989 
17788785233422248859 
5278865852900446472 
9052657317349052491 
7439239802335183804 
280124506773607363 
4951887064424754895 
4442074242463250219 
1127...

result:

ok 200000 lines

Subtask #5:

score: 17
Accepted

Test #27:

score: 17
Accepted
time: 4614ms
memory: 83704kb

input:

200000 200000
1958469220619413759 14991498002015735322 6054491201406941902 18206143187746582567 15082377615826460430 2936248617457291604 10073577150351675920 16534472678586906457 2207599132486246393 10301540360769075442 1492580560381080472 551692353431379140 13238280352539145808 8462626987240986565 ...

output:

11479812171669345085 
7612644482907856514 
7664363696211351499 
10419050713553268082 
7115244954460011045 
9683711549165598600 
15714069303067445091 
5098969076555779384 
17312050420753525411 
13302302653999024684 
15237835478514966949 
1011923303415334401 
15280591493481885526 
11613220426756932450...

result:

ok 200000 lines

Test #28:

score: 17
Accepted
time: 4607ms
memory: 85024kb

input:

200000 200000
16779443803326674772 15639579352489825289 13969981610137062426 16505376510381344640 9806280160602498118 1419045977670621133 7677707894082613460 11957033082833096140 2771983498938827257 14706498164400422706 9378952791453329569 1930132295950861416 16111764090559108273 8905137311835789422...

output:

16293566981830212911 
10264859857591337484 
8994663676867609646 
2754771179506593788 
4767946170760042771 
742819530451319825 
2803285017809086810 
3484130454853725644 
7697600623078121691 
5084812233611883732 
3280787561128521192 
1047502191383912852 
14082348302073768112 
2601331176748190671 
1174...

result:

ok 200000 lines

Test #29:

score: 17
Accepted
time: 1456ms
memory: 81200kb

input:

200000 200000
12029385893748061284 9172822681287286332 11779114870282057106 4849897936395853889 6103529715098530443 8797239236736271231 11618134370305604768 10908476427113524251 3933201111692274240 4499796948331538987 4232975400910660164 10415557794345312125 17360908993089799508 13708880030692860522...

output:

13101691483811142037 
7858940297704268921 
9131311782659594969 
3979986497647305855 
131040009215643795 
10080455913202724993 
13237896591702170157 
4007300413168456185 
10099014266690222675 
16590528230541839393 
10133194446659869919 
16360073169922464941 
15194261798246191631 
5464643399868946391 ...

result:

ok 200000 lines

Test #30:

score: 17
Accepted
time: 1643ms
memory: 80616kb

input:

200000 200000
12279899037614140058 8888114948527866653 13928233147675322734 12454101025136386040 5288759580423671283 8776652717163613021 16449880332412915864 17287034922899709125 10532733829212727135 10764189288575553991 13953267646406847995 13908054688602304211 5827028562849173311 10886964702131020...

output:

16698510136139978210 
16369094547606910925 
1326550504815919356 
15571631364851754526 
15142726028067532669 
16433307477502505346 
2288796203808772846 
14834334808701484355 
11332372387379739662 
16882038025761766711 
15880577744881855798 
3482331692875200083 
3909893051643604341 
175252211957833803...

result:

ok 200000 lines

Test #31:

score: 17
Accepted
time: 1209ms
memory: 84224kb

input:

200000 200000
4893160298280825903 18198846065921817748 16343447781007974282 15723743432312964985 12871862738540236681 9972578954818260019 125153552836276808 5361924347833293579 11971958522882153451 6606998668153528639 9846700557419796517 924197471899377062 16510652970019285610 13527675083280389351 1...

output:

12217733345977585604 
15090345895939064308 
8800682550100929240 
8418299123801754016 
9906718252280231096 
3019478245971491784 
9496949828298647194 
17471225676572414614 
11441204915622920024 
5759065639620250580 
3072007946120216696 
17839333347550122908 
11855291417460815970 
1574976372415972484 
...

result:

ok 200000 lines

Test #32:

score: 17
Accepted
time: 1351ms
memory: 80348kb

input:

200000 200000
16269080113100378653 4484500057558985491 3155111047194780915 1955124878557628793 1131676785723263995 15670458790089679131 12642775067469645913 16058994799171671871 11128893081798077921 17630174838696618160 10509057764997030178 2736352128209806460 11214180975026520052 990613932293281058...

output:

12064924625133015846 
16862321744372560028 
1994646811747150992 
10140722851099240116 
2557503422311666754 
15259878734280971978 
3955576474907811510 
3673505041702176640 
7400377071018962046 
12622228824601464114 
10514727287268994992 
17046945994663165568 
3131278608817391298 
7110396577833899144 ...

result:

ok 200000 lines

Test #33:

score: 17
Accepted
time: 4531ms
memory: 84100kb

input:

200000 200000
7793598924465250299 11320616179551810509 4514956344247028440 13595219380199005841 9022300443122747211 5306720789215014051 12829201090248291001 17484907120965865432 4426007998575926549 16938003364463208590 8456717373555158888 9856394533639307403 4263328592244098713 4497412961128822026 1...

output:

10753764993328700009 
18007939111928197938 
9749484091345535325 
5504011101575545606 
13062921586637652283 
11960644823021452066 
5934883515296641825 
14816522537666728261 
11155114586067595959 
7338645965836498696 
6416169899635462788 
11575170211633743517 
11478197945758314236 
5225462134046697629...

result:

ok 200000 lines

Subtask #6:

score: 19
Accepted

Test #34:

score: 19
Accepted
time: 1309ms
memory: 81648kb

input:

200000 200000
6794776813641982926 1561596256197101737 10910039723053043515 7892247858295192798 12233819960547881004 17695389034783066733 9173201689566865598 17626618141377486739 7358781671024283919 6787559733384974662 3884392438269280436 14872846228351316833 9037842441501571648 14299818404271084016 ...

output:

5519324519442957729 
13462861144392030499 
8898301730697138469 
4148979398311169421 
15090246851327208067 
8628707816538336707 
13867297907038176506 
10296428352441857103 
15654304415409320656 
7404566644919251615 
9870876264015800597 
6356224262148620783 
249874952637342736 
9023132497407647441 
14...

result:

ok 200000 lines

Test #35:

score: 19
Accepted
time: 806ms
memory: 85428kb

input:

200000 200000
11863650499568632095 6646669915142734572 4053375998669045948 14662364203830894482 7319511971537928619 4131498054494361157 7103043576860354080 2730587527012777841 8626012955062792888 7098277606750148625 12990209623538415680 100871355087529915 12267084290544303817 7008468684400973426 856...

output:

11796827338356402281 
853302424664654652 
564419876379363056 
11173501553976506440 
2595891684253320024 
5590778053561483334 
16613470245879883493 
5698255402711241072 
8125718572356459513 
11371252602486101178 
7605800585391618993 
17939653588292877927 
15906636118593883045 
14840423959426947118 
1...

result:

ok 200000 lines

Test #36:

score: 19
Accepted
time: 1858ms
memory: 83436kb

input:

200000 200000
7819034666999754227 1261434745131385029 4729051582132640442 9603230030483067185 9188148629137054368 4647584887897271213 14878584596185020248 5036501082632549589 13434605396022727436 10747373329537943689 2859138487129973374 17399126170759425906 5170686633178482234 1548518177806164267 68...

output:

13979872615900358449 
13089809959604496472 
1561607543806976909 
704865086165131395 
4750114500765789463 
8620101000132483891 
1061990993707638791 
8219417779659049453 
16783172337878697026 
731502258552473136 
15516870835064396649 
13412140913912394465 
5029558179142432386 
9655856473800271062 
144...

result:

ok 200000 lines

Test #37:

score: 19
Accepted
time: 1847ms
memory: 85464kb

input:

200000 200000
13667364256171297683 5643454264481609425 13916992424255487273 16139471110620927446 10964822257543206396 18104319795931117637 6754294313610492941 627150985476406559 9787453073837140391 8330282299925244302 16457178623381098023 2644823686047461659 3971198924127091796 9747389824949735337 1...

output:

11367465309833674818 
18362877133708215281 
7423548724337603968 
8957456044849213851 
17833913066069915980 
7858235162317128668 
12543057704351927321 
10505054748074388644 
6816176482433035300 
2467436539272277421 
1679282916199502250 
4514431222303891247 
8020348968469583082 
4250522620562980350 
3...

result:

ok 200000 lines

Test #38:

score: 19
Accepted
time: 465ms
memory: 81588kb

input:

200000 200000
8264785020939323331 5620958879723030311 933008402364228745 5711653520387260744 16167130674961631916 10635243671618608635 7034482071437480120 10254956504177159052 10510387087831623788 8381634740474427698 9506597691312026965 14784451691298216046 15821757099494287606 1919888068508281591 1...

output:

5787014875832445646 
9634577796009446262 
12314294073540302873 
2915216425908688602 
7120463906657998875 
4286046781319255714 
6776880553034928756 
7781782119312943753 
10261843991161497641 
6413565360321098258 
15025688638596291097 
9526784383328827422 
4012177064000612489 
1287077077700121461 
987...

result:

ok 200000 lines

Test #39:

score: 19
Accepted
time: 1923ms
memory: 82116kb

input:

200000 200000
11664667196988092805 1811572170904050995 15694419630875459125 12737549840477675073 16755302998318006416 4014818780481352253 5609118000649893828 6256332194728466258 15733576495075669968 17960532384856428505 15897732465031414620 17425753576410476171 4620624862371502705 112264419736513372...

output:

6480474289914832244 
5686011217288555755 
14160731859453855234 
17554436276709117739 
2341367826083254204 
8545580044567165676 
264741062779916095 
3300445074446425091 
1133253489203829542 
15906618027983611292 
4617068730941954223 
9183813939934374009 
17667722659841632674 
17058280131349615456 
59...

result:

ok 200000 lines

Test #40:

score: 19
Accepted
time: 1902ms
memory: 85020kb

input:

200000 200000
1537940886958943461 9001579450047645548 5527298164056925772 15445874594277229387 11547996012713764596 2685142508745516922 15898551218448062337 16566357055814699599 15778851736432174335 10222916087451023672 14639095824490451029 13130899683058695675 2954207938828868462 150325623383373666...

output:

6794024285749225899 
15444253183026756906 
16252225983581025191 
18270054647591833460 
14669804966517502833 
7889126920459519979 
11162985402720101082 
6093427967053788994 
10568703419124160247 
10842018941076619829 
12114458223856608006 
16611571295135208112 
6660992456255029750 
148542891421382500...

result:

ok 200000 lines

Test #41:

score: 19
Accepted
time: 1865ms
memory: 85080kb

input:

200000 200000
9312450956088465409 13091411438344500136 13533801408631028803 397220365455228788 9050318983523848941 14099016315633088068 17718824544128458130 18224580765371017222 16359847342241893914 6209442109030804295 8140737573685484628 16329892452717577856 12435238272437023209 1214903064014288477...

output:

17881136615169673858 
10075746974396262535 
1101717753396811008 
11092187645455964376 
312406901260616120 
15269190090424605570 
16293852523769965660 
7287397773622456008 
12586683442681630396 
10525460771223157010 
16483491603350167181 
5677129374080663282 
17770626863503596216 
1624138803450296047...

result:

ok 200000 lines

Subtask #7:

score: 20
Accepted

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

100%
Accepted

Dependency #4:

100%
Accepted

Dependency #5:

100%
Accepted

Dependency #6:

100%
Accepted

Test #42:

score: 20
Accepted
time: 2738ms
memory: 77512kb

input:

200000 200000
14540531313498226604 15389593605284580565 17781520426173506729 5832916091757234151 1848270997071173135 259061641843035350 8788725452029787311 7822255353565964065 2898146987051246947 16706450117617402631 18331448939496919494 11033274730694739396 3160887349810243541 9508620871820353151 1...

output:

17049938353951458115 
16201366126815963436 
15179590980620847012 
13523808932520753304 
18113661789553960601 
8039040892211880124 
246246849438183107 
2555100487772408152 
11194634462590564840 
5473066630455037966 
10281959280827743038 
15251719183697066440 
6002473457749888560 
5627648438789929583 ...

result:

ok 200000 lines

Test #43:

score: 20
Accepted
time: 1825ms
memory: 77588kb

input:

200000 200000
15918718481510652081 9040859920711789151 12399253023156465997 15645172606577164777 8083913706263123652 1759761994701635321 2013692435488690597 4174541162058903190 13694743549251724395 937888942370311846 4610104970367349522 9759012637166281205 7661043296876818329 10083206476714160525 16...

output:

11758732603542040525 
6923029958385052626 
17744573648670581503 
17077426643695313258 
8379372046406886334 
11072709831115448376 
940310146171950761 
9302248644083169165 
9729177136908768259 
3411977062759649501 
4466809099265801563 
6420491908745700617 
3905612714574332682 
14775225054894331987 
43...

result:

ok 200000 lines

Test #44:

score: 20
Accepted
time: 2056ms
memory: 77660kb

input:

200000 200000
17956619288159616954 10556553630289872840 15135502507722920974 13635123079776064177 9449656174452616725 1322724587213896301 18126543853033337874 5522292839124337292 12233137909466701604 17210013976051153447 7376083586917806911 11218732974526180022 9139950084057141111 110543368178528823...

output:

14765424723327792934 
8343698174832872301 
18098775875078336114 
18079539614935601327 
4542566753840425614 
13147285472592498383 
8761562420482000370 
13462926476075203839 
2680413257467703181 
1808344823315079313 
11807389387596478019 
12373904170649709441 
15670529126846696674 
2748127049783302843...

result:

ok 200000 lines

Test #45:

score: 20
Accepted
time: 2048ms
memory: 78444kb

input:

200000 200000
12250593392176518387 14958497980877902399 1417594180024650695 16267781615346740953 17613673585037294934 7139866418501087608 14929190017763396282 7435850532886934407 15096081909787242638 3292071312650754133 10091770298388939144 9191440695608806547 10490644359152758842 245434676950104657...

output:

9528427087279617641 
6430271970724029222 
8551111075441013570 
12985522103146607579 
13261271598818001344 
6859257690792251190 
445935698849376914 
12525891233567283656 
10898698373151607636 
11648052816467704877 
5353376459792790954 
7553930593008385765 
3622856558846827618 
16340325355724880322 
2...

result:

ok 200000 lines

Test #46:

score: 20
Accepted
time: 2032ms
memory: 79472kb

input:

200000 200000
15578130172661602915 4040243377896436560 7335383848748660045 9318072359765539874 15787007911105275478 14459397046982340771 12992090766931271542 14106348304681315921 7322750974307005742 13791122915211248763 4966042906976888045 1521814066577948738 7304263231409129465 14216592527499785253...

output:

3105695271661622878 
12759649760145987629 
4526942927386726915 
13000841195352685704 
7544252433413568963 
15425838017113049750 
13966412148249313434 
9340285826280561129 
10586504764054162497 
11182661161293796166 
2169083424750127057 
2913495396953510257 
10377841900238924790 
4926438481444151555 ...

result:

ok 200000 lines

Test #47:

score: 20
Accepted
time: 1483ms
memory: 75684kb

input:

200000 200000
325468914533218620 2428955728441197495 3735365409298831845 7325608096855386373 15673684303040941373 11665741652453695398 6693460773879815803 17908597805564615946 13254159657178912688 16259557593423455737 14914702982645468143 15632760869464904669 10188910957601652837 1662761521939034133...

output:

16902441545843226798 
2849531605983381979 
4560681691795519357 
7110106191263741943 
14803637399068390 
16059537132829622407 
11975522120793320311 
14112772792168330741 
6702236014725950572 
16890424121380166450 
18190346695204463590 
12347986781120582235 
4541511294950722999 
9278100506107235404 
1...

result:

ok 200000 lines

Test #48:

score: 20
Accepted
time: 2043ms
memory: 76524kb

input:

200000 200000
14934992724968072786 18285832870901492513 14828079101214074811 16126248007174860749 13182466895916509794 8983774054749199244 9680738082425504773 9008819761796848095 6983320676869955138 8880956025549740677 12839986818649750595 7815881827220827933 5876046146531041804 4647074279773193178 ...

output:

17834543877423299606 
5945352964781774389 
16254243783650983160 
3016995116635801112 
4498076540627741305 
10662235968784890080 
13736145455986456515 
14819195169367657116 
4392358739844414420 
8515755773557139770 
10275733712097943912 
17430191788870683657 
12565039700900590900 
5330780274015215009...

result:

ok 200000 lines

Test #49:

score: 20
Accepted
time: 1943ms
memory: 76916kb

input:

200000 200000
7733627180607634195 3698228143815722201 315941954502039975 7865167447791063071 14024510504432539346 3242747152853653155 9324538526970752021 4508478783648810776 8648239571241818711 16406000947776978297 17752282737962421449 10792802411776243742 745357055591881947 13784169290639768239 211...

output:

15287415572630919792 
15470574694884612856 
16948996586384707369 
6812124956908704769 
12311213465149628084 
12844999976840220113 
16656406905560309441 
12922459742324443127 
11607992685059291621 
7027621208943865829 
2684608325191356405 
5192475809235539972 
9066829527675264918 
1671593167920979024...

result:

ok 200000 lines

Test #50:

score: 20
Accepted
time: 2037ms
memory: 78076kb

input:

200000 200000
4698493261435599995 4390284109199531675 5777144265562724770 15068699434272862607 11148954315024552445 7739578260268323344 18287596451938460794 4832409057537892865 8254099224730817029 9200890861168236202 14335368926597094726 7018957700252807093 16858164596918236486 1763061237341633148 5...

output:

15306462248243475589 
13433006779928090628 
4078947887270684881 
10542832878323554849 
12685573746562999611 
9433537877758316077 
16046889962459596415 
3844118441391846567 
8833462019080542136 
7324524420996417416 
3419948746707421055 
396934735191217705 
900746509694171741 
3880266916990677590 
658...

result:

ok 200000 lines