Submission #1227808

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227808		Samuraj	Game (IOI13_game)	C++20	63 / 100	2032 ms	321536 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 node{
    node* l = nullptr;
    node* r = nullptr;
    node* tree = nullptr;
    ll val = 0;
};

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

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

ll qy(node* 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(node* 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(node* 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";

    if(!v->l) v->l = new node(); if(!v->r) v->r = new node();
    int mid = (a+b)/2;
    //cout << "stworzone new nodes\n";
    uy(v->l,a,mid); uy(v->r,mid+1,b);
    //teraz update naszego
    v->val = gcd2(v->l->val,v->r->val);
}

void ux(node* 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 node();
        uy(v->tree,0,base-1);
        return;
    }
    //tutaj rownoczesnie tx->tree, tx->l->tree, tx->r->tree
    if(!v->l) v->l = new node(); if(!v->r) v->r = new node();
    int mid = (a+b)/2;
    ux(v->l,a,mid); ux(v->r,mid+1,b);

    if(!v->tree) v->tree = new node();
    ll val1 = qy(v->l->tree,0,base-1); ll val2 = qy(v->r->tree,0,base-1);
    up_val = gcd2(val1,val2);

    uy(v->tree,0,base-1);
}


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

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