oj.uz

Submission #65065

# Submission time Handle Problem Language Result Execution time Memory
65065 2018-08-06T14:05:17 Z theknife2001 Game (IOI13_game) C++17
37 / 100
 13000 ms 132436 KB 
#include "game.h"
#include <bits/stdc++.h>
#define mid (l+r)/2


using namespace std;


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;
}

const int N=1e5+55;
long long tree[N*4][105];
int n,m;

void init(int R, int C)
{
    n=R;
    m=C;
}

void up(int l , int r , int node , int ind , long long val , int lev)
{
    if(l==r&&l==ind)
    {
        tree[node][lev]=val;
        return ;
    }
    if(ind<=mid)
        up(l,mid,node*2,ind,val,lev);
    else
        up(mid+1,r,node*2+1,ind,val,lev);
    tree[node][lev]=gcd2(tree[node*2][lev],tree[node*2+1][lev]);
}

long long query(int l , int r , int node , int x , int y , int lev)
{
    if(x<=l&&r<=y)
        return tree[node][lev];
    if(l>y||r<x)
        return 0;
    long long temp1=0;
    long long temp2=0;
    temp1=query(l,mid,node*2,x,y,lev);
    temp2=query(mid+1,r,node*2+1,x,y,lev);
    return gcd2(temp1,temp2);

}


void update(int P, int Q, long long K)
{
    up(0,m-1,1,Q,K,P);
}

long long calculate(int P, int Q, int U, int V)
{
    if(P>U)
        swap(P,U);
    if(Q>V)
        swap(Q,V);
    long long ans=0;
    for(int i=P;i<=U;i++)
    {
        ans=gcd2(ans,query(0,m-1,1,Q,V,i));
    }
    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 3 ms 288 KB Output is correct
2 Correct 3 ms 616 KB Output is correct
3 Correct 4 ms 616 KB Output is correct
4 Correct 3 ms 616 KB Output is correct
5 Correct 4 ms 616 KB Output is correct
6 Correct 3 ms 716 KB Output is correct
7 Correct 2 ms 716 KB Output is correct
8 Correct 3 ms 744 KB Output is correct
9 Correct 3 ms 744 KB Output is correct
10 Correct 3 ms 768 KB Output is correct
11 Correct 3 ms 768 KB Output is correct
12 Correct 3 ms 768 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 768 KB Output is correct
2 Correct 2 ms 768 KB Output is correct
3 Correct 3 ms 768 KB Output is correct
4 Correct 1766 ms 104200 KB Output is correct
5 Correct 1048 ms 104304 KB Output is correct
6 Correct 1387 ms 104304 KB Output is correct
7 Correct 1547 ms 104304 KB Output is correct
8 Correct 1202 ms 104304 KB Output is correct
9 Correct 1403 ms 104304 KB Output is correct
10 Correct 1229 ms 104304 KB Output is correct
11 Correct 2 ms 104304 KB Output is correct

Subtask #3
0 / 26.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 104304 KB Output is correct
2 Correct 4 ms 104304 KB Output is correct
3 Correct 4 ms 104304 KB Output is correct
4 Correct 3 ms 104304 KB Output is correct
5 Correct 5 ms 104304 KB Output is correct
6 Correct 3 ms 104304 KB Output is correct
7 Correct 2 ms 104304 KB Output is correct
8 Correct 3 ms 104304 KB Output is correct
9 Correct 3 ms 104304 KB Output is correct
10 Correct 3 ms 104304 KB Output is correct
11 Correct 3 ms 104304 KB Output is correct
12 Correct 1618 ms 105236 KB Output is correct
13 Correct 1090 ms 108712 KB Output is correct
14 Correct 1271 ms 110376 KB Output is correct
15 Correct 1379 ms 114772 KB Output is correct
16 Correct 982 ms 114772 KB Output is correct
17 Correct 1389 ms 123968 KB Output is correct
18 Correct 1256 ms 128216 KB Output is correct
19 Execution timed out 13044 ms 128216 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 128216 KB Output is correct
2 Correct 4 ms 128216 KB Output is correct
3 Correct 3 ms 128216 KB Output is correct
4 Correct 2 ms 128216 KB Output is correct
5 Correct 3 ms 128216 KB Output is correct
6 Correct 3 ms 128216 KB Output is correct
7 Correct 3 ms 128216 KB Output is correct
8 Correct 3 ms 128216 KB Output is correct
9 Correct 2 ms 128216 KB Output is correct
10 Correct 3 ms 128216 KB Output is correct
11 Correct 2 ms 128216 KB Output is correct
12 Correct 1754 ms 132376 KB Output is correct
13 Correct 1077 ms 132436 KB Output is correct
14 Correct 1505 ms 132436 KB Output is correct
15 Correct 1374 ms 132436 KB Output is correct
16 Correct 1141 ms 132436 KB Output is correct
17 Correct 1586 ms 132436 KB Output is correct
18 Correct 1264 ms 132436 KB Output is correct
19 Execution timed out 13087 ms 132436 KB Time limit exceeded
20 Halted 0 ms 0 KB -