oj.uz

Submission #38595

# Submission time Handle Problem Language Result Execution time Memory
38595 2018-01-05T02:28:25 Z funcsr Game (IOI13_game) C++14
10 / 100
 4889 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 long long MAX_N = 1LL<<60; // log(1e9^2)
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));
  }
};

const int MAX_N2 = 1<<30; // log(1e9)
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:34:13: warning: 'SegTree::val' will be initialized after [-Wreorder]
   long long val;
             ^
game.cpp:33:12: warning:   'SegTree* SegTree::lch' [-Wreorder]
   SegTree *lch, *rch;
            ^
game.cpp:35: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 2220 KB Output is correct
2 Correct 13 ms 4992 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 0 ms 2220 KB Output is correct
5 Correct 0 ms 2484 KB Output is correct
6 Correct 6 ms 4728 KB Output is correct
7 Correct 0 ms 2352 KB Output is correct
8 Correct 0 ms 2484 KB Output is correct
9 Correct 6 ms 4596 KB Output is correct
10 Correct 3 ms 3276 KB Output is correct
11 Correct 3 ms 3672 KB Output is correct
12 Correct 0 ms 2220 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2220 KB Output is correct
2 Correct 0 ms 2220 KB Output is correct
3 Correct 0 ms 2352 KB Output is correct
4 Memory limit exceeded 1863 ms 256000 KB Memory limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2220 KB Output is correct
2 Correct 3 ms 4992 KB Output is correct
3 Correct 9 ms 4992 KB Output is correct
4 Correct 0 ms 2220 KB Output is correct
5 Correct 0 ms 2484 KB Output is correct
6 Correct 0 ms 4728 KB Output is correct
7 Correct 0 ms 2352 KB Output is correct
8 Correct 0 ms 2484 KB Output is correct
9 Correct 6 ms 4596 KB Output is correct
10 Correct 3 ms 3276 KB Output is correct
11 Correct 3 ms 3672 KB Output is correct
12 Correct 2819 ms 155076 KB Output is correct
13 Correct 3926 ms 93168 KB Output is correct
14 Correct 1839 ms 6180 KB Output is correct
15 Correct 4889 ms 122736 KB Output is correct
16 Correct 1463 ms 198108 KB Output is correct
17 Memory limit exceeded 4623 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 2220 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 0 ms 2220 KB Output is correct
5 Correct 0 ms 2484 KB Output is correct
6 Correct 6 ms 4728 KB Output is correct
7 Correct 0 ms 2352 KB Output is correct
8 Correct 0 ms 2484 KB Output is correct
9 Correct 6 ms 4596 KB Output is correct
10 Correct 3 ms 3276 KB Output is correct
11 Correct 3 ms 3672 KB Output is correct
12 Memory limit exceeded 1859 ms 256000 KB Memory limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2220 KB Output is correct
2 Correct 6 ms 4992 KB Output is correct
3 Correct 6 ms 4992 KB Output is correct
4 Correct 0 ms 2220 KB Output is correct
5 Correct 0 ms 2484 KB Output is correct
6 Correct 6 ms 4728 KB Output is correct
7 Correct 0 ms 2352 KB Output is correct
8 Correct 0 ms 2484 KB Output is correct
9 Correct 3 ms 4596 KB Output is correct
10 Correct 3 ms 3276 KB Output is correct
11 Correct 3 ms 3672 KB Output is correct
12 Memory limit exceeded 2083 ms 256000 KB Memory limit exceeded
13 Halted 0 ms 0 KB -