제출 #1227828

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1227828		Samuraj	Game (IOI13_game)	C++20	63 / 100	1840 ms	279632 KiB

game

#include "game.h"
#include <bits/stdc++.h>

using namespace std;

#define st first
#define nd second
#define pb push_back
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define irep(i,a,b) for(int i = a; i >= b; i--)
typedef long long ll;
typedef long double ld;
//typedef __int128 int128;
typedef vector<int> vi;
typedef pair<int,int> pi; 
typedef pair<double,double> pd;
typedef pair<ll,ll> pl;

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 n2{
    n2* l = nullptr;
    n2* r = nullptr;
    ll val = 0;
};

struct n1{
    n1* l = nullptr;
    n1* r = nullptr;
    n2* tree = nullptr;
};

const int base = 1<<30;
n1* rootx;

int lx, rx, ly, ry; ll up_val;

ll qy(n2* v, int a, int b){
    if(!v) return 0;
    if(a > ry || b < ly) return 0;
    if(a >= ly && b <= ry) return v->val;
    
    //tu nie musze tworzyc!
    int mid = (a+b)/2;
    return gcd2(qy(v->l,a,mid),qy(v->r,mid+1,b));
}

ll qx(n1* v, int a, int b){
    //cout << "qx, a: " << a << " b: " << b << '\n';
    if(!v) return 0;
    if(a > rx || b < lx) return 0;
    if(a >= lx && b <= rx) return qy(v->tree,0,base-1);
    int mid = (a+b)/2;
    return gcd2(qx(v->l,a,mid),qx(v->r,mid+1,b));
}

void uy(n2* v, int a, int b){
    //t1 i t2 to pointery do tx->l i tx->r
    //cout << "uy, a: " << a << " b: " << b << '\n';
    if(a > ry || b < ry) return;
    if(a >= ly && b <= ry){
        v->val = up_val; //poczatkowy update
        return;
    }
    //cout << "ostatni case\n";

    int mid = (a+b)/2;
    if(ly <= mid){
        if(!v->l) v->l = new n2();
        uy(v->l,a,mid);
    }
    if(ry >= mid+1){
        if(!v->r) v->r = new n2();
        uy(v->r,mid+1,b);
    }
    //cout << "uy outer loop, a: " << a << " b: " << b << '\n'; 
    //cout << "v->l: " << v->l << " v->r: " << v->r << '\n';
    v->val = 0;
    if(v->l) v->val = gcd2(v->val,v->l->val);
    //cout << "v->l done\n";
    if(v->r) v->val = gcd2(v->val,v->r->val);
    //cout << "v->r done\n";
}

void ux(n1* v, int a, int b){
    //cout << "\nux, a: " << a << " b: " << b << '\n';
    if(a > rx || b < lx) return;
    if(a >= lx && b <= rx){
        if(!v->tree) v->tree = new n2();
        uy(v->tree,0,base-1);
        return;
    }
    //tutaj rownoczesnie tx->tree, tx->l->tree, tx->r->tree
    int mid = (a+b)/2;
    if(lx <= mid){
        if(!v->l) v->l = new n1();
        ux(v->l,a,mid);
    }
    if(rx >= mid+1){
        if(!v->r) v->r = new n1();
        ux(v->r,mid+1,b);
    }

    ll val1 = 0; ll val2 = 0;
    if(v->l) val1 = qy(v->l->tree,0,base-1);
    if(v->r) val2 = qy(v->r->tree,0,base-1);

    if(!v->tree) v->tree = new n2();
    up_val = gcd2(val1,val2);
    uy(v->tree,0,base-1);
}


void init(int R, int C){
    rootx = new n1();
}

void update(int P, int Q, ll K){
    //cout << "\n\nupdate, r: " << P << " c: " << Q << " K: " << K << '\n';
    lx = P; rx = P; ly = Q; ry = Q; up_val = K;
    ux(rootx,0,base-1);
}

long long calculate(int P, int Q, int U, int V){
    //cout << "\n\ncalculate, lx: " << P << " rx: " << U << " ly: " << Q << " ry: " << V << '\n';
    lx = P; rx = U;  ly = Q; ry = V;
    return qx(rootx,0,base-1);
}

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