oj.uz

Submission #38601

# Submission time Handle Problem Language Result Execution time Memory
38601 2018-01-05T02:45:32 Z funcsr Game (IOI13_game) C++14
63 / 100
 4799 ms 61212 KB 
#include "game.h"
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <set>
#include <cassert>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define pb push_back
#define _1 first
#define _2 second
#define INF 1145141919
#define MOD 1000000007

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;
}

const int MAX_R = 2000;
const int MAX_C = 100000;
//const int MAX_N2 = 1000000010;
const int MAX_N2 = MAX_R+1;
const long long MAX_N = 1LL*(MAX_R+1)*(MAX_C+1);
struct SegTree {
  SegTree *lch, *rch;
  long long val;
  SegTree() : val(0), lch(NULL), rch(NULL) {
  }
  void update(long long x, long long v, long long l=0, long long r=MAX_N) {
    if (r-l == 1) {
      val = v;
      return;
    }
    if (x < (l+r)/2) {
      if (lch == NULL) lch = new SegTree();
      lch->update(x, v, l, (l+r)/2);
    }
    else {
      if (rch == NULL) rch = new SegTree();
      rch->update(x, v, (l+r)/2, r);
    }
    val = gcd(lch?lch->val:0, rch?rch->val:0);
  }
  long long query(long long a, long long b, long long l=0, long long r=MAX_N) {
    if (b <= l || r <= a) return 0;
    if (a <= l && r <= b) return val;
    return gcd(lch?lch->query(a, b, l, (l+r)/2):0,
               rch?rch->query(a, b, (l+r)/2, r):0);
  }
};

struct SegTree2 {
  SegTree2 *lch, *rch;
  SegTree val;
  SegTree2() : lch(NULL), rch(NULL) {
  }
  void update(int x, int y, long long v, int l=0, int r=MAX_N2) {
    val.update(1LL*MAX_N2*y+x, v);
    if (r-l == 1) return;
    if (x < (l+r)/2) {
      if (lch == NULL) lch = new SegTree2();
      lch->update(x, y, v, l, (l+r)/2);
    }
    else {
      if (rch == NULL) rch = new SegTree2();
      rch->update(x, y, v, (l+r)/2, r);
    }
  }
  long long query(int a, int b, int ql, int qr, int l=0, int r=MAX_N2) {
    if (b <= l || r <= a) return 0;
    if (a <= l && r <= b) return val.query(1LL*MAX_N2*ql, 1LL*MAX_N2*qr);
    return gcd(lch?lch->query(a, b, ql, qr, l, (l+r)/2):0,
               rch?rch->query(a, b, ql, qr, (l+r)/2, r):0);
  }
};

SegTree2 root;

void init(int R, int C) {
}

void update(int P, int Q, long long K) {
  root.update(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
  return root.query(P, U+1, Q, V+1);
}

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;
      ^
game.cpp: In constructor 'SegTree::SegTree()':
game.cpp:38:13: warning: 'SegTree::val' will be initialized after [-Wreorder]
   long long val;
             ^
game.cpp:37:12: warning:   'SegTree* SegTree::lch' [-Wreorder]
   SegTree *lch, *rch;
            ^
game.cpp:39:3: warning:   when initialized here [-Wreorder]
   SegTree() : val(0), lch(NULL), rch(NULL) {
   ^

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2076 KB Output is correct
2 Correct 0 ms 2076 KB Output is correct
3 Correct 0 ms 2076 KB Output is correct
4 Correct 1089 ms 61212 KB Output is correct
5 Correct 683 ms 61212 KB Output is correct
6 Correct 1543 ms 61212 KB Output is correct
7 Correct 1523 ms 61212 KB Output is correct
8 Correct 856 ms 32568 KB Output is correct
9 Correct 1449 ms 61080 KB Output is correct
10 Correct 1416 ms 61212 KB Output is correct
11 Correct 0 ms 2076 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2076 KB Output is correct
2 Correct 3 ms 2604 KB Output is correct
3 Correct 0 ms 2604 KB Output is correct
4 Correct 0 ms 2076 KB Output is correct
5 Correct 0 ms 2076 KB Output is correct
6 Correct 0 ms 2604 KB Output is correct
7 Correct 0 ms 2076 KB Output is correct
8 Correct 0 ms 2076 KB Output is correct
9 Correct 0 ms 2604 KB Output is correct
10 Correct 0 ms 2340 KB Output is correct
11 Correct 0 ms 2340 KB Output is correct
12 Correct 1753 ms 49992 KB Output is correct
13 Correct 3643 ms 28740 KB Output is correct
14 Correct 563 ms 2868 KB Output is correct
15 Correct 4283 ms 34548 KB Output is correct
16 Correct 936 ms 59364 KB Output is correct
17 Correct 2446 ms 31908 KB Output is correct
18 Correct 4433 ms 59364 KB Output is correct
19 Correct 3636 ms 59364 KB Output is correct
20 Correct 3336 ms 59232 KB Output is correct
21 Correct 0 ms 2076 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2076 KB Output is correct
2 Correct 0 ms 2604 KB Output is correct
3 Correct 0 ms 2604 KB Output is correct
4 Correct 0 ms 2076 KB Output is correct
5 Correct 0 ms 2076 KB Output is correct
6 Correct 3 ms 2604 KB Output is correct
7 Correct 0 ms 2076 KB Output is correct
8 Correct 0 ms 2076 KB Output is correct
9 Correct 3 ms 2604 KB Output is correct
10 Correct 0 ms 2340 KB Output is correct
11 Correct 0 ms 2340 KB Output is correct
12 Correct 1109 ms 61212 KB Output is correct
13 Correct 749 ms 61212 KB Output is correct
14 Correct 1283 ms 61212 KB Output is correct
15 Correct 1419 ms 61212 KB Output is correct
16 Correct 889 ms 32568 KB Output is correct
17 Correct 1553 ms 61080 KB Output is correct
18 Correct 1149 ms 61212 KB Output is correct
19 Correct 1716 ms 49992 KB Output is correct
20 Correct 3709 ms 28740 KB Output is correct
21 Correct 583 ms 2868 KB Output is correct
22 Correct 4649 ms 34548 KB Output is correct
23 Correct 803 ms 59364 KB Output is correct
24 Correct 2243 ms 31908 KB Output is correct
25 Correct 3999 ms 59364 KB Output is correct
26 Correct 3566 ms 59364 KB Output is correct
27 Correct 3116 ms 59232 KB Output is correct
28 Incorrect 376 ms 2076 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2076 KB Output is correct
2 Correct 0 ms 2604 KB Output is correct
3 Correct 0 ms 2604 KB Output is correct
4 Correct 0 ms 2076 KB Output is correct
5 Correct 0 ms 2076 KB Output is correct
6 Correct 0 ms 2604 KB Output is correct
7 Correct 0 ms 2076 KB Output is correct
8 Correct 0 ms 2076 KB Output is correct
9 Correct 0 ms 2604 KB Output is correct
10 Correct 0 ms 2340 KB Output is correct
11 Correct 0 ms 2340 KB Output is correct
12 Correct 1119 ms 61212 KB Output is correct
13 Correct 739 ms 61212 KB Output is correct
14 Correct 1503 ms 61212 KB Output is correct
15 Correct 1619 ms 61212 KB Output is correct
16 Correct 1012 ms 32568 KB Output is correct
17 Correct 1393 ms 61080 KB Output is correct
18 Correct 1316 ms 61212 KB Output is correct
19 Correct 1796 ms 49992 KB Output is correct
20 Correct 3886 ms 28740 KB Output is correct
21 Correct 576 ms 2868 KB Output is correct
22 Correct 4799 ms 34548 KB Output is correct
23 Correct 853 ms 59364 KB Output is correct
24 Correct 2339 ms 31908 KB Output is correct
25 Correct 4306 ms 59364 KB Output is correct
26 Correct 3526 ms 59364 KB Output is correct
27 Correct 3369 ms 59232 KB Output is correct
28 Incorrect 386 ms 2076 KB Output isn't correct
29 Halted 0 ms 0 KB -