oj.uz

Submission #38600

# Submission time Handle Problem Language Result Execution time Memory
38600 2018-01-05T02:43:39 Z funcsr Game (IOI13_game) C++14
36 / 100
 4646 ms 58308 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 = 2000;
//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
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 Incorrect 316 ms 3264 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.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 1546 ms 49332 KB Output is correct
13 Correct 3813 ms 28212 KB Output is correct
14 Correct 506 ms 2868 KB Output is correct
15 Correct 4646 ms 33756 KB Output is correct
16 Correct 1246 ms 58308 KB Output is correct
17 Correct 2029 ms 30984 KB Output is correct
18 Correct 3929 ms 58308 KB Output is correct
19 Correct 3246 ms 58308 KB Output is correct
20 Correct 3006 ms 58176 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 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 Incorrect 316 ms 3264 KB Output isn't correct
13 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 Incorrect 279 ms 3264 KB Output isn't correct
13 Halted 0 ms 0 KB -