oj.uz

답안 #69060

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
69060 2018-08-19T16:50:26 Z MKopchev 게임 (IOI13_game) C++14
0 / 100
 14 ms 8556 KB 
#include<bits/stdc++.h>
#include "game.h"
using namespace std;
vector< 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;
void init(int R, int C)
{
    r=R;
    c=C;
    int u=1;
    while(u<R)u=u*2;
    //u=u*2+5;
    u=1000;

    int v=1;
    while(v<C)v=v*2;
    //v=v*2+5;
    v=1000;

    vector<long long> help={};
    for(int j=0;j<v;j++)help.push_back(0);
    for(int i=0;i<u;i++)
        {
        tree.push_back(help);
        }

}
void upd(int ind,int node,int l,int r,int pos,long long val,bool down)
{
    if(l==r)
    {
        assert(l==pos);
        if(down)tree[ind][node]=val;
        else tree[ind][node]=__gcd(tree[ind][node],val);
        //cout<<ind<<" "<<node<<" -> "<<val<<endl;
        return;
    }
    int av=(l+r)/2;
    if(pos<=av)upd(ind,node*2,l,av,pos,val,down);
    else upd(ind,node*2+1,av+1,r,pos,val,down);
    tree[ind][node]=my_gcd(tree[ind][node*2],tree[ind][node*2+1]);
}
void my_update(int node,int lx,int rx,int x,int y,long long val)
{
    upd(node,1,0,c-1,y,val,lx==rx);
    if(lx==rx)
    {
        assert(lx==x);
        return;
    }
    int av=(lx+rx)/2;
    if(x<=av)my_update(node*2,lx,av,x,y,val);
    else my_update(node*2+1,av+1,rx,x,y,val);
}
void update(int P, int Q, long long K)
{
    my_update(1,0,r-1,P,Q,K);
}
long long que(int ind,int node,int l,int r,int lq,int rq)
{
    //cout<<ind<<" "<<node<<" "<<l<<" "<<r<<" "<<lq<<" "<<rq<<endl;
    if(l==lq&&r==rq)return tree[ind][node];
    int av=(l+r)/2;
    long long ans=0;
    if(lq<=av)ans=my_gcd(ans,que(ind,node*2,l,av,lq,min(av,rq)));
    if(av<rq)ans=my_gcd(ans,que(ind,node*2+1,av+1,r,max(av+1,lq),rq));
    return ans;
}
int lq_x,rq_x,lq_y,rq_y;
long long my_query(int node,int l,int r,int lq,int rq)
{
    //cout<<node<<" "<<l<<" "<<r<<" "<<lq<<" "<<rq<<endl;
    /*
    cout<<lx<<" "<<rx<<" "<<ly<<" "<<ry<<endl;
    cout<<"query: "<<lq_x<<" "<<rq_x<<" "<<lq_y<<" "<<rq_y<<endl;
    */
    if(l==lq&&r==rq)return que(node,1,0,c-1,lq_y,rq_y);
    int av=(l+r)/2;
    long long ans=0;
    if(lq<=av)ans=my_gcd(ans,my_query(node*2,l,av,lq,min(av,rq)));
    if(av<rq)ans=my_gcd(ans,my_query(node*2+1,av+1,r,max(av+1,lq),rq));
    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,lq_x,rq_x);
    /*
    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,2);
update(0,0,30);
update(0,1,42);
update(1,0,70);
update(1,1,105);
for(int i1=0;i1<2;i1++)
    for(int j1=0;j1<2;j1++)
        for(int i2=i1;i2<2;i2++)
            for(int j2=j1;j2<2;j2++)
            {
            cout<<i1<<" "<<j1<<" "<<i2<<" "<<j2<<" -> "<<calculate(i1,j1,i2,j2)<<endl;
            }
*/
/*
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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 8184 KB Output is correct
2 Correct 12 ms 8292 KB Output is correct
3 Correct 9 ms 8292 KB Output is correct
4 Incorrect 9 ms 8368 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 8368 KB Output is correct
2 Incorrect 9 ms 8368 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 8372 KB Output is correct
2 Correct 11 ms 8424 KB Output is correct
3 Correct 11 ms 8484 KB Output is correct
4 Incorrect 9 ms 8484 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 8484 KB Output is correct
2 Correct 14 ms 8484 KB Output is correct
3 Correct 10 ms 8488 KB Output is correct
4 Incorrect 13 ms 8488 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 8556 KB Output is correct
2 Correct 11 ms 8556 KB Output is correct
3 Correct 11 ms 8556 KB Output is correct
4 Incorrect 9 ms 8556 KB Output isn't correct
5 Halted 0 ms 0 KB -