oj.uz

Submission #30152

# Submission time Handle Problem Language Result Execution time Memory
30152 2017-07-22T13:43:52 Z sampriti Game (IOI13_game) C++14
80 / 100
 10143 ms 256000 KB 
#include "game.h"
#include <cstdio>
#include <algorithm>

using namespace std;

int cnt = 0;
int cnt2 = 0;

long long gcd(long long X, long long Y) {
  long long tmp;
  while (X != Y && Y != 0) {
    tmp = X;
    X = Y;
    Y = tmp % Y;
  }
  return X;
}

inline long long gcd(long long X, long long Y, long long Z) {
  return gcd(X, gcd(Y, Z));
}

struct node2 {
  node2 *left, *mid, *right;
  long long val;

  node2(long long _val = 0, node2 *_left = NULL, node2 *_mid = NULL, node2 *_right = NULL) {
    cnt2++;
    val = _val;
    left = _left;
    mid = _mid;
    right = _right;
  }
};

struct node {
  node *left, *mid, *right;
  node2 *val;

  node(node2 *_val = NULL, node *_left = NULL, node *_mid = NULL, node *_right = NULL) {
    cnt++;
    val = _val;
    left = _left;
    mid = _mid;
    right = _right;
  }
};

int R, C;
node* root;

void update2(node2 *& root, int L, int R, int Q, long long K) {
  if(root == NULL) root = new node2();

  if(L == R) {
    root->val = K;
    return;
  }

  int mid1 = L + (R - L + 1)/3;
  int mid2 = R - (R - L + 1)/3;
  if(Q <= mid1) {
    update2(root->left, L, mid1, Q, K);
  }
  else if(Q <= mid2) {
    update2(root->mid, mid1 + 1, mid2, Q, K);
  }
  else {
    update2(root->right, mid2 + 1, R, Q, K);
  }
  root->val = gcd(root->left == NULL ? 0 : root->left->val,
                  root->mid == NULL ? 0 : root->mid->val,
                  root->right == NULL ? 0 : root->right->val);
}

void merge(node2*& root, node2* left, node2* mid, node2* right, int L, int R, int Q) {
  if(root == NULL) root = new node2();

  long long left_val = (left == NULL ? 0 : left->val);
  long long mid_val = (mid == NULL ? 0 : mid->val);
  long long right_val = (right == NULL ? 0 : right->val);

  root->val = gcd(left_val, mid_val, right_val);

  if(L == R) return;

  int mid1 = L + (R - L + 1)/3;
  int mid2 = R - (R - L + 1)/3;
  if (Q <= mid1) {
    merge(root->left,
        (left == NULL ? NULL : left->left),
        (mid == NULL ? NULL : mid->left),
        (right == NULL ? NULL : right->left),
        L, mid1, Q);
  }
  else if(Q <= mid2) {
    merge(root->mid,
        (left == NULL ? NULL : left->mid),
        (mid == NULL ? NULL : mid->mid),
        (right == NULL ? NULL : right->mid),
        mid1 + 1, mid2, Q);
  }
  else {
    merge(root->right,
        (left == NULL ? NULL : left->right),
        (mid == NULL ? NULL : mid->right),
        (right == NULL ? NULL : right->right),
        mid2 + 1, R, Q);
  }
}

void update(node *& root, int L, int R, int P, int Q, long long K) {
  if(root == NULL) root = new node();

  if(L == R) {
    update2(root->val, 0, C - 1, Q, K);
    return;
  }

  int mid1 = L + (R - L + 1)/3;
  int mid2 = R - (R - L + 1)/3;
  if(P <= mid1) {
    update(root->left, L, mid1, P, Q, K);
  }
  else if (P <= mid2) {
    update(root->mid, mid1 + 1, mid2, P, Q, K);
  }
  else {
    update(root->right, mid2 + 1, R, P, Q, K);
  }
  merge(root->val,
      (root->left == NULL ? NULL : root->left->val),
      (root->mid == NULL ? NULL : root->mid->val),
      (root->right == NULL ? NULL : root->right->val),
      0, C - 1, Q);
}

long long query2(node2* root, int L, int R, int C_L, int C_R) {
  if(root == NULL) return 0;
  if(L > R) return 0;
  if(C_L > R || C_R < L) return 0;

  if(C_L <= L && R <= C_R) return root->val;

  int mid1 = L + (R - L + 1)/3;
  int mid2 = R - (R - L + 1)/3;

  long long left = query2(root->left, L, mid1, C_L, C_R);
  long long mid = query2(root->mid, mid1 + 1, mid2, C_L, C_R);
  long long right = query2(root->right, mid2 + 1, R, C_L, C_R);
  return gcd(left, mid, right);
}

long long query(node* root, int L, int R, int R_L, int R_R, int C_L, int C_R) {
  if(root == NULL) return 0;
  if(R_L > R || R_R < L) return 0;

  if(R_L <= L && R <= R_R) return query2(root->val, 0, C - 1, C_L, C_R);

  int mid1 = L + (R - L + 1)/3;
  int mid2 = R - (R - L + 1)/3;

  long long left = query(root->left, L, mid1, R_L, R_R, C_L, C_R);
  long long mid = query(root->mid, mid1 + 1, mid2, R_L, R_R, C_L, C_R);
  long long right = query(root->right, mid2 + 1, R, R_L, R_R, C_L, C_R);
  return gcd(left, mid, right);
}

void init(int _R, int _C) {
  R = _R, C = _C;
  root = NULL;
}

void update(int P, int Q, long long K) {
  update(root, 0, R - 1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
  return query(root, 0, R - 1, P, U, Q, V);
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1176 KB Output is correct
2 Correct 0 ms 1176 KB Output is correct
3 Correct 0 ms 1176 KB Output is correct
4 Correct 969 ms 8700 KB Output is correct
5 Correct 583 ms 8700 KB Output is correct
6 Correct 923 ms 8700 KB Output is correct
7 Correct 1276 ms 8700 KB Output is correct
8 Correct 736 ms 5400 KB Output is correct
9 Correct 1129 ms 8832 KB Output is correct
10 Correct 1076 ms 8700 KB Output is correct
11 Correct 0 ms 1176 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1176 KB Output is correct
2 Correct 0 ms 1308 KB Output is correct
3 Correct 0 ms 1308 KB Output is correct
4 Correct 0 ms 1176 KB Output is correct
5 Correct 0 ms 1176 KB Output is correct
6 Correct 0 ms 1308 KB Output is correct
7 Correct 0 ms 1176 KB Output is correct
8 Correct 0 ms 1176 KB Output is correct
9 Correct 0 ms 1308 KB Output is correct
10 Correct 0 ms 1176 KB Output is correct
11 Correct 0 ms 1176 KB Output is correct
12 Correct 1486 ms 10416 KB Output is correct
13 Correct 3559 ms 5532 KB Output is correct
14 Correct 509 ms 1308 KB Output is correct
15 Correct 4019 ms 8040 KB Output is correct
16 Correct 199 ms 15564 KB Output is correct
17 Correct 1543 ms 9360 KB Output is correct
18 Correct 2943 ms 15564 KB Output is correct
19 Correct 2603 ms 15564 KB Output is correct
20 Correct 2063 ms 15564 KB Output is correct
21 Correct 0 ms 1176 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1176 KB Output is correct
2 Correct 0 ms 1308 KB Output is correct
3 Correct 0 ms 1308 KB Output is correct
4 Correct 0 ms 1176 KB Output is correct
5 Correct 0 ms 1176 KB Output is correct
6 Correct 0 ms 1308 KB Output is correct
7 Correct 0 ms 1176 KB Output is correct
8 Correct 0 ms 1176 KB Output is correct
9 Correct 0 ms 1308 KB Output is correct
10 Correct 0 ms 1176 KB Output is correct
11 Correct 0 ms 1176 KB Output is correct
12 Correct 1056 ms 8700 KB Output is correct
13 Correct 469 ms 8700 KB Output is correct
14 Correct 863 ms 8700 KB Output is correct
15 Correct 976 ms 8700 KB Output is correct
16 Correct 639 ms 5400 KB Output is correct
17 Correct 1056 ms 8832 KB Output is correct
18 Correct 796 ms 8700 KB Output is correct
19 Correct 1536 ms 10416 KB Output is correct
20 Correct 3493 ms 5532 KB Output is correct
21 Correct 503 ms 1308 KB Output is correct
22 Correct 4123 ms 8040 KB Output is correct
23 Correct 249 ms 15564 KB Output is correct
24 Correct 1956 ms 9360 KB Output is correct
25 Correct 3383 ms 15564 KB Output is correct
26 Correct 2799 ms 15564 KB Output is correct
27 Correct 2596 ms 15564 KB Output is correct
28 Correct 1423 ms 168288 KB Output is correct
29 Correct 3246 ms 182808 KB Output is correct
30 Correct 10143 ms 136476 KB Output is correct
31 Correct 8703 ms 104004 KB Output is correct
32 Correct 879 ms 1440 KB Output is correct
33 Correct 1018 ms 3288 KB Output is correct
34 Correct 466 ms 182676 KB Output is correct
35 Correct 2626 ms 92520 KB Output is correct
36 Correct 4062 ms 182808 KB Output is correct
37 Correct 4279 ms 182808 KB Output is correct
38 Correct 4449 ms 182808 KB Output is correct
39 Correct 3683 ms 140172 KB Output is correct
40 Correct 0 ms 1176 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1176 KB Output is correct
2 Correct 0 ms 1308 KB Output is correct
3 Correct 0 ms 1308 KB Output is correct
4 Correct 0 ms 1176 KB Output is correct
5 Correct 0 ms 1176 KB Output is correct
6 Correct 0 ms 1308 KB Output is correct
7 Correct 0 ms 1176 KB Output is correct
8 Correct 0 ms 1176 KB Output is correct
9 Correct 0 ms 1308 KB Output is correct
10 Correct 0 ms 1176 KB Output is correct
11 Correct 0 ms 1176 KB Output is correct
12 Correct 976 ms 8700 KB Output is correct
13 Correct 589 ms 8700 KB Output is correct
14 Correct 923 ms 8700 KB Output is correct
15 Correct 1169 ms 8700 KB Output is correct
16 Correct 713 ms 5400 KB Output is correct
17 Correct 1186 ms 8832 KB Output is correct
18 Correct 1018 ms 8700 KB Output is correct
19 Correct 1463 ms 10416 KB Output is correct
20 Correct 3536 ms 5532 KB Output is correct
21 Correct 549 ms 1308 KB Output is correct
22 Correct 4206 ms 8040 KB Output is correct
23 Correct 259 ms 15564 KB Output is correct
24 Correct 2019 ms 9360 KB Output is correct
25 Correct 3423 ms 15564 KB Output is correct
26 Correct 2906 ms 15564 KB Output is correct
27 Correct 2359 ms 15564 KB Output is correct
28 Correct 1189 ms 168288 KB Output is correct
29 Correct 2486 ms 182808 KB Output is correct
30 Correct 9633 ms 136476 KB Output is correct
31 Correct 9026 ms 104004 KB Output is correct
32 Correct 769 ms 1440 KB Output is correct
33 Correct 1249 ms 3288 KB Output is correct
34 Correct 479 ms 182676 KB Output is correct
35 Correct 2503 ms 92520 KB Output is correct
36 Correct 5199 ms 182808 KB Output is correct
37 Correct 3626 ms 182808 KB Output is correct
38 Correct 4176 ms 182808 KB Output is correct
39 Memory limit exceeded 889 ms 256000 KB Memory limit exceeded
40 Halted 0 ms 0 KB -