QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#739457	#9609. 幽默还是夢	I_be_wanna	100 ✓	1531ms	80312kb	C++14	10.4kb	2024-11-12 21:48:44	2024-11-12 21:48:46

Judging History

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

[2024-11-12 21:48:46]
评测

测评结果：100
用时：1531ms
内存：80312kb

查看

[2024-11-12 21:48:44]
提交

answer

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

using LL = long long;

struct Oper {
  int op, x, y, z;
  Oper(int op = 0, int x = 0, int y = 0, int z = 0)
      : op(op), x(x), y(y), z(z) {}
};
vector<LL> ans;

constexpr int N = 2E5;
constexpr int Inf = 2E9;

int n, O;
priority_queue<int> val1[N], del1[N];
priority_queue<int, vector<int>, greater<int>> val2[N], del2[N];

int cnt[4 * N + 10], mx[4 * N + 10], mn[4 * N + 10];
LL sum[4 * N + 10];

int pre[N], suf[N];
LL res[N];

void init(int n, int q) {
  ::n = n;
  for (O = 1; O < n + 2; O <<= 1);
  fill(mx, mx + O + n + 2, -Inf);
  fill(mn, mn + O + n + 2, Inf);
  fill(pre, pre + q, -Inf);
  fill(suf, suf + q, Inf);
}

void clr(int p) {
  while (val1[p].size()) val1[p].pop();
  while (val2[p].size()) val2[p].pop();
  while (del1[p].size()) del1[p].pop();
  while (del2[p].size()) del2[p].pop();
  for (int u = O + 1 + p; u; u >>= 1) {
    cnt[u] = sum[u] = 0;
    mx[u] = -Inf, mn[u] = Inf;
  }
}

void appVal(int p, int v, int op) {
  for (int u = O + 1 + p; u; u >>= 1) {
    cnt[u] += op;
    sum[u] += v * op;
  }
}
void appMax(int p, int v, int op) {
  if (op == 1) val1[p].emplace(v);
  else del1[p].emplace(v);
  while (val1[p].size() && del1[p].size() && val1[p].top() == del1[p].top()) {
    val1[p].pop();
    del1[p].pop();
  }
  mx[O + 1 + p] = (val1[p].size() ? val1[p].top() : -Inf);
  for (int u = (O + 1 + p) >> 1; u; u >>= 1) {
    mx[u] = max(mx[u << 1], mx[u << 1 | 1]);
  }
}
void appMin(int p, int v, int op) {
  if (op == 1) val2[p].emplace(v);
  else del2[p].emplace(v);
  while (val2[p].size() && del2[p].size() && val2[p].top() == del2[p].top()) {
    val2[p].pop();
    del2[p].pop();
  }
  mn[O + 1 + p] = (val2[p].size() ? val2[p].top() : Inf);
  for (int u = (O + 1 + p) >> 1; u; u >>= 1) {
    mn[u] = min(mn[u << 1], mn[u << 1 | 1]);
  }
}

int qC, qMx, qMn;
LL qS;

void qry(int l, int r) {
  l = O + l, r = O + r + 2;
  qC = qS = 0, qMx = -Inf, qMn = Inf;
  while (l ^ r ^ 1) {
    if (~l & 1) {
      qC += cnt[l ^ 1];
      qS += sum[l ^ 1];
      qMx = max(qMx, mx[l ^ 1]);
      qMn = min(qMn, mn[l ^ 1]);
    }
    if (r & 1) {
      qC += cnt[r ^ 1];
      qS += sum[r ^ 1];
      qMx = max(qMx, mx[r ^ 1]);
      qMn = min(qMn, mn[r ^ 1]);
    }
    l >>= 1, r >>= 1;
  }
}

vector<int> rag;

void solve(vector<Oper> &oper, int l, int r) {
  if (!oper.size()) return;
  if (l == r) {
    for (auto [op, x, y, z] : oper) {
      if (op >= 100) {
        qry(x, y);
        pre[op - 100] = max(pre[op - 100], qMx);
        suf[op - 100] = min(suf[op - 100], qMn);
        res[op - 100] += qS;
        LL nans = res[op - 100] - LL(qC - z) * rag[l];
        if ((qC - z) % 2 == 0) {
          ans[op - 100] = nans;
        } else {
          ans[op - 100] = nans + min(rag[l] - pre[op - 100], suf[op - 100] - rag[l]);
        }
      } else {
        if (abs(op) == 1) {
          appVal(x, y, op);
          appMax(x, y, op);
        } else {
          appVal(x, y, op);
          appMax(x, 2 * y - z, op / 2);
        }
      }
    }
    for (auto [op, x, y, z] : oper) {
      if (op < 100) {
        clr(x);
      }
    }
    return;
  }
  int mid = (l + r) / 2;
  bool has1 = false, has2 = false;
  vector<Oper> oper1, oper2;
  for (auto [op, x, y, z] : oper) {
    if (op >= 100) {
      qry(x, y);
      if (z <= qC) {
        suf[op - 100] = min(suf[op - 100], qMn);
        oper1.emplace_back(op, x, y, z);
        has1 = true;
      } else {
        pre[op - 100] = max(pre[op - 100], qMx);
        res[op - 100] += qS;
        oper2.emplace_back(op, x, y, z - qC);
        has2 = true;
      }
    } else {
      if (y <= rag[mid]) { // update value and prefix max
        if (abs(op) == 1) {
          appVal(x, y, op);
          appMax(x, y, op);
        } else {
          appVal(x, y, op);
          appMax(x, 2 * y - z, op / 2);
        }
        oper1.emplace_back(op, x, y, z);
      } else { // update suffix min
        if (abs(op) == 1) {
          appMin(x, y, op);
        } else {
          appMin(x, z, op / 2);
        }
        oper2.emplace_back(op, x, y, z);
      }
    }
  }
  for (auto [op, x, y, z] : oper) {
    if (op < 100) {
      clr(x);
    }
  }
  if (has1) solve(oper1, l, mid);
  if (has2) solve(oper2, mid + 1, r);
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, q;
  cin >> n >> q;
  vector<int> a(n), b(n);
  vector<Oper> oper;
  auto add = [&](int v, int i) {
    if (a[i] <= b[i] - a[i]) {
      oper.emplace_back(v, i, a[i] * 2);
      oper.emplace_back(v, i, (b[i] - a[i]) * 2);
      rag.emplace_back(a[i] * 2);
      rag.emplace_back((b[i] - a[i]) * 2);
    } else {
      oper.emplace_back(v * 2, i, b[i], a[i] * 2);
      rag.emplace_back(b[i]);
    }
  };
  for (int i = 0; i < n; ++i) {
    cin >> a[i] >> b[i];
    add(1, i);
  }
  for (int i = 0; i < q; ++i) {
    int op;
    cin >> op;
    if (op == 1) {
      int p, x, y;
      cin >> p >> x >> y;
      add(-1, p);
      a[p] = x, b[p] = y;
      add(1, p);
    } else {
      int l, r, k;
      cin >> l >> r >> k; // 0 <= l, r < n
      oper.emplace_back(100 + i, l, r, k);
    }
  }
  sort(rag.begin(), rag.end());
  rag.erase(unique(rag.begin(), rag.end()), rag.end());
  ans.assign(q, -1);
  init(n, q);
  solve(oper, 0, int(rag.size()) - 1);
  for (int i = 0; i < q; ++i) {
    if (~ans[i]) {
      cout << ans[i] / 2 << "\n";
    }
  }
  fprintf(stderr, "TIME: %.2f\n", double(clock()) / CLOCKS_PER_SEC);
  return 0;
}
/*#include <bits/stdc++.h>
using namespace std;

using LL = long long;

struct Oper {
  int op, x, y, z;
  Oper(int op = 0, int x = 0, int y = 0, int z = 0)
      : op(op), x(x), y(y), z(z) {}
};
vector<LL> ans;

constexpr int N = 2E5;
constexpr int Inf = 2E9;

int n, O;
priority_queue<int> val1[N], del1[N];
priority_queue<int, vector<int>, greater<int>> val2[N], del2[N];

int cnt[4 * N + 10], mx[4 * N + 10], mn[4 * N + 10];
LL sum[4 * N + 10];

int pre[N], suf[N];
LL res[N];

void init(int n, int q) {
  ::n = n;
  for (O = 1; O < n + 2; O <<= 1);
  fill(mx, mx + O + n + 2, -Inf);
  fill(mn, mn + O + n + 2, Inf);
  fill(pre, pre + q, -Inf);
  fill(suf, suf + q, Inf);
}

void clr(int p) {
  while (val1[p].size()) val1[p].pop();
  while (val2[p].size()) val2[p].pop();
  while (del1[p].size()) del1[p].pop();
  while (del2[p].size()) del2[p].pop();
  for (int u = O + 1 + p; u; u >>= 1) {
    cnt[u] = sum[u] = 0;
    mx[u] = -Inf, mn[u] = Inf;
  }
}

void appVal(int p, int v, int op) {
  for (int u = O + 1 + p; u; u >>= 1) {
    cnt[u] += op;
    sum[u] += v * op;
  }
}
void appMax(int p, int v, int op) {
  if (op == 1) val1[p].emplace(v);
  else del1[p].emplace(v);
  while (val1[p].size() && del1[p].size() && val1[p].top() == del1[p].top()) {
    val1[p].pop();
    del1[p].pop();
  }
  mx[O + 1 + p] = (val1[p].size() ? val1[p].top() : -Inf);
  for (int u = (O + 1 + p) >> 1; u; u >>= 1) {
    mx[u] = max(mx[u << 1], mx[u << 1 | 1]);
  }
}
void appMin(int p, int v, int op) {
  if (op == 1) val2[p].emplace(v);
  else del2[p].emplace(v);
  while (val2[p].size() && del2[p].size() && val2[p].top() == del2[p].top()) {
    val2[p].pop();
    del2[p].pop();
  }
  mn[O + 1 + p] = (val2[p].size() ? val2[p].top() : Inf);
  for (int u = (O + 1 + p) >> 1; u; u >>= 1) {
    mn[u] = min(mn[u << 1], mn[u << 1 | 1]);
  }
}

int qC, qMx, qMn;
LL qS;

void qry(int l, int r) {
  l = O + l, r = O + r + 2;
  qC = qS = 0, qMx = -Inf, qMn = Inf;
  while (l ^ r ^ 1) {
    if (~l & 1) {
      qC += cnt[l ^ 1];
      qS += sum[l ^ 1];
      qMx = max(qMx, mx[l ^ 1]);
      qMn = min(qMn, mn[l ^ 1]);
    }
    if (r & 1) {
      qC += cnt[r ^ 1];
      qS += sum[r ^ 1];
      qMx = max(qMx, mx[r ^ 1]);
      qMn = min(qMn, mn[r ^ 1]);
    }
    l >>= 1, r >>= 1;
  }
}

vector<int> rag;

void solve(vector<Oper> &oper, int l, int r) {
  if (!oper.size()) return;
  if (l == r) {
    for (auto [op, x, y, z] : oper) {
      if (op >= 100) {
        qry(x, y);
        pre[op - 100] = max(pre[op - 100], qMx);
        suf[op - 100] = min(suf[op - 100], qMn);
        res[op - 100] += qS;
        LL nans = res[op - 100] - LL(qC - z) * rag[l];
        if ((qC - z) % 2 == 0) {
          ans[op - 100] = nans;
        } else {
          ans[op - 100] = nans + min(rag[l] - pre[op - 100], suf[op - 100] - rag[l]);
        }
      } else {
        if (abs(op) == 1) {
          appVal(x, y, op);
          appMax(x, y, op);
        } else {
          appVal(x, y, op);
          appMax(x, 2 * y - z, op / 2);
        }
      }
    }
    for (auto [op, x, y, z] : oper) {
      if (op < 100) {
        clr(x);
      }
    }
    return;
  }
  int mid = (l + r) / 2;
  bool has1 = false, has2 = false;
  vector<Oper> oper1, oper2;
  for (auto [op, x, y, z] : oper) {
    if (op >= 100) {
      qry(x, y);
      if (z <= qC) {
        suf[op - 100] = min(suf[op - 100], qMn);
        oper1.emplace_back(op, x, y, z);
        has1 = true;
      } else {
        pre[op - 100] = max(pre[op - 100], qMx);
        res[op - 100] += qS;
        oper2.emplace_back(op, x, y, z - qC);
        has2 = true;
      }
    } else {
      if (y <= rag[mid]) { // update value and prefix max
        if (abs(op) == 1) {
          appVal(x, y, op);
          appMax(x, y, op);
        } else {
          appVal(x, y, op);
          appMax(x, 2 * y - z, op / 2);
        }
        oper1.emplace_back(op, x, y, z);
      } else { // update suffix min
        if (abs(op) == 1) {
          appMin(x, y, op);
        } else {
          appMin(x, z, op / 2);
        }
        oper2.emplace_back(op, x, y, z);
      }
    }
  }
  for (auto [op, x, y, z] : oper) {
    if (op < 100) {
      clr(x);
    }
  }
  if (has1) solve(oper1, l, mid);
  if (has2) solve(oper2, mid + 1, r);
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int n, q;
  cin >> n >> q;
  vector<int> a(n), b(n);
  vector<Oper> oper;
  auto add = [&](int v, int i) {
    if (a[i] <= b[i] - a[i]) {
      oper.emplace_back(v, i, a[i] * 2);
      oper.emplace_back(v, i, (b[i] - a[i]) * 2);
      rag.emplace_back(a[i] * 2);
      rag.emplace_back((b[i] - a[i]) * 2);
    } else {
      oper.emplace_back(v * 2, i, b[i], a[i] * 2);
      rag.emplace_back(b[i]);
    }
  };
  for (int i = 0; i < n; ++i) {
    cin >> a[i] >> b[i];
    add(1, i);
}*/

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5

Accepted

Test #1:

score: 5

Accepted

time: 3ms

memory: 37784kb

input:

output:

12
9

result:

ok 2 number(s): "12 9"

Test #2:

score: 5

Accepted

time: 0ms

memory: 38132kb

input:

output:

5
7

result:

ok 2 number(s): "5 7"

Test #3:

score: 5

Accepted

time: 0ms

memory: 38264kb

input:

output:

5
4
13

result:

ok 3 number(s): "5 4 13"

Test #4:

score: 5

Accepted

time: 3ms

memory: 37984kb

input:

14 14
137604651 148051578
362722420 701127241
112668315 125437888
287900155 387914570
372764764 835453510
487901436 886003378
220152717 420521021
398973222 512891403
388384759 595247888
89781009 585869215
26792323 118929846
336453982 364990768
321824819 613043271
388186725 818512652
1 6 181262309 25...

output:

result:

ok 11 numbers

Test #5:

score: 5

Accepted

time: 0ms

memory: 38568kb

input:

output:

result:

ok 10 numbers

Test #6:

score: 5

Accepted

time: 0ms

memory: 37632kb

input:

output:

result:

ok 4 number(s): "3 143 17 1"

Test #7:

score: 5

Accepted

time: 0ms

memory: 38488kb

input:

14 14
257829907 724715537
108651452 258598766
94683229 173211791
479210658 582119116
54540156 428302979
52455936 383613089
490920498 513399791
352653592 701946471
340154330 398349800
121686359 192733077
88773311 129421949
320698287 575819706
170879293 344150256
302356504 521941463
2 3 12 10
1 8 2452...

output:

result:

ok 9 numbers

Subtask #2:

score: 5

Accepted

Dependency #1:

100%

Accepted

Test #8:

score: 5

Accepted

time: 4ms

memory: 38292kb

input:

300 300
236272593 367977426
193245445 202346765
154060783 238627896
266263504 714515068
326570377 765576129
319118394 352576872
105744828 271847570
1123063 437252936
292326814 652693639
119178460 320083080
392059409 484903780
178885480 591157929
273931331 692199866
156093219 524526946
323752415 8226...

output:

12903467467
12140459036
15087634605
27198807498
29428660401
6169823972
15045538543
4383591
2359669927
1063857724
694501138
24620774975
9566547346
65353375060
10241685703
121125504
13264370395
9581854028
14132735946
77877326550
285563821
9085006335
18424522279
7729941213
6497908382
28538021992
662892...

result:

ok 146 numbers

Test #9:

score: 5

Accepted

time: 4ms

memory: 39240kb

input:

300 300
244663179 509035792
332903389 613341357
161987994 606940171
336723050 507606507
145455363 204317531
169573385 379283435
177050397 562868538
431733852 523770709
212243619 281715538
83255800 160178888
294475851 697375668
343483612 775166562
281248069 495482283
138995617 554668578
194259365 216...

output:

40254603
16369627943
2448905059
1868439239
1057562633
7471849467
14589706661
50073674230
3644726912
63713269
13049201228
16762172359
17712958839
18411593284
8546622062
33190286201
18793253982
10814998349
5882894800
15312531098
52138307
13762650523
1488748067
22823558723
11962399128
41833685078
40483...

result:

ok 143 numbers

Test #10:

score: 5

Accepted

time: 4ms

memory: 37976kb

input:

300 300
72911832 469485383
105942845 273018682
232457225 578806174
269721902 378206843
103384491 595940124
364126138 549620383
468136415 829403771
79997976 363085297
320307362 535761950
395259575 761297849
241479722 357024290
411307155 562957441
288347269 448717572
256345663 393867710
363610578 4187...

output:

6913154278
2842330034
2185597552
32914182697
3349781269
33240231006
13292793883
35013050874
36781788100
4492425969
733292842
2680419448
28899224522
178152769
3612931177
15062161441
4227210687
2083096048
62437668974
9145335161
20152648
1755242090
462627834
3738164822
3792823081
59119687341
1413096882...

result:

ok 170 numbers

Test #11:

score: 5

Accepted

time: 3ms

memory: 39472kb

input:

output:

result:

ok 140 numbers

Test #12:

score: 5

Accepted

time: 3ms

memory: 40536kb

input:

output:

result:

ok 142 numbers

Subtask #3:

score: 15

Accepted

Dependency #2:

100%

Accepted

Test #13:

score: 15

Accepted

time: 10ms

memory: 41292kb

input:

2000 2000
492156297 891105567
457854002 671145682
119875716 213459413
129540041 445263628
45723424 297701781
243530727 413420086
343868745 465766786
39585054 342872573
245699946 297595828
283288483 332910548
19248601 74422280
305868175 725593305
137155918 635077642
186537009 320193545
449764641 9168...

output:

769333315
31814430233
192156363
10731582114
310909096915
205483963778
124233092017
268012585576
164616784041
38053660249
9480536842
158352240104
407150954886
17063476029
82258316259
21369738423
3266683042
272282626186
556810418612
75466361119
398580395
186178907785
564338317766
145374417881
27185904...

result:

ok 965 numbers

Test #14:

score: 15

Accepted

time: 8ms

memory: 39920kb

input:

2000 2000
199918641 456527544
260775423 495168036
454126239 624980472
25503786 95958076
23049625 205204895
398321843 644801632
23803572 367932566
63791123 443652304
16717424 461899786
57182702 134288560
7367915 413777915
461864555 750003900
221881777 613181615
121094 462492090
235789679 722704353
13...

output:

119394915468
17941562480
279125740743
2233864829
106860370137
54758865798
143679361393
1877398337
779567529317
40363989047
263489643774
55000571549
7132978602
18526821294
222577978228
15638261704
161092153447
156826695129
36606198617
220813405946
60955688238
275212249345
221129445815
59748325945
163...

result:

ok 969 numbers

Test #15:

score: 15

Accepted

time: 9ms

memory: 41156kb

input:

2000 2000
497204382 995759939
221489796 251373672
498330228 556418029
450120891 715563300
307205005 406128293
215762347 678991374
86646319 139613276
8016302 35662129
25286265 324810382
371712021 641916776
63661846 497446528
458951932 868655385
10641798 205365852
319615379 615786917
90106107 41041485...

output:

13741251535
23390871836
13803366145
6846598624
164727658887
161453438707
151504751806
4382792638
1888841444
43321838168
118063814074
62184098093
132756597809
7616990021
65196341872
104234091197
148562690039
161010686208
108370261703
185354238433
202041650695
205544165494
65269540158
14074240805
5254...

result:

ok 991 numbers

Test #16:

score: 15

Accepted

time: 7ms

memory: 39088kb

input:

output:

result:

ok 1000 numbers

Test #17:

score: 15

Accepted

time: 8ms

memory: 40284kb

input:

output:

result:

ok 989 numbers

Subtask #4:

score: 15

Accepted

Test #18:

score: 15

Accepted

time: 317ms

memory: 64236kb

input:

100000 100000
14 26
20 23
12 27
12 26
19 31
19 36
19 31
4 20
6 10
10 20
3 6
5 8
12 23
2 14
11 15
7 12
4 8
3 11
17 32
5 21
20 37
14 23
11 15
1 8
10 18
9 26
15 34
14 20
4 19
1 20
13 18
1 5
9 21
3 6
12 18
18 24
2 12
10 22
7 21
4 7
13 20
11 23
19 37
5 18
15 18
12 26
8 10
7 23
7 26
17 23
4 15
15 22
2 10
...

output:

result:

ok 100000 numbers

Test #19:

score: 15

Accepted

time: 283ms

memory: 65440kb

input:

100000 100000
20 29
5 15
16 25
1 21
19 34
7 10
12 13
14 30
12 30
8 13
1 7
3 10
1 14
4 10
10 28
20 37
7 14
14 29
6 19
17 21
10 22
3 17
3 6
10 24
3 22
1 13
3 19
7 12
20 29
6 25
2 7
10 12
18 19
16 22
1 8
1 3
20 40
1 5
10 22
1 2
16 21
5 24
5 13
20 33
16 35
1 5
14 28
16 20
4 23
15 20
20 36
9 14
10 23
2 8...

output:

result:

ok 100000 numbers

Test #20:

score: 15

Accepted

time: 734ms

memory: 63952kb

input:

100000 100000
495149378 762667561
92804801 308704323
260829713 509258393
134985566 187603067
383688858 757703758
42584446 252140878
166171841 311884216
58894085 484698822
179904149 225131551
106046268 116048600
328369376 585575759
218728521 630432352
68063601 359383282
460115977 601281324
220720076 ...

output:

1812758092870
716777280196
6762481378372
5393411023109
20387004166659
276374836225
14393163199104
9060733840
708586821641
4402046274097
2995328388042
2426475426800
21365055698803
11654990261354
51051781302
807378906271
208257912510
14473781318613
2205074631517
2421075838275
1065039429683
16657175932...

result:

ok 100000 numbers

Test #21:

score: 15

Accepted

time: 865ms

memory: 63064kb

input:

100000 100000
317671798 724513306
267415730 720622263
438259841 609710587
338546641 679403828
414231034 428534303
72643161 493536554
351537022 385752969
99714633 133544561
22698327 381893760
176354095 231931408
489389965 775484006
264484999 269535193
240651757 350055491
3198275 407316049
308982646 5...

output:

239664815650
928888656042
2522829786033
43421209836739
5936815154306
12853457653071
1732783572874
8251302341580
709067422607
238590288446
40977678771
10727804866349
7476507892776
29223998617343
771404401863
25709809527597
189506325987
1482915516071
5309113956440
9169425573176
3902737030445
710730162...

result:

ok 100000 numbers

Test #22:

score: 15

Accepted

time: 759ms

memory: 64376kb

input:

100000 100000
350918315 359860548
469242404 928286463
199848321 507144420
266406590 637249851
92353752 538740822
355402324 492949190
77210679 423543086
60409773 435780188
12858185 328118533
436007287 856917524
233221654 545374045
4445595 334802817
14919077 428793589
285244243 337211810
48048546 4072...

output:

8051083624579
23566016619108
2179111806525
5316969302824
17783792865680
14832397287
3427227827375
5749419168056
25052813811875
9471567687067
15120661365228
13742344324346
409345333144
2222638824482
87246968549
31257792038098
12310709907568
4140428882471
9136752968253
2947148850202
29726531818326
168...

result:

ok 100000 numbers

Subtask #5:

score: 20

Accepted

Dependency #4:

100%

Accepted

Test #23:

score: 20

Accepted

time: 684ms

memory: 65512kb

input:

100000 100000
42072021 321809124
39872170 528597932
168585925 552562119
52246248 109524671
14770770 394983740
394986440 760758372
200610206 337295324
236903605 385901832
378712853 392866698
194639543 301474849
152944705 382720993
444881957 449478597
91981395 249429741
46866736 92449084
170002170 609...

output:

12256131816619
5168598209746
831671432639
2648148984271
5668619178376
495140428796
5570034058080
7844714247724
324634154543
3087905355809
22909504139876
784663794606
4973976072847
12580674106
14960179288492
11294234658777
482646064102
2339337364573
22679401106191
1334310362409
489271116946
809593662...

result:

ok 100000 numbers

Test #24:

score: 20

Accepted

time: 884ms

memory: 63296kb

input:

100000 100000
334637052 806195540
363358406 439507847
457589021 934731957
449465201 635359926
411815924 550005796
332440140 510392600
427357510 541195363
200194121 500001535
409072719 787768202
186689720 577015782
34009564 419688475
78505020 199378026
454786282 677626082
420700145 856988589
20865071...

output:

14293319455
4309002117152
3519091179166
4724687439551
3071910291748
1561428702301
418800747610
7054484136116
4495490595744
4919435161531
1049538308832
7373084770478
1891094424690
985583861919
721836749978
3801762884205
3671130882049
1668881184056
4165599384675
1782563225602
1211553659030
82797404666...

result:

ok 100000 numbers

Test #25:

score: 20

Accepted

time: 678ms

memory: 65188kb

input:

100000 100000
29088604 189163625
279923382 334676734
271040901 672934307
299620349 647700256
206152530 292298743
74369942 91957137
182072363 283099120
146507995 367654364
446672553 495293216
176531974 504858292
361380872 421212364
32178930 467780335
137366788 483788608
203313226 535311966
383683953 ...

output:

412369777227
16851705178447
422913729817
7919872713487
4611619504438
81245796670
14372310985716
187347606911
19040647907051
51264683605
3253344684405
23436004034094
22406561795002
288665240560
1033784582711
319846863052
167259641081
2900608079783
4268243087455
8436890128398
11836503978002
1105595334...

result:

ok 100000 numbers

Test #26:

score: 20

Accepted

time: 274ms

memory: 63968kb

input:

100000 100000
4 11
18 27
5 11
4 7
14 24
8 15
10 15
16 35
10 20
12 29
14 22
13 30
17 18
5 21
7 25
19 30
12 15
5 9
9 28
11 14
5 23
6 16
14 30
20 37
4 19
9 24
1 10
17 36
1 12
9 12
14 19
13 22
15 30
1 19
16 25
17 18
1 19
12 23
5 8
16 32
17 20
16 28
17 30
3 6
12 19
14 26
18 22
8 16
1 2
4 23
8 13
8 26
17 ...

output:

result:

ok 100000 numbers

Test #27:

score: 20

Accepted

time: 361ms

memory: 62176kb

input:

100000 100000
15 33
13 29
5 16
9 29
18 24
15 29
12 22
1 20
2 20
5 8
12 23
20 24
18 27
6 26
1 3
13 14
2 21
17 36
8 10
13 24
1 19
3 15
1 13
5 19
13 22
1 21
13 25
20 21
17 32
14 31
16 30
3 7
2 11
15 32
7 21
12 26
16 19
9 25
2 4
8 20
1 11
6 11
12 21
19 31
15 26
19 36
11 27
8 12
17 26
1 3
9 16
7 26
13 14...

output:

result:

ok 100000 numbers

Subtask #6:

score: 20

Accepted

Dependency #3:

100%

Accepted

Test #28:

score: 20

Accepted

time: 826ms

memory: 68092kb

input:

80000 80000
225354689 357421712
256970283 623358975
178383251 591207393
182615894 514317155
100808700 223792723
474091630 934549627
299874379 640509921
465635430 870489677
66892738 194064485
159834884 348499459
238168819 335814593
75986241 170063921
331860127 555061772
141800677 377649941
472424012 ...

output:

1762279935995
152583492030
517144080587
2477220778000
3494153362357
15293260287527
1776576246271
155282093361
2499857870870
162271062808
4370293512337
5413423315291
835337248692
242306033155
549102515584
1791806084707
889433171668
4323772395399
2533800070350
6337224579515
4360220916646
83224464908
5...

result:

ok 40040 numbers

Test #29:

score: 20

Accepted

time: 1059ms

memory: 73976kb

input:

80000 80000
466531356 551003849
190558763 390367786
462444921 779506042
370123580 753306808
300258431 659711385
252697279 511279935
44496271 274563035
376949880 707132432
422475659 764554784
167140484 645659252
98255291 537769304
452104417 509385384
21059793 56627313
336723789 701069885
472984029 92...

output:

1798699219643
234273928994
11158454906
1236025818935
17621549995
8431886526
12458103843
6608267925536
3329132139914
429447661710
1320524794237
3452347251370
1513764727820
1172629834209
140415867316
5320987568758
2083959022699
1417968101650
3453475785567
7464097434672
462455431396
1138020946533
16006...

result:

ok 40065 numbers

Test #30:

score: 20

Accepted

time: 789ms

memory: 71916kb

input:

80000 80000
213904970 335874002
11113047 134739857
289282252 478573320
155584174 520238373
74961190 96320075
60611155 456183205
264691501 342673041
279370823 488966819
236824214 611976325
292781630 386954010
181444664 320703964
250701759 598512929
152701579 242954176
74762826 347613326
256568972 755...

output:

14963722157365
3231968115664
371797683828
2387921132369
546980022807
3285168751793
7352242559202
350245316718
3657327775088
24335460700878
218723712872
190624040625
7342794083512
2389496888869
4828837321987
3526258628281
14183087586383
826901119189
4010570301133
2818425026519
11076686884769
67830162...

result:

ok 39907 numbers

Test #31:

score: 20

Accepted

time: 391ms

memory: 70168kb

input:

80000 80000
15 27
14 19
4 17
19 34
18 35
16 27
15 32
7 19
1 6
20 39
17 24
11 12
2 20
12 17
15 29
12 23
4 8
9 26
16 29
19 20
12 16
19 29
10 21
11 17
17 35
5 21
5 21
10 28
14 24
2 18
20 32
5 20
17 19
13 18
1 7
2 4
15 34
19 26
10 16
3 16
14 15
2 12
11 24
7 19
1 11
19 31
4 23
11 25
18 24
2 8
13 18
6 9
3...

output:

result:

ok 40217 numbers

Test #32:

score: 20

Accepted

time: 365ms

memory: 69552kb

input:

80000 80000
18 35
17 35
3 6
5 11
18 24
5 16
15 27
3 6
14 23
17 32
3 4
20 28
20 33
20 33
15 26
7 18
6 11
15 23
14 24
15 24
2 12
1 4
6 17
20 21
5 22
3 14
6 22
11 25
12 14
15 33
17 37
3 19
12 22
18 19
10 21
11 22
3 6
18 29
13 24
18 21
7 8
2 11
14 18
4 8
7 26
8 20
17 19
5 21
3 19
19 20
16 28
2 12
10 17
...

output:

result:

ok 40053 numbers

Test #33:

score: 20

Accepted

time: 1195ms

memory: 77580kb

input:

100000 100000
226837277 629340960
15356399 333988987
162106984 242750700
20082551 287851579
328071230 610388303
447593817 635405442
308736977 631719320
160200347 397247869
38277427 234064577
409441918 822798349
223535688 308685188
241171327 731560435
88999572 520819667
160876761 423873769
318618403 ...

output:

4896011847309
4193922187123
7267538159374
3009123033669
1150742787800
7376539231054
29986308174812
23514287962586
412292257966
431268376937
134374636779
4204584001628
6206145447825
2252898231053
4733304331
83360655662
3038841452167
1583402488870
7302689839462
13356634900697
8256846109573
48628772165...

result:

ok 50161 numbers

Subtask #7:

score: 30

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 #34:

score: 30

Accepted

time: 1094ms

memory: 76264kb

input:

100000 100000
229800237 722100077
43222268 521633530
194823742 296704281
34182355 312809937
77732257 273405549
102344836 351041358
395310846 551885672
432455924 824266021
377114525 517074442
241507899 704037560
462989507 476000772
226624645 392513169
84406407 301855054
403836860 780188676
451883792 ...

output:

572846633944
2889552313595
1246863931555
5030364036191
6743532540082
14439802479060
6812934247082
12082383982805
7274264760871
826327698429
5227199517735
509711027681
2908963089992
5025644378159
4996230167952
9857993025
9669151706423
95982662658
1519656247
2464410485616
16224520093277
4176190948
257...

result:

ok 50124 numbers

Test #35:

score: 30

Accepted

time: 1251ms

memory: 71932kb

input:

100000 100000
322903126 779528687
225929646 226849544
166982492 407140204
124023177 417756998
385758152 875610088
370143922 527551261
420494641 717158590
298294232 500025706
257468723 748040415
473979332 493843048
370708669 723572629
299702647 501193098
117383912 543482631
41886972 417906103
4531188...

output:

15882170866165
14418990597967
1485375698727
14493006946914
4261182164597
6136802352059
1190916982513
105803632338
4719099563475
299234101385
313468705501
796368729779
5624651440466
5163655923282
565647163118
61569871798
170115526705
5786632884514
139993180849
19433407147309
3337635033
3045305849926
...

result:

ok 50160 numbers

Test #36:

score: 30

Accepted

time: 835ms

memory: 80312kb

input:

100000 100000
8 27
5 18
11 22
20 40
3 17
4 17
7 25
4 9
1 3
4 22
3 21
2 8
3 11
11 31
13 32
17 34
10 30
12 28
3 21
7 20
8 24
4 23
9 23
4 13
14 33
11 25
3 22
2 19
4 21
6 24
7 24
11 23
1 18
5 24
5 17
9 26
1 17
6 17
12 27
11 29
4 15
15 35
8 20
1 18
4 8
9 28
5 19
7 23
1 13
8 25
2 16
12 32
5 25
9 26
5 23
1...

output:

result:

ok 50171 numbers

Test #37:

score: 30

Accepted

time: 1191ms

memory: 76476kb

input:

100000 100000
64801697 315632512
227872388 364810332
73187539 339809381
281608373 485275773
30170198 221808337
297409323 433956574
96597790 491239499
73205665 106408453
82450909 108224580
83703494 348384307
89632365 108834186
297524970 488061059
164251065 301275146
281309907 508188457
472271256 6078...

output:

6004891767080
315624773249
6919325461234
5756982057006
33962926881433
418718483950
6217632452838
8618956964
316293469803
20636283104952
10383925288709
27253323737
173628960746
3565551645977
2380123164617
878245225901
1395761159338
12230915005749
2141002682945
14399158968019
835320635999
130217234713...

result:

ok 50136 numbers

Test #38:

score: 30

Accepted

time: 1531ms

memory: 76728kb

input:

100000 100000
89504252 308122414
38107571 467517790
162131655 368900247
231602920 567418451
113524833 587438624
452599416 500886863
152177485 374383275
15560718 405461351
189461210 408685023
452824470 809374999
187265866 219172246
411472572 818555255
325093622 734296072
498950106 709769225
97384885 ...

output:

941175624259
4049841659456
173142362304
4071386059333
3717584414601
5456748417726
4889482629281
355236758567
5056595684187
8083564845
4664680587492
1526768872535
11725203977528
617191629055
1857267311697
202895082474
1402871671888
2150307444875
10662581432675
3470261974845
3107419758574
883761100063...

result:

ok 49870 numbers

Test #39:

score: 30

Accepted

time: 983ms

memory: 77084kb

input:

100000 100000
152241212 227669303
146067715 401950385
258705053 526116832
483074168 498470216
72171769 96706680
340680054 806796175
96561016 278756565
265124711 679463251
133673746 523176431
452068587 497939301
376773538 508029668
314094382 609529958
225003742 448223199
63618655 353251125
319482000 ...

output:

5765460862277
3525544759155
2098225240303
3298860826771
2918685762512
44455901203
178837470461
795319226558
6537024818811
1709592736733
8206945343
2642971689148
1651475564876
19431796776817
5447065821315
57227946028
9956821918304
6854518207600
3591166951174
4532220674092
15127357914954
3732358700618...

result:

ok 50006 numbers

Test #40:

score: 30

Accepted

time: 693ms

memory: 73660kb

input:

100000 100000
7 14
10 17
10 16
6 14
4 5
10 17
5 11
5 15
7 10
1 2
1 2
1 6
3 8
5 14
10 12
9 17
2 10
8 14
4 14
1 7
6 16
3 12
2 8
1 5
6 9
8 18
9 12
7 8
3 9
9 12
3 10
3 12
3 13
8 10
7 17
9 16
4 5
8 16
8 18
5 15
5 6
2 6
10 15
9 10
5 10
2 9
7 8
9 16
7 16
1 2
7 13
7 8
5 14
1 11
3 13
10 19
5 15
2 8
10 12
6 9...

output:

result:

ok 50242 numbers