oj.uz

Submission #956452

# Submission time Handle Problem Language Result Execution time Memory
956452 2024-04-02T01:00:46 Z abczz Game (IOI13_game) C++14
80 / 100
 2472 ms 256000 KB 
#include "game.h"
#include <iostream>
#include <vector>
#include <numeric>
#define ll long long
 
using namespace std;
 
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 (y <= mid) {
      int tmp = st[id].chl;
      updateC(tmp, (idl != -1 ? st[idl].chl : -1), (idr != -1 ? st[idr].chl : -1), l, mid, y, w);
      st[id].chl = tmp;
    }
    else {
      int tmp = st[id].chr;
      updateC(tmp, (idl != -1 ? st[idl].chr : -1), (idr != -1 ? st[idr].chr : -1), mid+1, r, y, w);
      st[id].chr = tmp;
    }
    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;
    }
    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 348 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 444 KB Output is correct
6 Correct 2 ms 2652 KB Output is correct
7 Correct 0 ms 448 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 440 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 499 ms 33464 KB Output is correct
5 Correct 405 ms 33376 KB Output is correct
6 Correct 543 ms 30996 KB Output is correct
7 Correct 528 ms 30544 KB Output is correct
8 Correct 392 ms 20892 KB Output is correct
9 Correct 546 ms 30864 KB Output is correct
10 Correct 494 ms 30344 KB Output is correct
11 Correct 0 ms 348 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 2652 KB Output is correct
3 Correct 3 ms 2652 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 2652 KB Output is correct
7 Correct 0 ms 440 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 796 ms 16972 KB Output is correct
13 Correct 1109 ms 9344 KB Output is correct
14 Correct 453 ms 5824 KB Output is correct
15 Correct 1252 ms 11776 KB Output is correct
16 Correct 383 ms 17744 KB Output is correct
17 Correct 719 ms 14908 KB Output is correct
18 Correct 1087 ms 19220 KB Output is correct
19 Correct 940 ms 19240 KB Output is correct
20 Correct 873 ms 19148 KB Output is correct
21 Correct 1 ms 344 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 2 ms 2492 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 440 KB Output is correct
6 Correct 2 ms 2652 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 388 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 500 ms 33636 KB Output is correct
13 Correct 406 ms 33308 KB Output is correct
14 Correct 490 ms 30744 KB Output is correct
15 Correct 541 ms 30548 KB Output is correct
16 Correct 359 ms 20820 KB Output is correct
17 Correct 514 ms 30580 KB Output is correct
18 Correct 492 ms 30460 KB Output is correct
19 Correct 808 ms 17204 KB Output is correct
20 Correct 1098 ms 9532 KB Output is correct
21 Correct 440 ms 5600 KB Output is correct
22 Correct 1301 ms 11736 KB Output is correct
23 Correct 399 ms 17688 KB Output is correct
24 Correct 727 ms 15060 KB Output is correct
25 Correct 1034 ms 19084 KB Output is correct
26 Correct 966 ms 19480 KB Output is correct
27 Correct 922 ms 18804 KB Output is correct
28 Correct 415 ms 136784 KB Output is correct
29 Correct 936 ms 151536 KB Output is correct
30 Correct 2472 ms 109072 KB Output is correct
31 Correct 2349 ms 86228 KB Output is correct
32 Correct 350 ms 12496 KB Output is correct
33 Correct 474 ms 12224 KB Output is correct
34 Correct 263 ms 145124 KB Output is correct
35 Correct 715 ms 81612 KB Output is correct
36 Correct 1262 ms 149360 KB Output is correct
37 Correct 1044 ms 149640 KB Output is correct
38 Correct 1066 ms 149284 KB Output is correct
39 Correct 923 ms 117072 KB Output is correct
40 Correct 0 ms 348 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 2652 KB Output is correct
3 Correct 2 ms 2652 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 2652 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 506 ms 33616 KB Output is correct
13 Correct 396 ms 33360 KB Output is correct
14 Correct 537 ms 30764 KB Output is correct
15 Correct 541 ms 30676 KB Output is correct
16 Correct 392 ms 20816 KB Output is correct
17 Correct 507 ms 30724 KB Output is correct
18 Correct 493 ms 30472 KB Output is correct
19 Correct 823 ms 16928 KB Output is correct
20 Correct 1113 ms 9300 KB Output is correct
21 Correct 391 ms 5980 KB Output is correct
22 Correct 1303 ms 12008 KB Output is correct
23 Correct 372 ms 17740 KB Output is correct
24 Correct 725 ms 14848 KB Output is correct
25 Correct 1016 ms 19068 KB Output is correct
26 Correct 968 ms 19428 KB Output is correct
27 Correct 885 ms 18768 KB Output is correct
28 Correct 405 ms 136876 KB Output is correct
29 Correct 949 ms 151752 KB Output is correct
30 Correct 2455 ms 109260 KB Output is correct
31 Correct 2332 ms 85064 KB Output is correct
32 Correct 354 ms 12656 KB Output is correct
33 Correct 453 ms 12300 KB Output is correct
34 Correct 273 ms 145176 KB Output is correct
35 Correct 640 ms 81336 KB Output is correct
36 Correct 1319 ms 149572 KB Output is correct
37 Correct 1043 ms 149588 KB Output is correct
38 Correct 1010 ms 149072 KB Output is correct
39 Runtime error 646 ms 256000 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -