oj.uz

Submission #38598

# Submission time Handle Problem Language Result Execution time Memory
38598 2018-01-05T02:34:39 Z funcsr Game (IOI13_game) C++14
10 / 100
 3426 ms 256000 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 = 100;
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) {
      assert(l == x);
      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;
    if (lch == NULL) lch = new SegTree();
    if (rch == NULL) rch = new SegTree();
    return gcd(lch->query(a, b, l, (l+r)/2),
               rch->query(a, b, (l+r)/2, r));
  }
};

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);
    if (lch == NULL) lch = new SegTree2();
    if (rch == NULL) rch = new SegTree2();
    return gcd(lch->query(a, b, ql, qr, l, (l+r)/2),
               rch->query(a, b, ql, qr, (l+r)/2, r));
  }
};

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 2084 KB Output is correct
2 Correct 0 ms 2876 KB Output is correct
3 Correct 0 ms 2876 KB Output is correct
4 Correct 0 ms 2084 KB Output is correct
5 Correct 0 ms 2612 KB Output is correct
6 Correct 0 ms 2480 KB Output is correct
7 Correct 0 ms 2216 KB Output is correct
8 Correct 0 ms 2348 KB Output is correct
9 Correct 0 ms 2480 KB Output is correct
10 Correct 0 ms 2612 KB Output is correct
11 Correct 0 ms 2216 KB Output is correct
12 Correct 0 ms 2084 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2084 KB Output is correct
2 Correct 0 ms 2084 KB Output is correct
3 Correct 0 ms 2216 KB Output is correct
4 Correct 3396 ms 84452 KB Output is correct
5 Correct 933 ms 31652 KB Output is correct
6 Memory limit exceeded 2109 ms 256000 KB Memory limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2084 KB Output is correct
2 Correct 0 ms 2876 KB Output is correct
3 Correct 3 ms 2876 KB Output is correct
4 Correct 0 ms 2084 KB Output is correct
5 Correct 0 ms 2612 KB Output is correct
6 Correct 0 ms 2480 KB Output is correct
7 Correct 0 ms 2216 KB Output is correct
8 Correct 0 ms 2348 KB Output is correct
9 Correct 0 ms 2480 KB Output is correct
10 Correct 0 ms 2612 KB Output is correct
11 Correct 0 ms 2216 KB Output is correct
12 Incorrect 1169 ms 17000 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2084 KB Output is correct
2 Correct 0 ms 2876 KB Output is correct
3 Correct 3 ms 2876 KB Output is correct
4 Correct 0 ms 2084 KB Output is correct
5 Correct 0 ms 2612 KB Output is correct
6 Correct 0 ms 2480 KB Output is correct
7 Correct 0 ms 2216 KB Output is correct
8 Correct 0 ms 2348 KB Output is correct
9 Correct 0 ms 2480 KB Output is correct
10 Correct 0 ms 2612 KB Output is correct
11 Correct 0 ms 2216 KB Output is correct
12 Correct 3116 ms 84452 KB Output is correct
13 Correct 836 ms 31652 KB Output is correct
14 Memory limit exceeded 2186 ms 256000 KB Memory limit exceeded
15 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2084 KB Output is correct
2 Correct 3 ms 2876 KB Output is correct
3 Correct 3 ms 2876 KB Output is correct
4 Correct 0 ms 2084 KB Output is correct
5 Correct 0 ms 2612 KB Output is correct
6 Correct 0 ms 2480 KB Output is correct
7 Correct 0 ms 2216 KB Output is correct
8 Correct 0 ms 2348 KB Output is correct
9 Correct 0 ms 2480 KB Output is correct
10 Correct 0 ms 2612 KB Output is correct
11 Correct 0 ms 2216 KB Output is correct
12 Correct 3426 ms 84452 KB Output is correct
13 Correct 829 ms 31652 KB Output is correct
14 Memory limit exceeded 2096 ms 256000 KB Memory limit exceeded
15 Halted 0 ms 0 KB -