oj.uz

Submission #38596

# Submission time Handle Problem Language Result Execution time Memory
38596 2018-01-05T02:32:01 Z funcsr Game (IOI13_game) C++14
10 / 100
 5216 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_N2 = 1000000010;
const int MAX_N2 = 2010;
const long long MAX_N = MAX_N2*MAX_N2;
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:36:13: warning: 'SegTree::val' will be initialized after [-Wreorder]
   long long val;
             ^
game.cpp:35:12: warning:   'SegTree* SegTree::lch' [-Wreorder]
   SegTree *lch, *rch;
            ^
game.cpp:37: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 3 ms 3272 KB Output is correct
3 Correct 0 ms 3272 KB Output is correct
4 Correct 0 ms 2084 KB Output is correct
5 Correct 3 ms 2744 KB Output is correct
6 Correct 0 ms 2612 KB Output is correct
7 Correct 0 ms 2216 KB Output is correct
8 Correct 0 ms 2480 KB Output is correct
9 Correct 0 ms 2612 KB Output is correct
10 Correct 0 ms 2744 KB Output is correct
11 Correct 0 ms 2348 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 Runtime error 0 ms 2088 KB Execution killed because of forbidden syscall gettid (186)
5 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 3272 KB Output is correct
3 Correct 0 ms 3272 KB Output is correct
4 Correct 0 ms 2084 KB Output is correct
5 Correct 0 ms 2744 KB Output is correct
6 Correct 3 ms 2612 KB Output is correct
7 Correct 0 ms 2216 KB Output is correct
8 Correct 0 ms 2480 KB Output is correct
9 Correct 0 ms 2612 KB Output is correct
10 Correct 3 ms 2744 KB Output is correct
11 Correct 0 ms 2348 KB Output is correct
12 Correct 3893 ms 56732 KB Output is correct
13 Correct 4459 ms 29408 KB Output is correct
14 Correct 2486 ms 10268 KB Output is correct
15 Correct 5216 ms 34952 KB Output is correct
16 Correct 1196 ms 58316 KB Output is correct
17 Memory limit exceeded 916 ms 256000 KB Memory limit exceeded
18 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 3 ms 3272 KB Output is correct
3 Correct 0 ms 3272 KB Output is correct
4 Correct 0 ms 2084 KB Output is correct
5 Correct 0 ms 2744 KB Output is correct
6 Correct 0 ms 2612 KB Output is correct
7 Correct 0 ms 2216 KB Output is correct
8 Correct 0 ms 2480 KB Output is correct
9 Correct 0 ms 2612 KB Output is correct
10 Correct 0 ms 2744 KB Output is correct
11 Correct 0 ms 2348 KB Output is correct
12 Runtime error 0 ms 2088 KB Execution killed because of forbidden syscall gettid (186)
13 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 3272 KB Output is correct
3 Correct 3 ms 3272 KB Output is correct
4 Correct 0 ms 2084 KB Output is correct
5 Correct 0 ms 2744 KB Output is correct
6 Correct 3 ms 2612 KB Output is correct
7 Correct 0 ms 2216 KB Output is correct
8 Correct 0 ms 2480 KB Output is correct
9 Correct 0 ms 2612 KB Output is correct
10 Correct 0 ms 2744 KB Output is correct
11 Correct 0 ms 2348 KB Output is correct
12 Runtime error 0 ms 2088 KB Execution killed because of forbidden syscall gettid (186)
13 Halted 0 ms 0 KB -