oj.uz

Submission #38608

# Submission time Handle Problem Language Result Execution time Memory
38608 2018-01-05T03:32:42 Z funcsr Game (IOI13_game) C++14
63 / 100
 6356 ms 221556 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 = 13000000;
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*(r-l)*y+(x-l), 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*(r-l)*ql, 1LL*(r-l)*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 221552 KB Output is correct
2 Correct 3 ms 221552 KB Output is correct
3 Correct 6 ms 221552 KB Output is correct
4 Correct 0 ms 221552 KB Output is correct
5 Correct 0 ms 221552 KB Output is correct
6 Correct 0 ms 221552 KB Output is correct
7 Correct 0 ms 221552 KB Output is correct
8 Correct 0 ms 221552 KB Output is correct
9 Correct 3 ms 221552 KB Output is correct
10 Correct 0 ms 221552 KB Output is correct
11 Correct 0 ms 221552 KB Output is correct
12 Correct 0 ms 221552 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 221552 KB Output is correct
2 Correct 0 ms 221552 KB Output is correct
3 Correct 0 ms 221552 KB Output is correct
4 Correct 1989 ms 221552 KB Output is correct
5 Correct 1359 ms 221552 KB Output is correct
6 Correct 2319 ms 221552 KB Output is correct
7 Correct 2639 ms 221552 KB Output is correct
8 Correct 1579 ms 221552 KB Output is correct
9 Correct 2389 ms 221552 KB Output is correct
10 Correct 2353 ms 221552 KB Output is correct
11 Correct 0 ms 221552 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 221552 KB Output is correct
2 Correct 3 ms 221552 KB Output is correct
3 Correct 3 ms 221552 KB Output is correct
4 Correct 0 ms 221552 KB Output is correct
5 Correct 0 ms 221552 KB Output is correct
6 Correct 3 ms 221552 KB Output is correct
7 Correct 0 ms 221552 KB Output is correct
8 Correct 0 ms 221552 KB Output is correct
9 Correct 0 ms 221552 KB Output is correct
10 Correct 0 ms 221552 KB Output is correct
11 Correct 0 ms 221552 KB Output is correct
12 Correct 3123 ms 221552 KB Output is correct
13 Correct 5293 ms 221552 KB Output is correct
14 Correct 1243 ms 221552 KB Output is correct
15 Correct 5899 ms 221552 KB Output is correct
16 Correct 1419 ms 221552 KB Output is correct
17 Correct 3236 ms 221552 KB Output is correct
18 Correct 6109 ms 221552 KB Output is correct
19 Correct 5119 ms 221552 KB Output is correct
20 Correct 4686 ms 221552 KB Output is correct
21 Correct 0 ms 221552 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 221552 KB Output is correct
2 Correct 3 ms 221552 KB Output is correct
3 Correct 3 ms 221552 KB Output is correct
4 Correct 0 ms 221552 KB Output is correct
5 Correct 0 ms 221552 KB Output is correct
6 Correct 3 ms 221552 KB Output is correct
7 Correct 0 ms 221552 KB Output is correct
8 Correct 0 ms 221552 KB Output is correct
9 Correct 3 ms 221552 KB Output is correct
10 Correct 0 ms 221552 KB Output is correct
11 Correct 0 ms 221552 KB Output is correct
12 Correct 2039 ms 221552 KB Output is correct
13 Correct 1449 ms 221552 KB Output is correct
14 Correct 2626 ms 221552 KB Output is correct
15 Correct 3073 ms 221552 KB Output is correct
16 Correct 1549 ms 221552 KB Output is correct
17 Correct 2799 ms 221552 KB Output is correct
18 Correct 2599 ms 221552 KB Output is correct
19 Correct 3123 ms 221552 KB Output is correct
20 Correct 5533 ms 221552 KB Output is correct
21 Correct 1306 ms 221552 KB Output is correct
22 Correct 6159 ms 221552 KB Output is correct
23 Correct 1426 ms 221552 KB Output is correct
24 Correct 3523 ms 221552 KB Output is correct
25 Correct 5973 ms 221552 KB Output is correct
26 Correct 5006 ms 221552 KB Output is correct
27 Correct 4646 ms 221552 KB Output is correct
28 Runtime error 1239 ms 221556 KB Execution killed because of forbidden syscall gettid (186)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 221552 KB Output is correct
2 Correct 3 ms 221552 KB Output is correct
3 Correct 3 ms 221552 KB Output is correct
4 Correct 0 ms 221552 KB Output is correct
5 Correct 0 ms 221552 KB Output is correct
6 Correct 0 ms 221552 KB Output is correct
7 Correct 0 ms 221552 KB Output is correct
8 Correct 0 ms 221552 KB Output is correct
9 Correct 3 ms 221552 KB Output is correct
10 Correct 0 ms 221552 KB Output is correct
11 Correct 0 ms 221552 KB Output is correct
12 Correct 2093 ms 221552 KB Output is correct
13 Correct 1539 ms 221552 KB Output is correct
14 Correct 2466 ms 221552 KB Output is correct
15 Correct 2729 ms 221552 KB Output is correct
16 Correct 1549 ms 221552 KB Output is correct
17 Correct 2749 ms 221552 KB Output is correct
18 Correct 2386 ms 221552 KB Output is correct
19 Correct 3099 ms 221552 KB Output is correct
20 Correct 5136 ms 221552 KB Output is correct
21 Correct 1126 ms 221552 KB Output is correct
22 Correct 6356 ms 221552 KB Output is correct
23 Correct 1343 ms 221552 KB Output is correct
24 Correct 3349 ms 221552 KB Output is correct
25 Correct 5583 ms 221552 KB Output is correct
26 Correct 5459 ms 221552 KB Output is correct
27 Correct 4746 ms 221552 KB Output is correct
28 Runtime error 1296 ms 221556 KB Execution killed because of forbidden syscall gettid (186)
29 Halted 0 ms 0 KB -