Submission #847558

#	Time	Username	Problem	Language	Result	Execution time	Memory
847558		YassirSalama	Game (IOI13_game)	C++17	27 / 100	514 ms	70264 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;}
const int MAXN=2100;
ll tree[4*11][4*(int)1e5];
int n,m;
ll op(ll a,ll b){
    return gcd2(a,b);
}
void build_y(int nodex,int lx,int rx,int nodey,int ly,int ry){
    if(ly==ry){
        if(lx==rx){
            tree[nodex][nodey]=0;
        }else{
            tree[nodex][nodey]=op(tree[nodex<<1][nodey],tree[nodex<<1|1][nodey]);
        }
        return;
    }
    int mid=(ly+ry)/2;
    build_y(nodex,lx,rx,nodey<<1,ly,mid);
    build_y(nodex,lx,rx,nodey<<1|1,mid+1,ry);
    tree[nodex][nodey]=op(tree[nodex][nodey<<1],tree[nodex][nodey<<1|1]);
}
void build_x(int node,int l,int r){
    if(l==r){
        build_y(node,l,r,1,0,m-1);
    }else{
        int mid=(l+r)/2;
        build_x(node<<1,l,mid);
        build_x(node<<1|1,mid+1,r);
        build_y(node,l,r,1,0,m-1);
    }
}
void update_y(int nodex,int lx,int rx,int nodey,int ly,int ry,int i,int j,ll x){
    if(ly==ry){
        if(lx==rx){
            tree[nodex][nodey]=x;
        }else{
            tree[nodex][nodey]=op(tree[nodex<<1][nodey],tree[nodex<<1|1][nodey]);
        }
        return;
    }
    int mid=(ly+ry)/2;
    if(j<=mid){
        update_y(nodex,lx,rx,nodey<<1,ly,mid,i,j,x);
    }else{
        update_y(nodex,lx,rx,nodey<<1|1,mid+1,ry,i,j,x);
    }
    tree[nodex][nodey]=op(tree[nodex][nodey<<1],tree[nodex][nodey<<1|1]);
}
void update_x(int node,int l,int r,int i,int j,ll x){
    if(l!=r){
        int mid=(l+r)/2;
        if(i<=mid){
            update_x(node<<1,l,mid,i,j,x);
        }else{
            update_x(node<<1|1,mid+1,r,i,j,x);
        }
    }
    update_y(node,l,r,1,0,m-1,i,j,x);
}
ll query_y(int nodex,int lx,int rx,int nodey,int ly,int ry,int x1,int y1,int x2,int y2){
    if(y1<=ly&&ry<=y2){
        // dbg(x1,y1,x2,y2,lx,rx,ly,ry,tree[nodex][nodey]);
        return tree[nodex][nodey];
    }
    int mid=(ly+ry)/2;
    ll ans=0;
    if(y1<=mid){
        ans=op(ans,query_y(nodex,lx,rx,nodey<<1,ly,mid,x1,y1,x2,y2));
    }
    if(y2>mid){
        ans=op(ans,query_y(nodex,lx,rx,nodey<<1|1,mid+1,ry,x1,y1,x2,y2));
    }
    return ans;
}
ll query_x(int node,int l,int r,int x1,int y1,int x2,int y2){
    if(x1<=l&&r<=x2) {
        // dbg(x1,y1,x2,y2,l,r);        
        return query_y(node,l,r,1,0,m-1,x1,y1,x2,y2);
    }
    int mid=(l+r)/2;
    ll ans=0;
    if(x1<=mid) 
        ans=op(ans,query_x(node<<1,l,mid,x1,y1,x2,y2));
    if(x2>mid)
        ans=op(ans,query_x(node<<1|1,mid+1,r,x1,y1,x2,y2));
    return ans; 
}
void init(int R, int C) {
    /* ... */
    n=R;
    m=C;
    build_x(1,0,n-1);
}

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

long long calculate(int P, int Q, int U, int V) {
    /* ... */
    // return 1;
    // dbg(P,Q,U,V);
    // for(int i=P;i<=U;i++){
        // for(int j=Q;j<=V;j++){
            // int x=query_x(1,0,n-1,P,Q,U,V);
            // dbg(i,j,x);
        // }
    // }
    return query_x(1,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: 0 / 10
• Subtask 2: 27 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20