oj.uz

Submission #529003

# Submission time Handle Problem Language Result Execution time Memory
529003 2022-02-21T21:35:38 Z AdamGS Game (IOI13_game) C++17
100 / 100
 9495 ms 203296 KB 
#include "game.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int base=10;
struct NodeC {
  ll val=0;
  NodeC *children[base]={};
};
struct NodeR {
  NodeC *root=nullptr;
  NodeR *children[base]={};
};
int N, M;
NodeR *root;
void updC(NodeC *v, int l, int r, int a, ll x) {
  if(l==r) {
    v->val=x;
    return;
  }
  int p=(r-l)/base+1, akt=l;
  v->val=0;
  for(int i=0; akt<=r; ++i) {
    if(akt<=a && a<=min(akt+p-1, r)) {
      if(v->children[i]==nullptr) v->children[i]=new NodeC();
      updC(v->children[i], akt, min(akt+p-1, r), a, x);
    }
    akt+=p;
    if(v->children[i]!=nullptr) v->val=gcd(v->val, (v->children[i])->val);
  }
}
ll cntC(NodeC *v, int l, int r, int a, int b) {
  if(v==nullptr || b<l || a>r) return 0;
  if(a<=l && r<=b) return v->val;
  ll ans=0;
  int p=(r-l)/base+1, akt=l;
  for(int i=0; akt<=r; ++i) {
    if(v->children[i]!=nullptr) {
      ans=gcd(ans, cntC(v->children[i], akt, min(akt+p-1, r), a, b));
    }
    akt+=p;
  }
  return ans;
}
void updR(NodeR *v, int l, int r, int a, int b, ll x) {
  if(v->root==nullptr) v->root=new NodeC();
  if(l!=r) {
    int p=(r-l)/base+1, akt=l;
    for(int i=0; akt<=r; ++i) {
      if(akt<=a && a<=min(akt+p-1, r)) {
        if(v->children[i]==nullptr) v->children[i]=new NodeR();
        updR(v->children[i], akt, min(akt+p-1, r), a, b, x);
      }
      akt+=p;
    }
    akt=l;
    ll y=0;
    for(int i=0; akt<=r; ++i) {
      if(v->children[i]!=nullptr) {
        y=gcd(y, cntC((v->children[i])->root, 0, M-1, b, b));
      }
      akt+=p;
    }
    x=y;
  }
  updC(v->root, 0, M-1, b, x);
}
ll cntR(NodeR *v, int l, int r, int ar, int br, int ac, int bc) {
  if(br<l || ar>r) return 0;
  if(ar<=l && r<=br) {
    if(v->root!=nullptr) return cntC(v->root, 0, M-1, ac, bc);
    return 0;
  }
  ll ans=0;
  int p=(r-l)/base+1, akt=l;
  for(int i=0; akt<=r; ++i) {
    if(v->children[i]!=nullptr) {
      ans=gcd(ans, cntR(v->children[i], akt, min(akt+p-1, r), ar, br, ac, bc));
    }
    akt+=p;
  }
  return ans;
}
void init(int R, int C) {
  N=R;
  M=C;
  root=new NodeR();
}
void update(int a, int b, ll x) {
  updR(root, 0, N-1, a, b, x);
}
ll calculate(int ar, int ac, int br, int bc) {
  return cntR(root, 0, N-1, ar, br, ac, bc);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 909 ms 12732 KB Output is correct
5 Correct 550 ms 12508 KB Output is correct
6 Correct 771 ms 10116 KB Output is correct
7 Correct 883 ms 9764 KB Output is correct
8 Correct 514 ms 8360 KB Output is correct
9 Correct 813 ms 9824 KB Output is correct
10 Correct 765 ms 9456 KB Output is correct
11 Correct 0 ms 204 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 292 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 292 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 2222 ms 13400 KB Output is correct
13 Correct 3591 ms 7464 KB Output is correct
14 Correct 267 ms 5544 KB Output is correct
15 Correct 3848 ms 11780 KB Output is correct
16 Correct 197 ms 16908 KB Output is correct
17 Correct 1206 ms 12828 KB Output is correct
18 Correct 2222 ms 18252 KB Output is correct
19 Correct 1815 ms 18460 KB Output is correct
20 Correct 1799 ms 17876 KB Output is correct
21 Correct 1 ms 204 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 0 ms 292 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 0 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 887 ms 12780 KB Output is correct
13 Correct 543 ms 12556 KB Output is correct
14 Correct 691 ms 10164 KB Output is correct
15 Correct 788 ms 9852 KB Output is correct
16 Correct 486 ms 8604 KB Output is correct
17 Correct 755 ms 9924 KB Output is correct
18 Correct 680 ms 9668 KB Output is correct
19 Correct 1862 ms 13452 KB Output is correct
20 Correct 3228 ms 7408 KB Output is correct
21 Correct 275 ms 5576 KB Output is correct
22 Correct 3674 ms 11668 KB Output is correct
23 Correct 202 ms 16868 KB Output is correct
24 Correct 1181 ms 12808 KB Output is correct
25 Correct 2079 ms 18588 KB Output is correct
26 Correct 1774 ms 18392 KB Output is correct
27 Correct 1748 ms 17860 KB Output is correct
28 Correct 595 ms 93352 KB Output is correct
29 Correct 2191 ms 102252 KB Output is correct
30 Correct 6626 ms 72580 KB Output is correct
31 Correct 5851 ms 57184 KB Output is correct
32 Correct 397 ms 10132 KB Output is correct
33 Correct 613 ms 11076 KB Output is correct
34 Correct 314 ms 95936 KB Output is correct
35 Correct 1473 ms 55944 KB Output is correct
36 Correct 2813 ms 100208 KB Output is correct
37 Correct 2252 ms 100432 KB Output is correct
38 Correct 2290 ms 99856 KB Output is correct
39 Correct 1903 ms 79500 KB Output is correct
40 Correct 1 ms 204 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 284 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 288 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 886 ms 12832 KB Output is correct
13 Correct 540 ms 12548 KB Output is correct
14 Correct 702 ms 10012 KB Output is correct
15 Correct 797 ms 10008 KB Output is correct
16 Correct 484 ms 8300 KB Output is correct
17 Correct 758 ms 9924 KB Output is correct
18 Correct 676 ms 9472 KB Output is correct
19 Correct 1791 ms 13504 KB Output is correct
20 Correct 3233 ms 7604 KB Output is correct
21 Correct 254 ms 5636 KB Output is correct
22 Correct 3709 ms 11620 KB Output is correct
23 Correct 196 ms 16860 KB Output is correct
24 Correct 1179 ms 12888 KB Output is correct
25 Correct 2093 ms 18256 KB Output is correct
26 Correct 1738 ms 18548 KB Output is correct
27 Correct 1727 ms 17872 KB Output is correct
28 Correct 599 ms 93220 KB Output is correct
29 Correct 2198 ms 102320 KB Output is correct
30 Correct 6714 ms 72484 KB Output is correct
31 Correct 5841 ms 57236 KB Output is correct
32 Correct 406 ms 10176 KB Output is correct
33 Correct 617 ms 11080 KB Output is correct
34 Correct 317 ms 96060 KB Output is correct
35 Correct 1470 ms 55756 KB Output is correct
36 Correct 2808 ms 100448 KB Output is correct
37 Correct 2243 ms 100276 KB Output is correct
38 Correct 2275 ms 99752 KB Output is correct
39 Correct 818 ms 184372 KB Output is correct
40 Correct 3478 ms 203296 KB Output is correct
41 Correct 9495 ms 143300 KB Output is correct
42 Correct 8363 ms 110872 KB Output is correct
43 Correct 614 ms 197972 KB Output is correct
44 Correct 514 ms 10532 KB Output is correct
45 Correct 1924 ms 79656 KB Output is correct
46 Correct 3637 ms 202284 KB Output is correct
47 Correct 3726 ms 202200 KB Output is correct
48 Correct 3594 ms 201720 KB Output is correct
49 Correct 0 ms 204 KB Output is correct