oj.uz

Submission #38602

# Submission time Handle Problem Language Result Execution time Memory
38602 2018-01-05T02:47:25 Z funcsr Game (IOI13_game) C++14
36 / 100
 6923 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 = 2000;
//const int MAX_C = 100000;
const int MAX_R = 1000000000;
const int MAX_C = 1000000000;
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:39:13: warning: 'SegTree::val' will be initialized after [-Wreorder]
   long long val;
             ^
game.cpp:38:12: warning:   'SegTree* SegTree::lch' [-Wreorder]
   SegTree *lch, *rch;
            ^
game.cpp:40: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 2212 KB Output is correct
2 Correct 6 ms 4720 KB Output is correct
3 Correct 13 ms 4720 KB Output is correct
4 Correct 0 ms 2212 KB Output is correct
5 Correct 0 ms 2080 KB Output is correct
6 Correct 9 ms 4720 KB Output is correct
7 Correct 0 ms 2212 KB Output is correct
8 Correct 0 ms 2212 KB Output is correct
9 Correct 9 ms 4456 KB Output is correct
10 Correct 3 ms 3136 KB Output is correct
11 Correct 3 ms 3664 KB Output is correct
12 Correct 0 ms 2212 KB Output is correct

Subtask #2
0 / 27.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2212 KB Output is correct
2 Correct 6 ms 4720 KB Output is correct
3 Correct 6 ms 4720 KB Output is correct
4 Correct 0 ms 2212 KB Output is correct
5 Correct 0 ms 2080 KB Output is correct
6 Correct 6 ms 4720 KB Output is correct
7 Correct 0 ms 2212 KB Output is correct
8 Correct 0 ms 2212 KB Output is correct
9 Correct 0 ms 4456 KB Output is correct
10 Correct 3 ms 3136 KB Output is correct
11 Correct 3 ms 3664 KB Output is correct
12 Correct 3196 ms 157312 KB Output is correct
13 Correct 5579 ms 95140 KB Output is correct
14 Correct 1259 ms 4852 KB Output is correct
15 Correct 6163 ms 124840 KB Output is correct
16 Correct 1453 ms 201004 KB Output is correct
17 Correct 3779 ms 115336 KB Output is correct
18 Correct 6923 ms 201004 KB Output is correct
19 Correct 5943 ms 201004 KB Output is correct
20 Correct 5443 ms 200872 KB Output is correct
21 Correct 0 ms 2212 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2212 KB Output is correct
2 Correct 3 ms 4720 KB Output is correct
3 Correct 6 ms 4720 KB Output is correct
4 Correct 0 ms 2212 KB Output is correct
5 Correct 0 ms 2080 KB Output is correct
6 Correct 6 ms 4720 KB Output is correct
7 Correct 0 ms 2212 KB Output is correct
8 Correct 0 ms 2212 KB Output is correct
9 Correct 6 ms 4456 KB Output is correct
10 Correct 3 ms 3136 KB Output is correct
11 Correct 3 ms 3664 KB Output is correct
12 Memory limit exceeded 1683 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 2212 KB Output is correct
2 Correct 13 ms 4720 KB Output is correct
3 Correct 13 ms 4720 KB Output is correct
4 Correct 0 ms 2212 KB Output is correct
5 Correct 0 ms 2080 KB Output is correct
6 Correct 6 ms 4720 KB Output is correct
7 Correct 0 ms 2212 KB Output is correct
8 Correct 0 ms 2212 KB Output is correct
9 Correct 6 ms 4456 KB Output is correct
10 Correct 3 ms 3136 KB Output is correct
11 Correct 3 ms 3664 KB Output is correct
12 Memory limit exceeded 1606 ms 256000 KB Memory limit exceeded
13 Halted 0 ms 0 KB -