Submission #514829

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
514829	2022-01-18 14:32:58	ritul_kr_singh	Game (IOI13_game)	C++17	100 / 100	3585 ms	233088 KiB

game

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
#define ll long long
#define m ((l + r) / 2)
 
const int N = 6e5, M = 1.3e7, B = 25;
 
ll gcd2(ll X, ll Y) {
  while(X != Y && Y) swap(X %= Y, Y);
  return X;
}
 
int limRow, limCol, sL, sR; ll sV;
 
ll sGcd[M], xGcd[N*B];
int G[M], H[M], sCnt, xCnt, xP[N*B], xRow[N*B];
 
void sUpd(int l, int r, int u) {
  if(r - l < 2) return void(sGcd[u] = sV);
 
  sL<m? sUpd(l, m, G[u] ? : G[u] = ++sCnt):
      sUpd(m, r, H[u] ? : H[u] = ++sCnt);
  sGcd[u] = gcd2(G[u] ? sGcd[G[u]] : 0LL, H[u] ? sGcd[H[u]] : 0LL);
}
 
ll sQry(int l, int r, int u) {
  if(sL<=l && r<=sR) return sGcd[u];
  if(sR<=l || r<=sL) return 0LL;
  return gcd2((G[u] ? sQry(l, m, G[u]) : 0LL),
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20