Submission #847821

#	Time	Username	Problem	Language	Result	Execution time	Memory
847821		YassirSalama	Game (IOI13_game)	C++17	63 / 100	1301 ms	256000 KiB

game

#include "game.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <iomanip>
#include <cmath>
#include <limits>
#include <map>
#include <utility>
#include <cctype>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <functional>
#include <iterator>
using namespace std;
#define OVL(x,s) for(auto y:x) cout<<y<<s; cout<<"\n";
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#define endl "\n"
#define pb push_back
#define F first
#define S second
#define ll long long
#define mod 1000000007
#define all(v) v.begin(),v.end()
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 Node_y{
    ll val;
    Node_y* left,*right;
    Node_y() {
        val=0LL;
        left=(nullptr),right=(nullptr);
    }
};
struct Node_x{
    Node_y* node;
    Node_x* left;
    Node_x* right;
    Node_x() : node(new Node_y()),left(nullptr),right(nullptr) {}
};
Node_x* root;
int n,m;
#define op(a,b) gcd2(a,b)
ll get(Node_y* node,int l,int r,int ql){
    if(node==nullptr) return 0LL;
    if(l==r) 
        return node->val;
    int mid=(l+r)/2;
    if(ql<=mid){
        if(node->left==nullptr) return 0;
        return get(node->left,l,mid,ql);
    }else{
        if(node->right==nullptr) return 0;
        return get(node->right,mid+1,r,ql);
    }
}
void update_y(Node_x* node,int lx,int rx,Node_y* nodey,int ly,int ry,int i,int j,ll x){
    if(ly==ry){
        if(lx==rx){
            nodey->val=x;
        }else{
            nodey->val=0;
            if(node->left==nullptr)
                nodey->val=nodey->val;
            else nodey->val=op(nodey->val,get(node->left->node,0,m-1,ly));
            if(node->right==nullptr)
                nodey->val=nodey->val;
            else nodey->val=op(nodey->val,get(node->right->node,0,m-1,ly));
        }
        return;
    }
    int mid=(ly+ry)/2;
    if(j<=mid){
        if(nodey->left==nullptr) nodey->left=new Node_y();
        update_y(node,lx,rx,nodey->left,ly,mid,i,j,x);
    }else{
        if(nodey->right==nullptr) nodey->right=new Node_y();
        update_y(node,lx,rx,nodey->right,mid+1,ry,i,j,x);
    }
    nodey->val=0;
    if(nodey->left==nullptr) nodey->val=nodey->val;
    else nodey->val=op(nodey->val,nodey->left->val);
    if(nodey->right==nullptr) nodey->val=nodey->val;
    else nodey->val=op(nodey->val,nodey->right->val);
}
void update_x(Node_x* node,int l,int r,int i,int j,ll x){
    if(l!=r){
        int mid=(l+r)/2;
        if(i<=mid){
            if(node->left==nullptr) node->left=new Node_x();
            update_x(node->left,l,mid,i,j,x);
        }else{
            if(node->right==nullptr) node->right=new Node_x();
            update_x(node->right,mid+1,r,i,j,x);
        }
    }
    if(node->node==nullptr){
        node->node=new Node_y();
    }
    update_y(node,l,r,node->node,0,m-1,i,j,x);
}
ll ans=0;
ll query_y(Node_y* node,int l,int r,int x1,int y1,int x2,int y2){
    if(y1<=l&&r<=y2) return node->val;
    int mid=(l+r)/2;
    if(y1<=mid){
        if(node->left==nullptr) ans=ans;
        else ans=op(ans,query_y(node->left,l,mid,x1,y1,x2,y2));
    }
    if(y2>mid){
        if(node->right==nullptr) ans=ans;
        else ans=op(ans,query_y(node->right,mid+1,r,x1,y1,x2,y2));
    }
    return ans;
}
ll query_x(Node_x* node,int l,int r,int x1,int y1,int x2,int y2){
    if(x1<=l&&r<=x2){
        if(node->node==nullptr) return 0LL;
        return query_y(node->node,0,m-1,x1,y1,x2,y2);
    }
    int mid=(l+r)/2;
    if(x1<=mid){
        if(node->left==nullptr) ans=ans;
        else ans=op(ans,query_x(node->left,l,mid,x1,y1,x2,y2));
    }
    if(x2>mid){
        if(node->right==nullptr) ans=ans;
        else ans=op(ans,query_x(node->right,mid+1,r,x1,y1,x2,y2));
    }
    return ans;
}
void init(int R, int C) {
    n=R;
    m=C;
    root=new Node_x();
}

void update(int P, int Q, long long K) {
    update_x(root,0,n-1,P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
    ans=0;
    return query_x(root,0,n-1,P,Q,U,V);
}




#ifdef IOI
#include <stdio.h>
#include <stdlib.h>
#include "game.h"

#define fail(s, x...) do { \
        fprintf(stderr, s "\n", ## x); \
        exit(1); \
    } while(0)

#define MAX_SIZE 1000000000
#define MAX_N 272000

int main() {
    int R, C, N;
    int P, Q, U, V;
    long long K;
    int i, type;
    int res;

    FILE *f = fopen("game.in", "r");
    if (!f)
        fail("Failed to open input file.");

    res = fscanf(f, "%d", &R);
    res = fscanf(f, "%d", &C);
    res = fscanf(f, "%d", &N);

    init(R, C);

    for (i = 0; i < N; i++) {
        res = fscanf(f, "%d", &type);
        if (type == 1) {
            res = fscanf(f, "%d%d%lld", &P, &Q, &K);
            update(P, Q, K);
        } else if (type == 2) {
            res = fscanf(f, "%d%d%d%d", &P, &Q, &U, &V);
            printf("%lld\n", calculate(P, Q, U, V));
        } else
            fail("Invalid action type in input file.");
    }
    fclose(f);

    return 0;
}

#endif

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