oj.uz

Submission #1102630

# Submission time Handle Problem Language Result Execution time Memory
1102630 2024-10-18T13:29:36 Z ttamx Game (IOI13_game) C++17
100 / 100
 4011 ms 56852 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll gcd2(ll X,ll Y){
    while(Y!=0)tie(X,Y)=make_pair(Y,X%Y);
    return X;
}

int n,m;

struct Treap{
    struct Node;
    using Ptr = Node*;
    struct Node{
        ll val,sum;
        int key,prio;
        Ptr l,r;
        Node(int i,ll v):val(v),sum(v),key(i),prio(rng()),l(),r(){}
    };
    Ptr root;
    Treap():root(){}
    ll get(Ptr t){
        return t?t->sum:0LL;
    }
    void pull(Ptr t){
        if(!t)return;
        t->sum=gcd2(t->val,gcd2(get(t->l),get(t->r)));
    }
    void merge(Ptr &t,Ptr l,Ptr r){
        if(!l)return void(t=r);
        if(!r)return void(t=l);
        if(l->prio>r->prio)merge(l->r,l->r,r),t=l;
        else merge(r->l,l,r->l),t=r;
        pull(t);
    }
    void split(Ptr t,Ptr &l,Ptr &r,int key){
        if(!t)return void(l=r=t);
        if(t->key<=key)split(t->r,t->r,r,key),l=t;
        else split(t->l,l,t->l,key),r=t;
        pull(t);
    }
    void modify(int x,ll v){
        Ptr l,t,r;
        split(root,l,root,x-1);
        split(root,t,r,x);
        if(t)t->val=t->sum=v;
        else t=new Node(x,v);
        merge(root,l,t);
        merge(root,root,r);
    }
    ll query(int x,int y){
        Ptr l,t,r;
        split(root,l,root,x-1);
        split(root,t,r,y);
        ll res=get(t);
        merge(root,l,t);
        merge(root,root,r);
        return res;
    }
};

struct SegTree2D{
    struct Node;
    using Ptr = Node*;
    struct Node{
        Treap tree;
        Ptr l,r;
        Node():tree(),l(),r(){}
    };
    Ptr root;
    SegTree2D():root(){}
    ll get(Ptr t,int x){
        return t?t->tree.query(x,x):0LL;
    }
    void modify(int l,int r,Ptr &t,int x,int y,ll v){
        if(!t)t=new Node();
        if(l<r){
            int m=(l+r)/2;
            if(x<=m)modify(l,m,t->l,x,y,v);
            else modify(m+1,r,t->r,x,y,v);
            v=gcd2(get(t->l,y),get(t->r,y));
        }
        t->tree.modify(y,v);
    }
    void modify(int x,int y,ll v){
        modify(0,n-1,root,x,y,v);
    }
    ll query(int l,int r,Ptr &t,int x,int y,int x2,int y2){
        if(y<l||r<x||!t)return 0LL;
        if(x<=l&&r<=y)return t->tree.query(x2,y2);
        int m=(l+r)/2;
        return gcd2(query(l,m,t->l,x,y,x2,y2),query(m+1,r,t->r,x,y,x2,y2));
    }
    ll query(int x,int y,int x2,int y2){
        return query(0,n-1,root,x,y,x2,y2);
    }
}seg;

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

void update(int P,int Q,ll K){
    seg.modify(P,Q,K);
}

ll calculate(int P,int Q,int U,int V){
    return seg.query(P,U,Q,V);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 512 ms 6256 KB Output is correct
5 Correct 234 ms 6728 KB Output is correct
6 Correct 737 ms 3436 KB Output is correct
7 Correct 809 ms 3104 KB Output is correct
8 Correct 517 ms 2924 KB Output is correct
9 Correct 789 ms 3124 KB Output is correct
10 Correct 668 ms 2728 KB Output is correct
11 Correct 1 ms 336 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 782 ms 8000 KB Output is correct
13 Correct 1261 ms 3112 KB Output is correct
14 Correct 238 ms 1008 KB Output is correct
15 Correct 1327 ms 3732 KB Output is correct
16 Correct 276 ms 5704 KB Output is correct
17 Correct 1300 ms 4144 KB Output is correct
18 Correct 2052 ms 5960 KB Output is correct
19 Correct 1873 ms 6192 KB Output is correct
20 Correct 1608 ms 5624 KB Output is correct
21 Correct 1 ms 336 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 504 ms 6472 KB Output is correct
13 Correct 244 ms 6728 KB Output is correct
14 Correct 755 ms 3400 KB Output is correct
15 Correct 838 ms 3044 KB Output is correct
16 Correct 580 ms 2888 KB Output is correct
17 Correct 836 ms 3128 KB Output is correct
18 Correct 672 ms 2788 KB Output is correct
19 Correct 717 ms 8008 KB Output is correct
20 Correct 1261 ms 3180 KB Output is correct
21 Correct 245 ms 1008 KB Output is correct
22 Correct 1370 ms 3656 KB Output is correct
23 Correct 279 ms 5700 KB Output is correct
24 Correct 1260 ms 4012 KB Output is correct
25 Correct 2224 ms 5960 KB Output is correct
26 Correct 1890 ms 6008 KB Output is correct
27 Correct 1513 ms 5452 KB Output is correct
28 Correct 613 ms 25252 KB Output is correct
29 Correct 1281 ms 24680 KB Output is correct
30 Correct 1860 ms 20772 KB Output is correct
31 Correct 1606 ms 16928 KB Output is correct
32 Correct 336 ms 5704 KB Output is correct
33 Correct 490 ms 6256 KB Output is correct
34 Correct 379 ms 21064 KB Output is correct
35 Correct 1421 ms 16808 KB Output is correct
36 Correct 2833 ms 21496 KB Output is correct
37 Correct 2279 ms 29960 KB Output is correct
38 Correct 2107 ms 21120 KB Output is correct
39 Correct 1828 ms 16988 KB Output is correct
40 Correct 1 ms 336 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 508 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 504 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 466 ms 6288 KB Output is correct
13 Correct 244 ms 6708 KB Output is correct
14 Correct 726 ms 3328 KB Output is correct
15 Correct 897 ms 3144 KB Output is correct
16 Correct 542 ms 2888 KB Output is correct
17 Correct 853 ms 3400 KB Output is correct
18 Correct 679 ms 2792 KB Output is correct
19 Correct 781 ms 8024 KB Output is correct
20 Correct 1300 ms 3144 KB Output is correct
21 Correct 238 ms 840 KB Output is correct
22 Correct 1331 ms 3744 KB Output is correct
23 Correct 259 ms 5704 KB Output is correct
24 Correct 1203 ms 4140 KB Output is correct
25 Correct 2160 ms 5972 KB Output is correct
26 Correct 1909 ms 6224 KB Output is correct
27 Correct 1614 ms 5532 KB Output is correct
28 Correct 673 ms 25416 KB Output is correct
29 Correct 1224 ms 24140 KB Output is correct
30 Correct 1836 ms 16888 KB Output is correct
31 Correct 1616 ms 17012 KB Output is correct
32 Correct 342 ms 5704 KB Output is correct
33 Correct 512 ms 6224 KB Output is correct
34 Correct 361 ms 26440 KB Output is correct
35 Correct 1432 ms 11592 KB Output is correct
36 Correct 2685 ms 26956 KB Output is correct
37 Correct 2157 ms 29924 KB Output is correct
38 Correct 2075 ms 26696 KB Output is correct
39 Correct 961 ms 55000 KB Output is correct
40 Correct 2325 ms 56852 KB Output is correct
41 Correct 3017 ms 42644 KB Output is correct
42 Correct 2565 ms 34224 KB Output is correct
43 Correct 820 ms 51632 KB Output is correct
44 Correct 578 ms 10572 KB Output is correct
45 Correct 1957 ms 27188 KB Output is correct
46 Correct 3690 ms 55740 KB Output is correct
47 Correct 4011 ms 55628 KB Output is correct
48 Correct 3333 ms 55336 KB Output is correct
49 Correct 1 ms 340 KB Output is correct