제출 #847890

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
847890		YassirSalama	게임 (IOI13_game)	C++17	63 / 100	1271 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()
ll gcd2(ll a, ll b) {
    while (b != 0) {
        a = a % b;
        swap(a, b);
    }
    return a;
}
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(nullptr),left(nullptr),right(nullptr) {}
};
Node_x* root;
int n,m;
#define gcd2(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);
    }
}
int i;int j;ll x;
void update_y(Node_x* node,int lx,int rx,Node_y* nodey,int ly,int ry){
    if(nodey==nullptr) nodey=new Node_y();
    if(ly==ry){
        if(lx==rx){
            nodey->val=x;
        }else{
            nodey->val=0;
            if(node->left==nullptr)
                nodey->val=nodey->val;
            else nodey->val=gcd2(nodey->val,get(node->left->node,0,m-1,ly));
            if(node->right==nullptr)
                nodey->val=nodey->val;
            else nodey->val=gcd2(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);
    }else{
        if(nodey->right==nullptr) nodey->right=new Node_y();
        update_y(node,lx,rx,nodey->right,mid+1,ry);
    }
    nodey->val=0;
    if(nodey->left==nullptr) nodey->val=nodey->val;
    else nodey->val=gcd2(nodey->val,nodey->left->val);
    if(nodey->right==nullptr) nodey->val=nodey->val;
    else nodey->val=gcd2(nodey->val,nodey->right->val);
}
void update_x(Node_x* node,int l,int r){
    if(node==nullptr) node=new Node_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);
        }else{
            if(node->right==nullptr) node->right=new Node_x();
            update_x(node->right,mid+1,r);
        }
    }
    if(node->node==nullptr){
        node->node=new Node_y();
    }
    update_y(node,l,r,node->node,0,m-1);
}
ll ans=0;
int x1;int Y1;int x2;int y2;
//iterative sparse segment tree
void queryy(Node_y* node,int l,int r){
    stack<pair<Node_y*,pair<int,int>>> st;
    st.push({node,{l,r}});
    while(!st.empty()){
        Node_y* nodey=st.top().F;
        int lll=st.top().S.F;
        int rrr=st.top().S.S;
        st.pop();
        if(Y1<=lll&&rrr<=y2){
            ans=gcd2(ans,nodey->val);
            continue;
        }
        int mid=(lll+rrr)/2;
        if(Y1<=mid){
            if(nodey->left!=nullptr) {
                st.push({nodey->left,{lll,mid}});
            }
        }
        if(y2>mid){
            if(nodey->right!=nullptr){
                st.push({nodey->right,{mid+1,rrr}});
            }
        }
    }
}
void queryx(Node_x* node,int l,int r){
    stack<pair<Node_x*,pair<int,int>>> st;
    st.push({node,{l,r}});
    while(!st.empty()){
        Node_x* nodex=st.top().F;
        int lll=st.top().S.F;
        int rrr=st.top().S.S;
        st.pop();
        if(x1<=lll&&rrr<=x2){
            if(nodex->node==nullptr) continue;
            queryy(nodex->node,0,m-1);
            continue;
        }
        int mid=(lll+rrr)/2;
        if(x1<=mid){
            if(nodex->left!=nullptr)
                st.push({nodex->left,{lll,mid}}); 
        }
        if(x1>mid){
            if(nodex->right!=nullptr)
                st.push({nodex->right,{mid+1,rrr}});
        }
    }
}
ll query_y(Node_y* node,int l,int r){
    if(Y1<=l&&r<=y2) return node->val;
    int mid=(l+r)/2;
    if(Y1<=mid){
        if(node->left==nullptr) ans=ans;
        else ans=gcd2(ans,query_y(node->left,l,mid));
    }
    if(y2>mid){
        if(node->right==nullptr) ans=ans;
        else ans=gcd2(ans,query_y(node->right,mid+1,r));
    }
    return ans;
}
ll query_x(Node_x* node,int l,int r){
    if(x1<=l&&r<=x2){
        if(node->node==nullptr) return 0LL;
        return query_y(node->node,0,m-1);
    }
    int mid=(l+r)/2;
    if(x1<=mid){
        if(node->left==nullptr) ans=ans;
        else ans=gcd2(ans,query_x(node->left,l,mid));
    }
    if(x2>mid){
        if(node->right==nullptr) ans=ans;
        else ans=gcd2(ans,query_x(node->right,mid+1,r));
    }
    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) {
    i=P;
    j=Q;
    x=K;
    update_x(root,0,n-1);
}

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




#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