oj.uz

Submission #38606

# Submission time Handle Problem Language Result Execution time Memory
38606 2018-01-05T03:24:43 Z funcsr Game (IOI13_game) C++14
36 / 100
 6733 ms 174680 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];

inline int alloc() {
  lch[V1] = -1, rch[V1] = -1;
  assert(V1 < MAX_V1);
  return V1++;
}
void seg1_update(long long x, long long v, int k, 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, 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));
}

int V2 = 0;
const int MAX_V2 = 1400000;
int lch2[MAX_V2], rch2[MAX_V2];
int seg_k2[MAX_V2];
inline int alloc2() {
  lch2[V2] = -1, rch2[V2] = -1;
  seg_k2[V2] = alloc();
  assert(V2 < MAX_V2);
  return V2++;
}
void seg2_update(int x, int y, long long v, int k, int l=0, int r=MAX_N2) {
  seg1_update(1LL*MAX_N2*y+x, v, seg_k2[k]);
  if (r-l == 1) return;
  if (x < (l+r)/2) {
    if (lch2[k] == -1) lch2[k] = alloc2();
    seg2_update(x, y, v, lch2[k], l, (l+r)/2);
  }
  else {
    if (rch2[k] == -1) rch2[k] = alloc2();
    seg2_update(x, y, v, rch2[k], (l+r)/2, r);
  }
}
long long seg2_query(int a, int b, int ql, int qr, int k, 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_k2[k]);
  return gcd(lch2[k]==-1?0:seg2_query(a, b, ql, qr, lch2[k], l, (l+r)/2),
             rch2[k]==-1?0:seg2_query(a, b, ql, qr, rch2[k], (l+r)/2, r));
}

int root;

void init(int R, int C) {
  root = alloc2();
}

void update(int P, int Q, long long K) {
  seg2_update(P, Q, K, root);
}

long long calculate(int P, int Q, int U, int V) {
  return seg2_query(P, U+1, Q, V+1, root);
}

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 174676 KB Output is correct
2 Correct 0 ms 174676 KB Output is correct
3 Correct 3 ms 174676 KB Output is correct
4 Correct 0 ms 174676 KB Output is correct
5 Correct 0 ms 174676 KB Output is correct
6 Correct 3 ms 174676 KB Output is correct
7 Correct 0 ms 174676 KB Output is correct
8 Correct 0 ms 174676 KB Output is correct
9 Correct 3 ms 174676 KB Output is correct
10 Correct 0 ms 174676 KB Output is correct
11 Correct 0 ms 174676 KB Output is correct
12 Correct 0 ms 174676 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 174676 KB Output is correct
2 Correct 0 ms 174676 KB Output is correct
3 Correct 0 ms 174676 KB Output is correct
4 Runtime error 1863 ms 174680 KB Execution killed because of forbidden syscall gettid (186)
5 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 174676 KB Output is correct
2 Correct 6 ms 174676 KB Output is correct
3 Correct 6 ms 174676 KB Output is correct
4 Correct 0 ms 174676 KB Output is correct
5 Correct 0 ms 174676 KB Output is correct
6 Correct 3 ms 174676 KB Output is correct
7 Correct 0 ms 174676 KB Output is correct
8 Correct 0 ms 174676 KB Output is correct
9 Correct 3 ms 174676 KB Output is correct
10 Correct 0 ms 174676 KB Output is correct
11 Correct 0 ms 174676 KB Output is correct
12 Correct 3053 ms 174676 KB Output is correct
13 Correct 5599 ms 174676 KB Output is correct
14 Correct 1179 ms 174676 KB Output is correct
15 Correct 6733 ms 174676 KB Output is correct
16 Correct 1253 ms 174676 KB Output is correct
17 Correct 3329 ms 174676 KB Output is correct
18 Correct 6409 ms 174676 KB Output is correct
19 Correct 5193 ms 174676 KB Output is correct
20 Correct 4326 ms 174676 KB Output is correct
21 Correct 0 ms 174676 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 174676 KB Output is correct
2 Correct 3 ms 174676 KB Output is correct
3 Correct 3 ms 174676 KB Output is correct
4 Correct 0 ms 174676 KB Output is correct
5 Correct 0 ms 174676 KB Output is correct
6 Correct 3 ms 174676 KB Output is correct
7 Correct 0 ms 174676 KB Output is correct
8 Correct 0 ms 174676 KB Output is correct
9 Correct 3 ms 174676 KB Output is correct
10 Correct 0 ms 174676 KB Output is correct
11 Correct 0 ms 174676 KB Output is correct
12 Runtime error 1936 ms 174680 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 174676 KB Output is correct
2 Correct 3 ms 174676 KB Output is correct
3 Correct 3 ms 174676 KB Output is correct
4 Correct 0 ms 174676 KB Output is correct
5 Correct 0 ms 174676 KB Output is correct
6 Correct 6 ms 174676 KB Output is correct
7 Correct 0 ms 174676 KB Output is correct
8 Correct 0 ms 174676 KB Output is correct
9 Correct 3 ms 174676 KB Output is correct
10 Correct 3 ms 174676 KB Output is correct
11 Correct 3 ms 174676 KB Output is correct
12 Runtime error 1819 ms 174680 KB Execution killed because of forbidden syscall gettid (186)
13 Halted 0 ms 0 KB -