oj.uz

Submission #598508

# Submission time Handle Problem Language Result Execution time Memory
598508 2022-07-18T12:30:32 Z Bench0310 Game (IOI13_game) C++17
100 / 100
 5803 ms 77696 KB 
#include <bits/stdc++.h>
#include "game.h"

using namespace std;
typedef long long ll;

mt19937 gen(513);
int N,M;

struct Treap;
using twoTreaps=array<Treap*,2>;

struct Treap
{
    int p;
    ll val;
    ll g;
    int priority;
    twoTreaps kids;
    Treap(int np,ll ng){p=np;val=g=ng;priority=gen();kids[0]=kids[1]=nullptr;}
};

void recalc(Treap *me)
{
    if(!me) return;
    me->g=gcd(gcd(me->kids[0]?me->kids[0]->g:0,me->kids[1]?me->kids[1]->g:0),me->val);
}

twoTreaps tsplit(Treap *me,int lim) //p<=lim
{
    if(!me) return {nullptr,nullptr};
    if(me->p>lim)
    {
        auto [one,two]=tsplit(me->kids[0],lim);
        me->kids[0]=two;
        recalc(me);
        return {one,me};
    }
    else
    {
        auto [one,two]=tsplit(me->kids[1],lim);
        me->kids[1]=one;
        recalc(me);
        return {me,two};
    }
}

Treap* tmerge(Treap *a,Treap *b)
{
    if(!a) return b;
    if(!b) return a;
    if(a->priority<b->priority)
    {
        a->kids[1]=tmerge(a->kids[1],b);
        recalc(a);
        return a;
    }
    else
    {
        b->kids[0]=tmerge(a,b->kids[0]);
        recalc(b);
        return b;
    }
}

Treap* tupdate(Treap *me,int p,ll g)
{
    auto [one,tmp]=tsplit(me,p-1);
    auto [two,three]=tsplit(tmp,p);
    if(two==nullptr) two=new Treap(p,g);
    else two->val=two->g=g;
    return tmerge(tmerge(one,two),three);
}

ll tquery(Treap *me,int l,int r)
{
    auto [one,tmp]=tsplit(me,l-1);
    auto [two,three]=tsplit(tmp,r);
    ll g=(two?two->g:0);
    tmerge(tmerge(one,two),three);
    return g;
}

struct Up
{
    Treap *me;
    Up *l,*r;
    Up(){me=nullptr;l=r=nullptr;}
    void extend(){if(!l){l=new Up();r=new Up();}}
};

void update(Up *now,int l,int r,int pos_r,int pos_c,ll g)
{
    if(l==r) now->me=tupdate(now->me,pos_c,g);
    else
    {
        now->extend();
        int m=(l+r)/2;
        if(pos_r<=m) update(now->l,l,m,pos_r,pos_c,g);
        else update(now->r,m+1,r,pos_r,pos_c,g);
        now->me=tupdate(now->me,pos_c,gcd(tquery(now->l->me,pos_c,pos_c),tquery(now->r->me,pos_c,pos_c)));
    }
}

ll query(Up *now,int l,int r,int ql,int qr,int cl,int cr)
{
    if(ql>qr||!now) return 0;
    if(l==ql&&r==qr) return tquery(now->me,cl,cr);
    int m=(l+r)/2;
    return gcd(query(now->l,l,m,ql,min(qr,m),cl,cr),query(now->r,m+1,r,max(ql,m+1),qr,cl,cr));
}

Up* root=nullptr;

void init(int n,int m)
{
    N=n;
    M=m;
    root=new Up();
}

void update(int r,int c,ll k)
{
    update(root,1,N,r+1,c+1,k);
}

ll calculate(int p,int q,int u,int v)
{
    return query(root,1,N,p+1,u+1,q+1,v+1);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 895 ms 11304 KB Output is correct
5 Correct 383 ms 11192 KB Output is correct
6 Correct 1123 ms 8720 KB Output is correct
7 Correct 1313 ms 8596 KB Output is correct
8 Correct 845 ms 7436 KB Output is correct
9 Correct 1226 ms 8600 KB Output is correct
10 Correct 1106 ms 8148 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 300 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1329 ms 13448 KB Output is correct
13 Correct 2924 ms 7608 KB Output is correct
14 Correct 395 ms 5580 KB Output is correct
15 Correct 3169 ms 9100 KB Output is correct
16 Correct 418 ms 11332 KB Output is correct
17 Correct 1686 ms 9676 KB Output is correct
18 Correct 3031 ms 12764 KB Output is correct
19 Correct 2624 ms 12868 KB Output is correct
20 Correct 2353 ms 12552 KB Output is correct
21 Correct 0 ms 212 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 893 ms 11420 KB Output is correct
13 Correct 372 ms 11312 KB Output is correct
14 Correct 1149 ms 8660 KB Output is correct
15 Correct 1301 ms 8372 KB Output is correct
16 Correct 836 ms 7392 KB Output is correct
17 Correct 1225 ms 8528 KB Output is correct
18 Correct 1116 ms 8152 KB Output is correct
19 Correct 1321 ms 13400 KB Output is correct
20 Correct 2895 ms 7688 KB Output is correct
21 Correct 398 ms 5580 KB Output is correct
22 Correct 3134 ms 8996 KB Output is correct
23 Correct 407 ms 11304 KB Output is correct
24 Correct 1659 ms 9672 KB Output is correct
25 Correct 3015 ms 12820 KB Output is correct
26 Correct 2540 ms 12900 KB Output is correct
27 Correct 2347 ms 12472 KB Output is correct
28 Correct 1044 ms 41216 KB Output is correct
29 Correct 1955 ms 43920 KB Output is correct
30 Correct 3787 ms 31064 KB Output is correct
31 Correct 3369 ms 25704 KB Output is correct
32 Correct 598 ms 10204 KB Output is correct
33 Correct 871 ms 10596 KB Output is correct
34 Correct 589 ms 37580 KB Output is correct
35 Correct 1997 ms 26428 KB Output is correct
36 Correct 3859 ms 41856 KB Output is correct
37 Correct 3067 ms 42008 KB Output is correct
38 Correct 2972 ms 41456 KB Output is correct
39 Correct 2591 ms 34632 KB Output is correct
40 Correct 0 ms 212 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 304 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 885 ms 11420 KB Output is correct
13 Correct 398 ms 11232 KB Output is correct
14 Correct 1107 ms 8628 KB Output is correct
15 Correct 1371 ms 8444 KB Output is correct
16 Correct 838 ms 7508 KB Output is correct
17 Correct 1247 ms 8656 KB Output is correct
18 Correct 1109 ms 8208 KB Output is correct
19 Correct 1333 ms 13380 KB Output is correct
20 Correct 2873 ms 7760 KB Output is correct
21 Correct 406 ms 5592 KB Output is correct
22 Correct 3166 ms 9108 KB Output is correct
23 Correct 428 ms 11288 KB Output is correct
24 Correct 1700 ms 9764 KB Output is correct
25 Correct 2969 ms 12808 KB Output is correct
26 Correct 2537 ms 13040 KB Output is correct
27 Correct 2327 ms 12488 KB Output is correct
28 Correct 989 ms 41180 KB Output is correct
29 Correct 1915 ms 43880 KB Output is correct
30 Correct 3892 ms 31100 KB Output is correct
31 Correct 3376 ms 25692 KB Output is correct
32 Correct 595 ms 10068 KB Output is correct
33 Correct 863 ms 10472 KB Output is correct
34 Correct 609 ms 37624 KB Output is correct
35 Correct 1927 ms 26404 KB Output is correct
36 Correct 3648 ms 41800 KB Output is correct
37 Correct 2931 ms 42048 KB Output is correct
38 Correct 2865 ms 41296 KB Output is correct
39 Correct 1382 ms 75584 KB Output is correct
40 Correct 3142 ms 77696 KB Output is correct
41 Correct 5803 ms 57924 KB Output is correct
42 Correct 4949 ms 45404 KB Output is correct
43 Correct 1277 ms 72272 KB Output is correct
44 Correct 903 ms 10700 KB Output is correct
45 Correct 2461 ms 34576 KB Output is correct
46 Correct 5003 ms 76360 KB Output is correct
47 Correct 5062 ms 76360 KB Output is correct
48 Correct 4796 ms 75992 KB Output is correct
49 Correct 0 ms 300 KB Output is correct