oj.uz

Submission #393810

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

const int MX=22000*31+42;

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

vector<info> tree[MX];

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[pointer]=(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 10 ms 16204 KB Output is correct
2 Correct 12 ms 16332 KB Output is correct
3 Correct 10 ms 16280 KB Output is correct
4 Correct 10 ms 16204 KB Output is correct
5 Correct 10 ms 16228 KB Output is correct
6 Correct 11 ms 16320 KB Output is correct
7 Correct 10 ms 16204 KB Output is correct
8 Correct 10 ms 16204 KB Output is correct
9 Correct 10 ms 16332 KB Output is correct
10 Correct 10 ms 16332 KB Output is correct
11 Correct 11 ms 16332 KB Output is correct
12 Correct 10 ms 16204 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16204 KB Output is correct
2 Correct 10 ms 16216 KB Output is correct
3 Correct 10 ms 16204 KB Output is correct
4 Correct 612 ms 25820 KB Output is correct
5 Correct 527 ms 26516 KB Output is correct
6 Correct 497 ms 22836 KB Output is correct
7 Correct 518 ms 22700 KB Output is correct
8 Correct 381 ms 21168 KB Output is correct
9 Correct 518 ms 22944 KB Output is correct
10 Correct 465 ms 21756 KB Output is correct
11 Correct 11 ms 16240 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 16204 KB Output is correct
2 Correct 10 ms 16332 KB Output is correct
3 Correct 11 ms 16328 KB Output is correct
4 Correct 10 ms 16312 KB Output is correct
5 Correct 10 ms 16204 KB Output is correct
6 Correct 10 ms 16352 KB Output is correct
7 Correct 10 ms 16204 KB Output is correct
8 Correct 10 ms 16320 KB Output is correct
9 Correct 10 ms 16332 KB Output is correct
10 Correct 12 ms 16332 KB Output is correct
11 Correct 10 ms 16332 KB Output is correct
12 Correct 1006 ms 29148 KB Output is correct
13 Correct 1605 ms 20740 KB Output is correct
14 Correct 325 ms 16928 KB Output is correct
15 Correct 1979 ms 22412 KB Output is correct
16 Correct 243 ms 29596 KB Output is correct
17 Correct 806 ms 24900 KB Output is correct
18 Correct 1356 ms 30036 KB Output is correct
19 Correct 1085 ms 30232 KB Output is correct
20 Correct 1044 ms 29460 KB Output is correct
21 Correct 10 ms 16204 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16204 KB Output is correct
2 Correct 10 ms 16280 KB Output is correct
3 Correct 10 ms 16340 KB Output is correct
4 Correct 9 ms 16204 KB Output is correct
5 Correct 10 ms 16204 KB Output is correct
6 Correct 11 ms 16296 KB Output is correct
7 Correct 10 ms 16204 KB Output is correct
8 Correct 10 ms 16204 KB Output is correct
9 Correct 10 ms 16332 KB Output is correct
10 Correct 10 ms 16332 KB Output is correct
11 Correct 10 ms 16352 KB Output is correct
12 Correct 595 ms 25880 KB Output is correct
13 Correct 497 ms 26544 KB Output is correct
14 Correct 464 ms 22768 KB Output is correct
15 Correct 500 ms 22568 KB Output is correct
16 Correct 357 ms 21384 KB Output is correct
17 Correct 520 ms 22880 KB Output is correct
18 Correct 475 ms 21744 KB Output is correct
19 Correct 1048 ms 28916 KB Output is correct
20 Correct 1613 ms 20708 KB Output is correct
21 Correct 311 ms 16964 KB Output is correct
22 Correct 1912 ms 22312 KB Output is correct
23 Correct 270 ms 29684 KB Output is correct
24 Correct 758 ms 24824 KB Output is correct
25 Correct 1260 ms 30040 KB Output is correct
26 Correct 1084 ms 30388 KB Output is correct
27 Correct 1064 ms 29456 KB Output is correct
28 Correct 999 ms 156176 KB Output is correct
29 Correct 1979 ms 171472 KB Output is correct
30 Correct 5009 ms 129664 KB Output is correct
31 Correct 4787 ms 107692 KB Output is correct
32 Correct 623 ms 17220 KB Output is correct
33 Correct 809 ms 19484 KB Output is correct
34 Correct 672 ms 169036 KB Output is correct
35 Correct 1375 ms 93888 KB Output is correct
36 Correct 2535 ms 169012 KB Output is correct
37 Correct 2083 ms 169272 KB Output is correct
38 Correct 2132 ms 168740 KB Output is correct
39 Correct 1763 ms 134020 KB Output is correct
40 Correct 10 ms 16204 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 16284 KB Output is correct
2 Correct 10 ms 16288 KB Output is correct
3 Correct 10 ms 16388 KB Output is correct
4 Correct 10 ms 16204 KB Output is correct
5 Correct 10 ms 16316 KB Output is correct
6 Correct 10 ms 16332 KB Output is correct
7 Correct 10 ms 16204 KB Output is correct
8 Correct 10 ms 16204 KB Output is correct
9 Correct 10 ms 16332 KB Output is correct
10 Correct 10 ms 16332 KB Output is correct
11 Correct 10 ms 16332 KB Output is correct
12 Correct 616 ms 25816 KB Output is correct
13 Correct 465 ms 26408 KB Output is correct
14 Correct 471 ms 22816 KB Output is correct
15 Correct 499 ms 22520 KB Output is correct
16 Correct 365 ms 21172 KB Output is correct
17 Correct 488 ms 22828 KB Output is correct
18 Correct 456 ms 21756 KB Output is correct
19 Correct 980 ms 28896 KB Output is correct
20 Correct 1603 ms 20772 KB Output is correct
21 Correct 310 ms 16836 KB Output is correct
22 Correct 1923 ms 22452 KB Output is correct
23 Correct 232 ms 29764 KB Output is correct
24 Correct 756 ms 24780 KB Output is correct
25 Correct 1225 ms 30000 KB Output is correct
26 Correct 1050 ms 30252 KB Output is correct
27 Correct 1008 ms 29524 KB Output is correct
28 Correct 950 ms 156220 KB Output is correct
29 Correct 1969 ms 171604 KB Output is correct
30 Correct 5006 ms 129512 KB Output is correct
31 Correct 4798 ms 107652 KB Output is correct
32 Correct 628 ms 17244 KB Output is correct
33 Correct 806 ms 19660 KB Output is correct
34 Correct 652 ms 168980 KB Output is correct
35 Correct 1311 ms 93896 KB Output is correct
36 Correct 2465 ms 169020 KB Output is correct
37 Correct 2098 ms 169116 KB Output is correct
38 Correct 2088 ms 168772 KB Output is correct
39 Runtime error 1130 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -