oj.uz

Submission #38605

# Submission time Handle Problem Language Result Execution time Memory
38605 2018-01-05T03:01:09 Z funcsr Game (IOI13_game) C++14
36 / 100
 6479 ms 158420 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);
int V1 = 0;
//const int MAX_V1 = 4*1e7;
const int MAX_V1 = 1e7;
int lch[MAX_V1], rch[MAX_V1];
long long val[MAX_V1];
int alloc() {
  lch[V1] = -1, rch[V1] = -1;
  return V1++;
}
void seg1_update(long long x, long long v, int k=0, long long l=0, long long r=MAX_N) {
  if (r-l == 1) {
    val[k] = v;
    return;
  }
  if (x < (l+r)/2) {
    if (lch[k] == -1) lch[k] = alloc();
    seg1_update(x, v, lch[k], l, (l+r)/2);
  }
  else {
    if (rch[k] == -1) rch[k] = alloc();
    seg1_update(x, v, rch[k], (l+r)/2, r);
  }
  val[k] = gcd(lch[k]==-1?0:val[lch[k]], rch[k]==-1?0:val[rch[k]]);
}
long long seg1_query(long long a, long long b, int k=0, long long l=0, long long r=MAX_N) {
  if (b <= l || r <= a) return 0;
  if (a <= l && r <= b) return val[k];
  return gcd(lch[k]==-1?0:seg1_query(a, b, lch[k], l, (l+r)/2),
             rch[k]==-1?0:seg1_query(a, b, rch[k], (l+r)/2, r));
}

struct SegTree2 {
  SegTree2 *lch, *rch;
  int seg_k;
  SegTree2() : lch(NULL), rch(NULL) {
    seg_k = alloc();
  }
  void update(int x, int y, long long v, int l=0, int r=MAX_N2) {
    seg1_update(1LL*MAX_N2*y+x, v, seg_k);
    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 seg1_query(1LL*MAX_N2*ql, 1LL*MAX_N2*qr, seg_k);
    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;
      ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 158288 KB Output is correct
2 Correct 3 ms 158288 KB Output is correct
3 Correct 3 ms 158288 KB Output is correct
4 Correct 0 ms 158288 KB Output is correct
5 Correct 0 ms 158288 KB Output is correct
6 Correct 3 ms 158288 KB Output is correct
7 Correct 0 ms 158288 KB Output is correct
8 Correct 0 ms 158288 KB Output is correct
9 Correct 3 ms 158288 KB Output is correct
10 Correct 0 ms 158288 KB Output is correct
11 Correct 0 ms 158288 KB Output is correct
12 Correct 0 ms 158288 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 158288 KB Output is correct
2 Correct 0 ms 158288 KB Output is correct
3 Correct 0 ms 158288 KB Output is correct
4 Runtime error 1909 ms 158288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 158288 KB Output is correct
2 Correct 3 ms 158288 KB Output is correct
3 Correct 6 ms 158288 KB Output is correct
4 Correct 0 ms 158288 KB Output is correct
5 Correct 0 ms 158288 KB Output is correct
6 Correct 6 ms 158288 KB Output is correct
7 Correct 0 ms 158288 KB Output is correct
8 Correct 0 ms 158288 KB Output is correct
9 Correct 3 ms 158288 KB Output is correct
10 Correct 0 ms 158288 KB Output is correct
11 Correct 0 ms 158288 KB Output is correct
12 Correct 3226 ms 158420 KB Output is correct
13 Correct 5676 ms 158420 KB Output is correct
14 Correct 1069 ms 158288 KB Output is correct
15 Correct 6479 ms 158420 KB Output is correct
16 Correct 1239 ms 158420 KB Output is correct
17 Correct 3336 ms 158420 KB Output is correct
18 Correct 5743 ms 158420 KB Output is correct
19 Correct 5059 ms 158420 KB Output is correct
20 Correct 4536 ms 158420 KB Output is correct
21 Correct 0 ms 158288 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 158288 KB Output is correct
2 Correct 3 ms 158288 KB Output is correct
3 Correct 3 ms 158288 KB Output is correct
4 Correct 0 ms 158288 KB Output is correct
5 Correct 0 ms 158288 KB Output is correct
6 Correct 6 ms 158288 KB Output is correct
7 Correct 0 ms 158288 KB Output is correct
8 Correct 0 ms 158288 KB Output is correct
9 Correct 6 ms 158288 KB Output is correct
10 Correct 0 ms 158288 KB Output is correct
11 Correct 0 ms 158288 KB Output is correct
12 Runtime error 1596 ms 158288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 158288 KB Output is correct
2 Correct 3 ms 158288 KB Output is correct
3 Correct 3 ms 158288 KB Output is correct
4 Correct 0 ms 158288 KB Output is correct
5 Correct 0 ms 158288 KB Output is correct
6 Correct 3 ms 158288 KB Output is correct
7 Correct 0 ms 158288 KB Output is correct
8 Correct 0 ms 158288 KB Output is correct
9 Correct 3 ms 158288 KB Output is correct
10 Correct 0 ms 158288 KB Output is correct
11 Correct 0 ms 158288 KB Output is correct
12 Runtime error 1799 ms 158288 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Halted 0 ms 0 KB -