Submission #587134

#	Time	Username	Problem	Language	Result	Execution time	Memory
587134		FatihSolak	Game (IOI13_game)	C++17	10 / 100	138 ms	256000 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
struct SegTree{
    vector<long long> t;
    int n;
    SegTree(int size){
        n = size;
        t.assign(4*n,0);
    }
    void init(int size){
        n = size;
        t.assign(4*n,0);
    }
    void upd(int v,int tl,int tr,int pos,long long val){
        if(tl == tr){
            t[v] = val;
            return;
        }
        int tm = (tl + tr)/2;
        if(pos <= tm)
            upd(v*2,tl,tm,pos,val);
        else upd(v*2+1,tm+1,tr,pos,val);
        t[v] = gcd2(t[v*2],t[v*2+1]);
    }
    long long get(int v,int tl,int tr,int l,int r){
        if(tr < l || r < tl)
            return 0;
        if(l <= tl && tr <= r){
            return t[v];
        }
        int tm = (tl + tr)/2;
        return gcd2(get(v*2,tl,tm,l,r),get(v*2+1,tm+1,tr,l,r));
    }
    void upd(int pos,long long val){
        upd(1,1,n,pos,val);
    }
    long long get(int l,int r){
        return get(1,1,n,l,r);
    }
};
struct SegTree2D{
    vector<SegTree> t;
    vector<vector<SegTree>> numbers;
    int n;
    int m;
    void init(int size1,int size2){
        n = size1;
        m = size2;
        t.assign(4*n,m);
        numbers.assign(4*n,{});
        build(1,1,n);
    }
    void build(int v,int tl,int tr){
        numbers[v].assign(m+1,n);
        if(tl == tr)return;
        int tm = (tl + tr)/2;
        build(v*2,tl,tm);
        build(v*2+1,tm+1,tr);
    }
    void upd(int v,int tl,int tr,int x,int y,long long val){
        numbers[v][y].upd(x,val);
        t[v].upd(y,numbers[v][y].get(tl,tr));
        if(tl == tr){
            return;
        }
        int tm = (tl + tr)/2;
        if(x <= tm)
            upd(v*2,tl,tm,x,y,val);
        else upd(v*2+1,tm+1,tr,x,y,val);
    }
    long long get(int v,int tl,int tr,int l,int r,int l2,int r2){
        if(tr < l || r < tl)
            return 0;
        if(l <= tl && tr <= r){
            return t[v].get(l2,r2);
        }
        int tm = (tl + tr)/2;
        return gcd2(get(v*2,tl,tm,l,r,l2,r2),get(v*2+1,tm+1,tr,l,r,l2,r2));
    }
    void upd(int x,int y,long long val){
        upd(1,1,n,x,y,val);
    }
    long long get(int l,int r,int l2,int r2){
        return get(1,1,n,l,r,l2,r2);
    }
}tree;
void init(int R, int C) {
    tree.init(R,C);
}

void update(int P, int Q, long long K) {
    P++,Q++;
    tree.upd(P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
    P++,Q++,U++,V++;
    return tree.get(P,U,Q,V);
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20