oj.uz

Submission #393805

# Submission time Handle Problem Language Result Execution time Memory
393805 2021-04-24T14:27:39 Z MKopchev Game (IOI13_game) C++14
80 / 100
 5132 ms 256004 KB 
#include "game.h"
#include<bits/stdc++.h>
using namespace std;

struct info
{
    long long g;
    int l,r;
};

vector< vector<info> > tree;

int pointer;

int make_info()
{
    info me;
    me.g=0;
    me.l=-1;
    me.r=-1;

    vector<info> now={};
    now.push_back(me);
    now.push_back(me);

    tree.push_back(now);
    pointer++;

    //cout<<"make_info "<<pointer-1<<endl;

    return pointer-1;
}
int build(int id)
{
    //int ret=tree[id].size();

    info me;
    me.g=0;
    me.l=-1;
    me.r=-1;

    tree[id].push_back(me);

    //cout<<"build "<<id<<" "<<ret<<endl;

    return tree[id].size()-1;
}

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

int n,m;
int x_first,y_first,x_second,y_second;

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

long long ask_for(int id,int lq,int rq)
{
    if(id==-1)return 0;

    int l=0,r=m;

    int node=1;

    while(l!=lq||r!=rq)
    {
        int av=(l+r)/2;

        if(rq<=av)
        {
            if(tree[id][node].l==-1)return 0;

            node=tree[id][node].l;
            r=av;
        }
        else
        {
            if(tree[id][node].r==-1)return 0;

            node=tree[id][node].r;
            l=av+1;
        }
    }

    return tree[id][node].g;
}
long long minor_update(int id,int node,int l,int r,int y,long long val,bool type)
{
    //cout<<"minor_update "<<id<<" "<<node<<" "<<l<<" "<<r<<" "<<y<<" "<<val<<" "<<type<<" "<<tree[id].size()<<endl;

    if(l==r)
    {
        if(type==1)tree[id][node].g=val;
        else tree[id][node].g=gcd2(ask_for(tree[id][0].l,l,r),ask_for(tree[id][0].r,l,r));

        //cout<<"stop "<<id<<" "<<node<<" -> "<<tree[id][node].g<<endl;

        return tree[id][node].g;
    }

    int av=(l+r)/2;

    long long ret=0;

    if(y<=av)
    {
        if(tree[id][node].l==-1)
        {
            int help=build(id);
            tree[id][node].l=help;
            //tree[id][node].l=build(id);
        }
        minor_update(id,tree[id][node].l,l,av,y,val,type);
    }

    else
    {
        if(tree[id][node].r==-1)
        {
            int help=build(id);
            tree[id][node].r=help;
            //tree[id][node].r=build(id);
        }
        minor_update(id,tree[id][node].r,av+1,r,y,val,type);
    }

    if(tree[id][node].l!=-1)ret=gcd2(ret,tree[id][tree[id][node].l].g);
    if(tree[id][node].r!=-1)ret=gcd2(ret,tree[id][tree[id][node].r].g);

    tree[id][node].g=ret;

    //cout<<id<<" "<<node<<" -> "<<tree[id][node].g<<endl;

    return ret;
}
void main_update(int node,int l,int r,int x,int y,long long val)
{
    if(l==r)
    {
        minor_update(node,1,0,m,y,val,1);
        return;
    }

    int av=(l+r)/2;

    if(x<=av)
    {
        if(tree[node][0].l==-1)
        {
            int help=make_info();
            tree[node][0].l=help;
        }

        main_update(tree[node][0].l,l,av,x,y,val);
    }
    else
    {
        if(tree[node][0].r==-1)
        {
            int help=make_info();
            tree[node][0].r=help;
        }
        main_update(tree[node][0].r,av+1,r,x,y,val);
    }

    minor_update(node,1,0,m,y,val,0);
}
void update(int P, int Q, long long K) {
    main_update(0,0,n,P,Q,K);
    //cout<<"---"<<endl;
}

long long minor_query(int id,int node,int l,int r,int lq,int rq)
{
    if(l==lq&&r==rq)
    {
        //cout<<"minor "<<id<<" "<<node<<" "<<l<<" "<<r<<" -> "<<tree[id][node].g<<endl;
        return tree[id][node].g;
    }
    long long ret=0;

    int av=(l+r)/2;

    if(lq<=av)
    {
        if(tree[id][node].l!=-1)ret=gcd2(  ret,minor_query(id,tree[id][node].l,l,av,lq,min(av,rq)));
    }

    if(av<rq)
    {
        if(tree[id][node].r!=-1)ret=gcd2(ret,minor_query(id,tree[id][node].r,av+1,r,max(av+1,lq),rq));
    }

    return ret;
}

long long main_query(int node,int l,int r,int lq,int rq)
{
    if(l==lq&&r==rq)return minor_query(node,1,0,m,y_first,y_second);

    long long ret=0;

    int av=(l+r)/2;

    if(lq<=av)
    {
        if(tree[node][0].l!=-1)ret=gcd2(ret,main_query(tree[node][0].l,l,av,lq,min(av,rq)));
    }

    if(av<rq)
    {
        if(tree[node][0].r!=-1)ret=gcd2(ret,main_query(tree[node][0].r,av+1,r,max(av+1,lq),rq));
    }

    return ret;
}
long long calculate(int P, int Q, int U, int V) {
    x_first=P;
    y_first=Q;
    x_second=U;
    y_second=V;

    return main_query(0,0,n,x_first,x_second);
}
/*
int main()
{
init(2,3);

update(0,0,20);
update(0,2,15);
update(1,1,12);
cout<<calculate(0,1,1,2)<<endl;//3
cout<<calculate(0,0,0,2)<<endl;//5
cout<<calculate(0,0,1,1)<<endl;//4
cout<<calculate(0,1,1,2)<<endl;//3

update(0,1,6);
update(1,1,14);
cout<<calculate(0,0,0,2)<<endl;//1
cout<<calculate(0,0,1,1)<<endl;//2

    return 0;
}
*/

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 585 ms 9900 KB Output is correct
5 Correct 477 ms 14316 KB Output is correct
6 Correct 464 ms 11312 KB Output is correct
7 Correct 513 ms 11016 KB Output is correct
8 Correct 349 ms 9412 KB Output is correct
9 Correct 510 ms 11552 KB Output is correct
10 Correct 451 ms 10640 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 292 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 994 ms 16988 KB Output is correct
13 Correct 1661 ms 8624 KB Output is correct
14 Correct 313 ms 5516 KB Output is correct
15 Correct 2027 ms 10772 KB Output is correct
16 Correct 230 ms 17944 KB Output is correct
17 Correct 776 ms 13812 KB Output is correct
18 Correct 1276 ms 19352 KB Output is correct
19 Correct 1070 ms 19720 KB Output is correct
20 Correct 1072 ms 19064 KB Output is correct
21 Correct 1 ms 204 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 594 ms 14396 KB Output is correct
13 Correct 462 ms 14372 KB Output is correct
14 Correct 466 ms 11320 KB Output is correct
15 Correct 520 ms 11000 KB Output is correct
16 Correct 364 ms 9336 KB Output is correct
17 Correct 481 ms 11496 KB Output is correct
18 Correct 486 ms 10684 KB Output is correct
19 Correct 989 ms 17016 KB Output is correct
20 Correct 1641 ms 8516 KB Output is correct
21 Correct 316 ms 5596 KB Output is correct
22 Correct 1938 ms 10956 KB Output is correct
23 Correct 314 ms 17960 KB Output is correct
24 Correct 769 ms 13708 KB Output is correct
25 Correct 1239 ms 19460 KB Output is correct
26 Correct 1107 ms 19692 KB Output is correct
27 Correct 1053 ms 18948 KB Output is correct
28 Correct 1010 ms 154944 KB Output is correct
29 Correct 2065 ms 169672 KB Output is correct
30 Correct 5132 ms 122920 KB Output is correct
31 Correct 4974 ms 100556 KB Output is correct
32 Correct 664 ms 10416 KB Output is correct
33 Correct 839 ms 12636 KB Output is correct
34 Correct 706 ms 163848 KB Output is correct
35 Correct 1437 ms 89768 KB Output is correct
36 Correct 2628 ms 168088 KB Output is correct
37 Correct 2208 ms 167892 KB Output is correct
38 Correct 2144 ms 167368 KB Output is correct
39 Correct 1801 ms 131640 KB Output is correct
40 Correct 1 ms 204 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 296 KB Output is correct
11 Correct 1 ms 296 KB Output is correct
12 Correct 639 ms 14228 KB Output is correct
13 Correct 471 ms 14324 KB Output is correct
14 Correct 467 ms 11300 KB Output is correct
15 Correct 503 ms 10948 KB Output is correct
16 Correct 347 ms 9396 KB Output is correct
17 Correct 486 ms 11576 KB Output is correct
18 Correct 462 ms 10808 KB Output is correct
19 Correct 985 ms 17024 KB Output is correct
20 Correct 1629 ms 8768 KB Output is correct
21 Correct 307 ms 5500 KB Output is correct
22 Correct 1932 ms 10960 KB Output is correct
23 Correct 231 ms 18020 KB Output is correct
24 Correct 778 ms 13744 KB Output is correct
25 Correct 1236 ms 19532 KB Output is correct
26 Correct 1123 ms 19652 KB Output is correct
27 Correct 1031 ms 18932 KB Output is correct
28 Correct 998 ms 155100 KB Output is correct
29 Correct 2035 ms 169756 KB Output is correct
30 Correct 5049 ms 122828 KB Output is correct
31 Correct 4840 ms 100404 KB Output is correct
32 Correct 647 ms 10424 KB Output is correct
33 Correct 843 ms 12612 KB Output is correct
34 Correct 678 ms 163900 KB Output is correct
35 Correct 1362 ms 89748 KB Output is correct
36 Correct 2619 ms 167764 KB Output is correct
37 Correct 2138 ms 167908 KB Output is correct
38 Correct 2128 ms 167604 KB Output is correct
39 Runtime error 1277 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -