oj.uz

Submission #956472

# Submission time Handle Problem Language Result Execution time Memory
956472 2024-04-02T03:48:41 Z abczz Game (IOI13_game) C++14
100 / 100
 2833 ms 63908 KB 
#include "game.h"
#include <iostream>
#include <vector>
#include <numeric>
#define ll long long
 
using namespace std;

ll A[22000], sz;
ll gcd(ll a, ll b) {
  if (!b) return a;
  else if (!a) return b;
  else return gcd(b%a, a);
}
struct SegTree{
  struct Node{
    ll val;
    int chl;
    int chr;
  };
  int cnt = 0;
  Node st[20000000];
  void get(int &id) {
    if (id != -1) return;
    st[cnt] = {0, -1, -1};
    id = cnt++;
  }
  void updateC(int &id, int idl, int idr, int l, int r, int y, ll w) {
    get(id);
    if (l == r) {
      if (idl == -1 && idr == -1) st[id].val = w;
      else st[id].val = gcd((idl != -1 ? st[idl].val : 0), (idr != -1 ? st[idr].val : 0));
      return;
    }
    int mid = (l+r)/2;
    if (st[id].chr == -1e9) {
      int ty = st[id].chl;
      ll tw = st[id].val;
      st[id] = {0, -1, -1};
      if (ty <= mid) {
        int tmp = st[id].chl, tmpchl = (idl != -1 ? st[idl].chl : -1), tmpchr = (idr != -1 ? st[idr].chl : -1);
        if (idl != -1 && st[idl].chr == -1e9) {
          if (st[idl].chl <= mid) tmpchl = idl;
          else tmpchl = -1;
        }
        if (idr != -1 && st[idr].chr == -1e9) {
          if (st[idr].chl <= mid) tmpchr = idr;
          else tmpchr = -1;
        }
        updateC(tmp, tmpchl, tmpchr, l, mid, ty, tw);
        st[id].chl = tmp;
      }
      else {
        int tmp = st[id].chr, tmpchl = (idl != -1 ? st[idl].chr : -1), tmpchr = (idr != -1 ? st[idr].chr : -1);
        if (idl != -1 && st[idl].chr == -1e9) {
          if (st[idl].chl > mid) tmpchl = idl;
          else tmpchl = -1;
        }
        if (idr != -1 && st[idr].chr == -1e9) {
          if (st[idr].chl > mid) tmpchr = idr;
          else tmpchr = -1;
        }
        updateC(tmp, tmpchl, tmpchr, mid+1, r, ty, tw);
        st[id].chr = tmp;
      }
    }
    else if (id + 1 == cnt) {
      st[id].val = w;
      st[id].chl = y;
      st[id].chr = -1e9;
      return;
    }
    if (y <= mid) {
      int tmp = st[id].chl, tmpchl = (idl != -1 ? st[idl].chl : -1), tmpchr = (idr != -1 ? st[idr].chl : -1);
      if (idl != -1 && st[idl].chr == -1e9) {
        if (st[idl].chl <= mid) tmpchl = idl;
        else tmpchl = -1;
      }
      if (idr != -1 && st[idr].chr == -1e9) {
        if (st[idr].chl <= mid) tmpchr = idr;
        else tmpchr = -1;
      }
      updateC(tmp, tmpchl, tmpchr, l, mid, y, w);
      st[id].chl = tmp;
    }
    else {
      int tmp = st[id].chr, tmpchl = (idl != -1 ? st[idl].chr : -1), tmpchr = (idr != -1 ? st[idr].chr : -1);
      if (idl != -1 && st[idl].chr == -1e9) {
        if (st[idl].chl > mid) tmpchl = idl;
        else tmpchl = -1;
      }
      if (idr != -1 && st[idr].chr == -1e9) {
        if (st[idr].chl > mid) tmpchr = idr;
        else tmpchr = -1;
      }
      updateC(tmp, tmpchl, tmpchr, mid+1, r, y, w);
      st[id].chr = tmp;
    }
    //cout << id << " " << st[id].chl << " " << st[id].chr << endl;
    st[id].val = gcd((st[id].chl != -1 ? st[st[id].chl].val : 0), (st[id].chr != -1 ? st[st[id].chr].val : 0));
  }
  void updateR(int &id, int l, int r, int x, int y, ll w) {
    get(id);
    if (id+1 == cnt) {
      int tmp = -1;
      get(tmp);
    }
    int tmp = id+1;
    if (l == r) {
      updateC(tmp, -1, -1, 0, (int)1e9-1, y, w);
      st[id].val = st[id+1].val;
      return;
    }
    int mid = (l+r)/2;
    if (x <= mid) {
      int tmp = st[id].chl;
      updateR(tmp, l, mid, x, y, w);
      st[id].chl = tmp;
    }
    else {
      int tmp = st[id].chr;
      updateR(tmp, mid+1, r, x, y, w);
      st[id].chr = tmp;
    }
    updateC(tmp, (st[id].chl != -1 ? st[id].chl+1 : -1), (st[id].chr != -1 ? st[id].chr+1 : -1), 0, (ll)1e9-1, y, w);
    st[id].val = gcd((st[id].chl != -1 ? st[st[id].chl].val : 0), (st[id].chr != -1 ? st[st[id].chr].val : 0));
  }
  ll queryC(int id, int l, int r, int ql, int qr) {
    if (id == -1 || qr < l || r < ql) return 0;
    else if (ql <= l && r <= qr) {
      return st[id].val;
    }
    if (st[id].chr == -1e9) {
      if (ql <= st[id].chl && st[id].chl <= qr) return st[id].val;
      else return 0;
    }
    int mid = (l+r)/2;
    return gcd(queryC(st[id].chl, l, mid, ql, qr), queryC(st[id].chr, mid+1, r, ql, qr));
  }
  ll queryR(int id, int l, int r, int ql, int qr, int qx, int qy) {
    if (id == -1 || qr < l || r < ql) return 0;
    else if (ql <= l && r <= qr) return queryC(id+1, 0, (int)1e9-1, qx, qy);
    int mid = (l+r)/2;
    return gcd(queryR(st[id].chl, l, mid, ql, qr, qx, qy), queryR(st[id].chr, mid+1, r, ql, qr, qx, qy));
  }
}ST;
 
void init(int R, int C) {
  int rt = -1;
  ST.get(rt);
}
 
void update(int P, int Q, long long K) {
  int rt = 0;
  ST.updateR(rt, 0, (int)1e9-1, P, Q, K);
}
 
long long calculate(int P, int Q, int U, int V) {
  int rt = 0;
  return ST.queryR(rt, 0, (int)1e9-1, P, U, Q, V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 0 ms 444 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 344 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 517 ms 20904 KB Output is correct
5 Correct 394 ms 20548 KB Output is correct
6 Correct 485 ms 17596 KB Output is correct
7 Correct 513 ms 17556 KB Output is correct
8 Correct 352 ms 11860 KB Output is correct
9 Correct 497 ms 17496 KB Output is correct
10 Correct 480 ms 17208 KB Output is correct
11 Correct 0 ms 344 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 448 KB Output is correct
12 Correct 814 ms 12240 KB Output is correct
13 Correct 1158 ms 8788 KB Output is correct
14 Correct 416 ms 4948 KB Output is correct
15 Correct 1332 ms 11240 KB Output is correct
16 Correct 391 ms 11140 KB Output is correct
17 Correct 698 ms 10028 KB Output is correct
18 Correct 1020 ms 12080 KB Output is correct
19 Correct 924 ms 12720 KB Output is correct
20 Correct 865 ms 11776 KB Output is correct
21 Correct 1 ms 348 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 481 ms 20560 KB Output is correct
13 Correct 390 ms 20488 KB Output is correct
14 Correct 498 ms 17724 KB Output is correct
15 Correct 521 ms 17756 KB Output is correct
16 Correct 352 ms 11860 KB Output is correct
17 Correct 493 ms 17668 KB Output is correct
18 Correct 493 ms 17060 KB Output is correct
19 Correct 782 ms 11860 KB Output is correct
20 Correct 1160 ms 8776 KB Output is correct
21 Correct 410 ms 4856 KB Output is correct
22 Correct 1329 ms 11344 KB Output is correct
23 Correct 385 ms 10832 KB Output is correct
24 Correct 698 ms 9620 KB Output is correct
25 Correct 1006 ms 11992 KB Output is correct
26 Correct 952 ms 12100 KB Output is correct
27 Correct 869 ms 11672 KB Output is correct
28 Correct 297 ms 25764 KB Output is correct
29 Correct 752 ms 26364 KB Output is correct
30 Correct 2281 ms 21096 KB Output is correct
31 Correct 2176 ms 33788 KB Output is correct
32 Correct 379 ms 10400 KB Output is correct
33 Correct 486 ms 10112 KB Output is correct
34 Correct 162 ms 21212 KB Output is correct
35 Correct 507 ms 17644 KB Output is correct
36 Correct 834 ms 24336 KB Output is correct
37 Correct 693 ms 24388 KB Output is correct
38 Correct 663 ms 24064 KB Output is correct
39 Correct 626 ms 20304 KB Output is correct
40 Correct 1 ms 348 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 478 ms 20876 KB Output is correct
13 Correct 391 ms 20560 KB Output is correct
14 Correct 483 ms 17632 KB Output is correct
15 Correct 520 ms 17352 KB Output is correct
16 Correct 354 ms 11856 KB Output is correct
17 Correct 508 ms 17888 KB Output is correct
18 Correct 470 ms 17084 KB Output is correct
19 Correct 812 ms 12116 KB Output is correct
20 Correct 1161 ms 9008 KB Output is correct
21 Correct 408 ms 4944 KB Output is correct
22 Correct 1327 ms 11536 KB Output is correct
23 Correct 381 ms 11092 KB Output is correct
24 Correct 698 ms 9812 KB Output is correct
25 Correct 1006 ms 12368 KB Output is correct
26 Correct 942 ms 12444 KB Output is correct
27 Correct 869 ms 11716 KB Output is correct
28 Correct 302 ms 26948 KB Output is correct
29 Correct 723 ms 27952 KB Output is correct
30 Correct 2287 ms 22120 KB Output is correct
31 Correct 2150 ms 34776 KB Output is correct
32 Correct 368 ms 11676 KB Output is correct
33 Correct 492 ms 11604 KB Output is correct
34 Correct 162 ms 22068 KB Output is correct
35 Correct 517 ms 18928 KB Output is correct
36 Correct 820 ms 25680 KB Output is correct
37 Correct 708 ms 25680 KB Output is correct
38 Correct 653 ms 25216 KB Output is correct
39 Correct 438 ms 46732 KB Output is correct
40 Correct 1016 ms 42488 KB Output is correct
41 Correct 2833 ms 39124 KB Output is correct
42 Correct 2799 ms 63908 KB Output is correct
43 Correct 232 ms 37456 KB Output is correct
44 Correct 486 ms 12620 KB Output is correct
45 Correct 625 ms 22368 KB Output is correct
46 Correct 1056 ms 41232 KB Output is correct
47 Correct 1070 ms 41508 KB Output is correct
48 Correct 1014 ms 41144 KB Output is correct
49 Correct 0 ms 348 KB Output is correct