oj.uz

Submission #1102575

# Submission time Handle Problem Language Result Execution time Memory
1102575 2024-10-18T11:00:49 Z ttamx Game (IOI13_game) C++11
63 / 100
 1178 ms 256000 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

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

int n,m;

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

struct SegTree2D{
    struct Node;
    using Ptr = Node*;
    struct Node{
        SegTree 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 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 376 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 298 ms 12580 KB Output is correct
5 Correct 220 ms 12872 KB Output is correct
6 Correct 266 ms 9800 KB Output is correct
7 Correct 298 ms 9712 KB Output is correct
8 Correct 259 ms 6728 KB Output is correct
9 Correct 337 ms 9956 KB Output is correct
10 Correct 291 ms 9260 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 1 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 545 ms 15764 KB Output is correct
13 Correct 739 ms 6216 KB Output is correct
14 Correct 166 ms 1096 KB Output is correct
15 Correct 850 ms 8648 KB Output is correct
16 Correct 144 ms 18352 KB Output is correct
17 Correct 542 ms 11624 KB Output is correct
18 Correct 856 ms 18776 KB Output is correct
19 Correct 769 ms 18860 KB Output is correct
20 Correct 658 ms 17992 KB Output is correct
21 Correct 1 ms 336 KB Output is correct

Subtask #4
0 / 17.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 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 305 ms 12760 KB Output is correct
13 Correct 202 ms 12872 KB Output is correct
14 Correct 293 ms 9800 KB Output is correct
15 Correct 328 ms 9704 KB Output is correct
16 Correct 215 ms 6728 KB Output is correct
17 Correct 313 ms 9800 KB Output is correct
18 Correct 282 ms 9180 KB Output is correct
19 Correct 536 ms 15944 KB Output is correct
20 Correct 764 ms 6144 KB Output is correct
21 Correct 162 ms 1096 KB Output is correct
22 Correct 826 ms 8776 KB Output is correct
23 Correct 135 ms 18260 KB Output is correct
24 Correct 507 ms 11392 KB Output is correct
25 Correct 796 ms 18676 KB Output is correct
26 Correct 713 ms 18760 KB Output is correct
27 Correct 661 ms 18096 KB Output is correct
28 Correct 642 ms 253452 KB Output is correct
29 Runtime error 1178 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -

Subtask #5
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 512 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 299 ms 12748 KB Output is correct
13 Correct 217 ms 12872 KB Output is correct
14 Correct 286 ms 9808 KB Output is correct
15 Correct 312 ms 9544 KB Output is correct
16 Correct 207 ms 6728 KB Output is correct
17 Correct 298 ms 9712 KB Output is correct
18 Correct 259 ms 9288 KB Output is correct
19 Correct 490 ms 15920 KB Output is correct
20 Correct 723 ms 6216 KB Output is correct
21 Correct 163 ms 1096 KB Output is correct
22 Correct 833 ms 8704 KB Output is correct
23 Correct 126 ms 18248 KB Output is correct
24 Correct 533 ms 11600 KB Output is correct
25 Correct 739 ms 18624 KB Output is correct
26 Correct 681 ms 18692 KB Output is correct
27 Correct 642 ms 17992 KB Output is correct
28 Correct 670 ms 253272 KB Output is correct
29 Runtime error 1108 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -