oj.uz

Submission #1102562

# Submission time Handle Problem Language Result Execution time Memory
1102562 2024-10-18T09:45:57 Z ttamx Game (IOI13_game) C++17
0 / 100
 1 ms 504 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

ll gcd2(ll X,ll Y){
    while(X!=Y&&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(new Node()){}
    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(new Node()){}
    void modify(int l,int r,Ptr &t,int x,int y,ll v){
        if(!t)t=new Node();
        t->tree.modify(y,v);
        if(l==r)return;
        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);
    }
    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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 504 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 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 Incorrect 1 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -