oj.uz

Submission #68990

# Submission time Handle Problem Language Result Execution time Memory
68990 2018-08-19T12:18:21 Z MKopchev Game (IOI13_game) C++14
10 / 100
 13000 ms 132464 KB 
#include<bits/stdc++.h>
#include "game.h"
using namespace std;
vector<long long> tree;
long long my_gcd(long long a,long long b)
{
    if(a==0||b==0)return a+b;
    long long r=a%b;
    while(r)
    {
        a=b;
        b=r;
        r=a%b;
    }
    return b;
}
int r,c,SZ=0;
void init(int R, int C)
{
    r=R;
    c=C;
    int u=1;
    while(u<C)u=u*2;
    u=u*2+5;

    int v=1;
    while(v<R)v=v*2;
    v=v*2+5;

    int prod=u*v;
    for(int i=0;i<prod;i++)
        {
        tree.push_back(0);
        }
    SZ=tree.size();
}
void my_update(int node,int lx,int rx,int ly,int ry,int x,int y,long long val)
{
    assert(node<SZ);
    if(lx==rx&&ly==ry)
    {
        assert(lx==x&&ly==y);
        tree[node]=val;
        return;
    }
    if(rx-lx+1<=ry-ly+1)
    {
    int av=(ly+ry)/2;
    if(y<=av)my_update(node*2,lx,rx,ly,av,x,y,val);
    else my_update(node*2+1,lx,rx,av+1,ry,x,y,val);
    }
    else
    {
    int av=(lx+rx)/2;
    if(x<=av)my_update(node*2,lx,av,ly,ry,x,y,val);
    else my_update(node*2+1,av+1,rx,ly,ry,x,y,val);
    }
    tree[node]=my_gcd(tree[node*2],tree[node*2+1]);
}
void update(int P, int Q, long long K)
{
    my_update(1,0,r-1,0,c-1,P,Q,K);
}
int lq_x,rq_x,lq_y,rq_y;
long long my_query(int node,int lx,int rx,int ly,int ry)
{
    /*
    cout<<lx<<" "<<rx<<" "<<ly<<" "<<ry<<endl;
    cout<<"query: "<<lq_x<<" "<<rq_x<<" "<<lq_y<<" "<<rq_y<<endl;
    */
    assert(node<SZ);
    if(tree[node]==0)return 0;
    if(lq_x<=lx&&rx<=rq_x&&lq_y<=ly&&ry<=rq_y)return tree[node];
    if(max(lq_x,lx)>min(rq_x,rx)||max(lq_y,ly)>min(rq_y,ry))
    {
    return 0;
    }
    long long ans=0;
    if(rx-lx+1<=ry-ly+1)
    {
    int av=(ly+ry)/2;
    ans=my_gcd(ans,my_query(node*2,lx,rx,ly,av));
    ans=my_gcd(ans,my_query(node*2+1,lx,rx,av+1,ry));
    }
    else
    {
    int av=(lx+rx)/2;
    ans=my_gcd(ans,my_query(node*2,lx,av,ly,ry));
    ans=my_gcd(ans,my_query(node*2+1,av+1,rx,ly,ry));
    }
    return ans;
}
long long calculate(int P, int Q, int U, int V)
{
    lq_x=P;
    lq_y=Q;
    rq_x=U;
    rq_y=V;
    long long ans=my_query(1,0,r-1,0,c-1);
    /*
    for(int i=P;i<=U;i++)
        ans=my_gcd(ans,my_query(i,1,0,c-1,Q,V));
    */
    return ans;
}
/*
int main()
{
init(2,3);
update(0,0,20);
update(0,2,15);
update(1,1,12);
cout<<calculate(0,0,0,2)<<endl;//5
cout<<calculate(0,0,1,1)<<endl;//4
update(0,1,6);
update(1,1,14);
cout<<calculate(0,0,0,2)<<endl;//1
cout<<calculate(0,0,1,1)<<endl;//2
}
*/

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

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1784 KB Output is correct
2 Correct 3 ms 1784 KB Output is correct
3 Correct 2 ms 1784 KB Output is correct
4 Execution timed out 13092 ms 132216 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 20.0

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