oj.uz

Submission #18956

# Submission time Handle Problem Language Result Execution time Memory
18956 2016-02-16T17:56:44 Z ggoh Game (IOI13_game) C++
36 / 100
 3325 ms 132156 KB 
#include "game.h"
#include<algorithm>
#include<vector>
int a,b,X,t;
long long seg[4096][4096];
long long gcd2(long long xx,long long yy){
    if(yy==0)return xx;
    return gcd2(yy,xx%yy);
}

long long yans(int xnum,int num,int s,int e,int px,int qx,int py,int qy)
{
    if(s>qy||py>e)return (long long)0;
    if(py<=s&&e<=qy)return seg[xnum][num];
    return gcd2(yans(xnum,num*2,s,(s+e)/2,px,qx,py,qy),yans(xnum,num*2+1,(s+e)/2+1,e,px,qx,py,qy));
}
long long xans(int num,int s,int e,int px,int qx,int py,int qy)
{
    if(s>qx||px>e)return (long long)0;
    if(px<=s&&e<=qx)return yans(num,1,0,X-1,px,qx,py,qy);
    return gcd2(xans(num*2,s,(s+e)/2,px,qx,py,qy),xans(num*2+1,(s+e)/2+1,e,px,qx,py,qy));
}
void init(int R, int C)
{
    X=2048;
}
void update(int P, int Q, long long K)
{
    int u=X+P,o;
    o=X+Q;
    seg[u][o]=K;o/=2;
    while(o)
    {
        seg[u][o]=gcd2(seg[u][o*2],seg[u][o*2+1]);
        o/=2;
    }
    u/=2;
    while(u)
    {
        o=X+Q;
        while(o)
        {
            seg[u][o]=gcd2(seg[u*2][o],seg[u*2+1][o]);
            o/=2;
        }
        u/=2;
    }
}
long long calculate (int P, int Q, int U, int V)
{
    return xans(1,0,X-1,P,U,Q,V);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 132156 KB Output is correct
2 Correct 0 ms 132156 KB Output is correct
3 Correct 0 ms 132156 KB Output is correct
4 Incorrect 311 ms 132156 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 132156 KB Output is correct
2 Correct 0 ms 132156 KB Output is correct
3 Correct 0 ms 132156 KB Output is correct
4 Correct 0 ms 132156 KB Output is correct
5 Correct 0 ms 132156 KB Output is correct
6 Correct 0 ms 132156 KB Output is correct
7 Correct 0 ms 132156 KB Output is correct
8 Correct 0 ms 132156 KB Output is correct
9 Correct 0 ms 132156 KB Output is correct
10 Correct 0 ms 132156 KB Output is correct
11 Correct 0 ms 132156 KB Output is correct
12 Correct 1832 ms 132156 KB Output is correct
13 Correct 3001 ms 132156 KB Output is correct
14 Correct 1089 ms 132156 KB Output is correct
15 Correct 3325 ms 132156 KB Output is correct
16 Correct 558 ms 132156 KB Output is correct
17 Correct 1776 ms 132156 KB Output is correct
18 Correct 2136 ms 132156 KB Output is correct
19 Correct 2057 ms 132156 KB Output is correct
20 Correct 1961 ms 132156 KB Output is correct
21 Correct 0 ms 132156 KB Output is correct

Subtask #4
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 132156 KB Output is correct
2 Correct 0 ms 132156 KB Output is correct
3 Correct 0 ms 132156 KB Output is correct
4 Correct 0 ms 132156 KB Output is correct
5 Correct 0 ms 132156 KB Output is correct
6 Correct 0 ms 132156 KB Output is correct
7 Correct 0 ms 132156 KB Output is correct
8 Correct 0 ms 132156 KB Output is correct
9 Correct 0 ms 132156 KB Output is correct
10 Correct 0 ms 132156 KB Output is correct
11 Correct 0 ms 132156 KB Output is correct
12 Incorrect 318 ms 132156 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 132156 KB Output is correct
2 Correct 0 ms 132156 KB Output is correct
3 Correct 0 ms 132156 KB Output is correct
4 Correct 0 ms 132156 KB Output is correct
5 Correct 0 ms 132156 KB Output is correct
6 Correct 0 ms 132156 KB Output is correct
7 Correct 0 ms 132156 KB Output is correct
8 Correct 0 ms 132156 KB Output is correct
9 Correct 3 ms 132156 KB Output is correct
10 Correct 0 ms 132156 KB Output is correct
11 Correct 0 ms 132156 KB Output is correct
12 Incorrect 314 ms 132156 KB Output isn't correct
13 Halted 0 ms 0 KB -