oj.uz

Submission #62839

# Submission time Handle Problem Language Result Execution time Memory
62839 2018-07-30T12:57:13 Z mhnd Game (IOI13_game) C++14
37 / 100
 13000 ms 116700 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int N = 1e5+50;
const ll oo = 1e18;
const ll mod = 1e9+7;

ll seg[2010][4*2010],seg2[11][4*N];
int c,type;

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

ll l,r,val,cur;
void update1(int n,int s,int e){
    if(s > r || e < l)return;
    if(s == e){
        if(type)seg[cur][n] = val;
        else seg2[cur][n] = val;
        return;
    }
    update1(n*2,s,(s+e)/2);
    update1(n*2+1,(s+e)/2+1,e);
    if(type)seg[cur][n] = gcd2(seg[cur][n*2],seg[cur][n*2+1]);
    else seg2[cur][n] = gcd2(seg2[cur][n*2],seg2[cur][n*2+1]);
}

ll get(int n,int s,int e){
    if(s > r || e < l)return 0;
    if(s >= l && e <= r){
        if(type)return seg[cur][n];
        else return seg2[cur][n];
    }
    return gcd2(get(n*2,s,(s+e)/2),get(n*2+1,(s+e)/2+1,e));
}

void init(int R, int C) {
    type = (R>10);
    c=C;
}

void update(int P, int Q, long long K) {
    Q++;
    l = r = Q;
    val = K;
    cur = P;
    update1(1,1,c);
}

long long calculate(int P, int Q, int U, int V) {
    l = Q+1;
    r = V+1;
    ll ans = 0;
    for(int i=P;i<=U;i++){
        cur = i;
        ans = gcd2(ans,get(1,1,c));
    }
    return ans;
}

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 2 ms 376 KB Output is correct
2 Correct 3 ms 856 KB Output is correct
3 Correct 3 ms 888 KB Output is correct
4 Correct 3 ms 888 KB Output is correct
5 Correct 4 ms 888 KB Output is correct
6 Correct 4 ms 896 KB Output is correct
7 Correct 3 ms 896 KB Output is correct
8 Correct 3 ms 896 KB Output is correct
9 Correct 3 ms 904 KB Output is correct
10 Correct 4 ms 904 KB Output is correct
11 Correct 4 ms 904 KB Output is correct
12 Correct 3 ms 904 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 904 KB Output is correct
2 Correct 2 ms 904 KB Output is correct
3 Correct 3 ms 904 KB Output is correct
4 Correct 1898 ms 25420 KB Output is correct
5 Correct 887 ms 29568 KB Output is correct
6 Correct 1590 ms 34844 KB Output is correct
7 Correct 1558 ms 39208 KB Output is correct
8 Correct 1137 ms 42140 KB Output is correct
9 Correct 1754 ms 48176 KB Output is correct
10 Correct 1282 ms 52184 KB Output is correct
11 Correct 2 ms 52184 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 52184 KB Output is correct
2 Correct 4 ms 52184 KB Output is correct
3 Correct 4 ms 52184 KB Output is correct
4 Correct 2 ms 52184 KB Output is correct
5 Correct 3 ms 52184 KB Output is correct
6 Correct 3 ms 52184 KB Output is correct
7 Correct 3 ms 52184 KB Output is correct
8 Correct 3 ms 52184 KB Output is correct
9 Correct 4 ms 52184 KB Output is correct
10 Correct 3 ms 52184 KB Output is correct
11 Correct 3 ms 52184 KB Output is correct
12 Execution timed out 13019 ms 52184 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 52184 KB Output is correct
2 Correct 3 ms 52184 KB Output is correct
3 Correct 4 ms 52184 KB Output is correct
4 Correct 2 ms 52184 KB Output is correct
5 Correct 4 ms 52184 KB Output is correct
6 Correct 3 ms 52184 KB Output is correct
7 Correct 3 ms 52184 KB Output is correct
8 Correct 3 ms 52184 KB Output is correct
9 Correct 3 ms 52184 KB Output is correct
10 Correct 3 ms 52184 KB Output is correct
11 Correct 3 ms 52184 KB Output is correct
12 Correct 1749 ms 57380 KB Output is correct
13 Correct 819 ms 61716 KB Output is correct
14 Correct 1560 ms 66952 KB Output is correct
15 Correct 1819 ms 71380 KB Output is correct
16 Correct 1390 ms 74216 KB Output is correct
17 Correct 1521 ms 80228 KB Output is correct
18 Correct 1420 ms 84352 KB Output is correct
19 Execution timed out 13096 ms 84352 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 84352 KB Output is correct
2 Correct 3 ms 84352 KB Output is correct
3 Correct 4 ms 84352 KB Output is correct
4 Correct 3 ms 84352 KB Output is correct
5 Correct 5 ms 84352 KB Output is correct
6 Correct 4 ms 84352 KB Output is correct
7 Correct 2 ms 84352 KB Output is correct
8 Correct 3 ms 84352 KB Output is correct
9 Correct 4 ms 84352 KB Output is correct
10 Correct 3 ms 84352 KB Output is correct
11 Correct 3 ms 84352 KB Output is correct
12 Correct 1812 ms 89736 KB Output is correct
13 Correct 922 ms 93936 KB Output is correct
14 Correct 1480 ms 99108 KB Output is correct
15 Correct 1470 ms 103584 KB Output is correct
16 Correct 1124 ms 106396 KB Output is correct
17 Correct 1554 ms 112524 KB Output is correct
18 Correct 1241 ms 116700 KB Output is correct
19 Execution timed out 13014 ms 116700 KB Time limit exceeded
20 Halted 0 ms 0 KB -