oj.uz

Submission #871281

# Submission time Handle Problem Language Result Execution time Memory
871281 2023-11-10T11:48:24 Z HuyQuang_re_Zero Game (IOI13_game) C++14
100 / 100
 4346 ms 67800 KB 
#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define TII pair <treap*,treap*>
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))

#include "game.h"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll GCD(ll a,ll b) { return (a==0 && b==0) ? 0 : __gcd(a,b); }
struct treap
{
    treap *left,*right;
    ll key,prio,val,my_val;
    treap(ll _key,ll _val) { key=_key; val=my_val=_val; prio=rng(); left=right=NULL; }
    void comp()
    {
        val=GCD(my_val,GCD(left==NULL ? 0 : left->val,right==NULL ? 0 : right->val));
    }
};

TII Split(treap *u,ll key)
{
    if(u==NULL) return { NULL,NULL };
    if(u->key>key)
    {
        TII x=Split(u->left,key);
        u->left=x.snd;
        u->comp();
        return { x.fst,u };
    }
    else
    {
        TII x=Split(u->right,key);
        u->right=x.fst;
        u->comp();
        return { u,x.snd };
    }
}

treap *Merge(treap *u,treap *v)
{
    if(u==NULL && v==NULL) return NULL;
    if(u==NULL) return v;
    if(v==NULL) return u;
    if(u->prio>=v->prio)
    {
        u->right=Merge(u->right,v);
        u->comp();
        return u;
    }
    else
    {
        v->left=Merge(u,v->left);
        v->comp();
        return v;
    }
}
ll get_range(treap *u,ll l,ll r)
{
    TII x=Split(u,l-1);
    TII y=Split(x.snd,r);
   // cerr<<y.fst->key<<'\n';
    ll res=(y.fst==NULL ? 0 : y.fst->val);
    treap *tg=Merge(x.fst,y.fst);
    Merge(tg,y.snd);
    return res;
}
treap *Assign(treap *u,ll key,ll val)
{
    TII x=Split(u,key-1);
    TII y=Split(x.snd,key);
    treap *v=new treap(key,val);
  //  get_range(v,key,key)<<'\n';
   // exit(0);
    u=Merge(x.fst,v);
  //  cerr<<get_range(u,val,val)<<'\n';
    u=Merge(u,y.snd);
  //  cerr<<get_range(u,val,val)<<'\n';
    return u;
}


////////////////////////////////////////////////////////////////////////
struct node
{
    node *left,*right;
    treap *tree;
} *root;
treap *get_tree(node *u) { return (u==NULL) ? NULL : u->tree; }
node *UPDATE(node *u,int l,int r,int x,int y,ll k)
{
    if(u==NULL) u=new node();
    if(l==r)
    {
        u->tree=Assign(u->tree,y,k);
        return u;
    }
    int mid=(l+r)>>1;
    if(x<=mid) u->left=UPDATE(u->left,l,mid,x,y,k);
    else u->right=UPDATE(u->right,mid+1,r,x,y,k);
    u->tree=Assign(u->tree,y,GCD(get_range(get_tree(u->left),y,y),get_range(get_tree(u->right),y,y)));
    return u;
}

ll GET(node *u,int l,int r,int x1,int y1,int x2,int y2)
{
    if(u==NULL || x1>r || x2<l) return 0;
    if(x1<=l && r<=x2) return get_range(u->tree,y1,y2);
    int mid=(l+r)>>1;
    return GCD(GET(u->left,l,mid,x1,y1,x2,y2),GET(u->right,mid+1,r,x1,y1,x2,y2));
}

ll n,m,x,y,k,q,type;
void init(int _n,int _m) { n=_n; m=_m; }
void update(int x,int y,ll k)
{
    root=UPDATE(root,1,n,x+1,y+1,k);
}
ll calculate(int x1,int y1,int x2,int y2)
{
    return GET(root,1,n,x1+1,y1+1,x2+1,y2+1);
}

/*
int main()
{
    freopen("game.inp","r",stdin);
    freopen("game.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>m>>q;
    init(n,m);
    while(cin>>type)
        if(type==1) cin>>x>>y>>k,update(x,y,k);
        else
        {
            int x1,y1,x2,y2;
            cin>>x1>>y1>>x2>>y2;
            cout<<calculate(x1,y1,x2,y2)<<'\n';
        }
}
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 436 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 440 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 671 ms 11400 KB Output is correct
5 Correct 334 ms 11440 KB Output is correct
6 Correct 944 ms 8848 KB Output is correct
7 Correct 1081 ms 8416 KB Output is correct
8 Correct 686 ms 7464 KB Output is correct
9 Correct 1010 ms 8712 KB Output is correct
10 Correct 888 ms 8272 KB Output is correct
11 Correct 0 ms 344 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 440 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 440 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 416 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 436 KB Output is correct
12 Correct 950 ms 15352 KB Output is correct
13 Correct 2077 ms 12228 KB Output is correct
14 Correct 319 ms 13108 KB Output is correct
15 Correct 2262 ms 13664 KB Output is correct
16 Correct 340 ms 12880 KB Output is correct
17 Correct 1415 ms 10528 KB Output is correct
18 Correct 2440 ms 14184 KB Output is correct
19 Correct 2132 ms 14844 KB Output is correct
20 Correct 1894 ms 14004 KB Output is correct
21 Correct 0 ms 348 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 681 ms 11456 KB Output is correct
13 Correct 298 ms 11520 KB Output is correct
14 Correct 912 ms 8932 KB Output is correct
15 Correct 1056 ms 8980 KB Output is correct
16 Correct 678 ms 7492 KB Output is correct
17 Correct 1010 ms 8472 KB Output is correct
18 Correct 858 ms 8372 KB Output is correct
19 Correct 992 ms 15492 KB Output is correct
20 Correct 2049 ms 11920 KB Output is correct
21 Correct 325 ms 12884 KB Output is correct
22 Correct 2268 ms 13192 KB Output is correct
23 Correct 341 ms 12880 KB Output is correct
24 Correct 1414 ms 10288 KB Output is correct
25 Correct 2450 ms 14544 KB Output is correct
26 Correct 2113 ms 14832 KB Output is correct
27 Correct 1877 ms 13888 KB Output is correct
28 Correct 747 ms 36216 KB Output is correct
29 Correct 1534 ms 39052 KB Output is correct
30 Correct 2806 ms 30324 KB Output is correct
31 Correct 2415 ms 29664 KB Output is correct
32 Correct 476 ms 29776 KB Output is correct
33 Correct 670 ms 29364 KB Output is correct
34 Correct 485 ms 32768 KB Output is correct
35 Correct 1608 ms 23888 KB Output is correct
36 Correct 3048 ms 36916 KB Output is correct
37 Correct 2431 ms 37548 KB Output is correct
38 Correct 2360 ms 36484 KB Output is correct
39 Correct 2050 ms 31196 KB Output is correct
40 Correct 0 ms 344 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 440 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 683 ms 11604 KB Output is correct
13 Correct 325 ms 11348 KB Output is correct
14 Correct 917 ms 8720 KB Output is correct
15 Correct 1085 ms 8784 KB Output is correct
16 Correct 672 ms 7544 KB Output is correct
17 Correct 1030 ms 8696 KB Output is correct
18 Correct 901 ms 8120 KB Output is correct
19 Correct 984 ms 15440 KB Output is correct
20 Correct 2175 ms 11836 KB Output is correct
21 Correct 321 ms 13332 KB Output is correct
22 Correct 2254 ms 13232 KB Output is correct
23 Correct 333 ms 13040 KB Output is correct
24 Correct 1403 ms 10416 KB Output is correct
25 Correct 2410 ms 14168 KB Output is correct
26 Correct 2067 ms 14480 KB Output is correct
27 Correct 1853 ms 14172 KB Output is correct
28 Correct 735 ms 36436 KB Output is correct
29 Correct 1425 ms 39296 KB Output is correct
30 Correct 2766 ms 30120 KB Output is correct
31 Correct 2449 ms 29780 KB Output is correct
32 Correct 468 ms 29520 KB Output is correct
33 Correct 692 ms 29268 KB Output is correct
34 Correct 552 ms 32652 KB Output is correct
35 Correct 1555 ms 23868 KB Output is correct
36 Correct 2886 ms 37156 KB Output is correct
37 Correct 2326 ms 37120 KB Output is correct
38 Correct 2274 ms 37064 KB Output is correct
39 Correct 1099 ms 65500 KB Output is correct
40 Correct 2450 ms 67800 KB Output is correct
41 Correct 4346 ms 57364 KB Output is correct
42 Correct 3822 ms 55896 KB Output is correct
43 Correct 1006 ms 62492 KB Output is correct
44 Correct 766 ms 52984 KB Output is correct
45 Correct 2025 ms 31132 KB Output is correct
46 Correct 4011 ms 66540 KB Output is correct
47 Correct 3885 ms 66464 KB Output is correct
48 Correct 3663 ms 65960 KB Output is correct
49 Correct 0 ms 348 KB Output is correct