Submission #747299

#	Time	Username	Problem	Language	Result	Execution time	Memory
747299		nicksms	Game (IOI13_game)	C++17	100 / 100	3910 ms	90344 KiB

game

#include "game.h"

/**
 *      Author:  Nicholas Winschel
 *      Created: 05.23.2023 20:57:47
**/

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using db=long double;
template<class T> using V=vector<T>;
using vi = V<int>;
using vl = V<ll>;
using pi = pair<int,int>;
#define f first
#define s second
#define sz(x) (int)((x).size())

static char buf[200 << 20];
void* operator new(size_t s) {
	static size_t i = sizeof buf; assert(s < i);
	return (void*)&buf[i -= s];
}
void operator delete(void*) {}

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 inf = 1e9+20;

struct lt {
    lt *l=NULL, *r=NULL;
    int p;
    pi x;
    ll c,g;
    ll sx,ex;
    lt () : p (rand()), x(-1,-1), c(0),g(0), sx(-1),ex(-1) {}
    void upd() {
        g = gcd(c,gcd(l ? l->g : 0, r ? r->g : 0));
        sx=ex=x.f;
        if (l) sx = l->sx;
        if (r) ex = r->ex;
    }
    friend void split(lt *t, lt *&wl, lt *&wr, const pi &X) {
        if (!t) {
            wl=wr=NULL;
            return;
        }
        if (t->x <= X) {
            split(t->r,t->r,wr,X);
            wl=t;
        } else {
            split(t->l,wl,t->l,X);
            wr=t;
        }
        t->upd();
    }
    friend void merge(lt *tl, lt *tr, lt *&i) {
        // cerr << "test4" << " " << tl << " " << tr << endl;
        assert(tl != tr);
        if (!tl || !tr) {
            i = (tl ? tl : tr);
            return;
        }
        if (tl->p < tr->p) {
            merge(tl,tr->l,tr->l);
            i=tr;
        } else {
            merge(tl->r,tr,tl->r);
            i=tl;
        }
        i->upd();
    }
    static void op(lt *&root, const pi &X, ll val) {
        // cerr << "test" << endl;
        lt *lp=NULL,*rp=NULL;
        split(root,root,rp,X);
        split(root,lp,root,{X.f,X.s-1});
        if (!root) {
            root = new lt;
            root->x=X;
            root->upd();
        }
        root->g=root->c=val;
        // cerr << "test3" << endl;
        merge(lp,root,root);
        merge(root,rp,root);
    }
    static ll q(lt *root, int xl, int xr) { // benq speedup -- no rewrite
        if (!root) return 0;
        if (root->ex < xl || root->sx > xr) return 0;
        if (xl <= root->sx && root->ex <= xr) return root->g;
        ll val = (root->x.f >= xl && root->x.f <= xr ? root->c : 0);
        if (root->l) val=gcd(val,q(root->l,xl,xr));
        if (root->r) val=gcd(val,q(root->r,xl,xr));
        return val;
    }
};

struct sstot {
    sstot *l=NULL, *r=NULL;
    int s,e;
    lt *t;
    sstot () {
        t=new lt;
    }
    void op(const pi &X, ll val) {
        // cerr << "test2 " << X.f << " " << X.s << " " << val << endl;
        lt::op(t,X,val);
        if (e-s <= 1) return;
        int y = X.s;
        int m = (s+e)>>1;
        if (y < m) {
            if (!l) l = new sstot;
            l->s=s;
            l->e=m;
            l->op(X,val);
        } else {
            if (!r) r = new sstot;
            r->s=m;
            r->e=e;
            r->op(X,val);
        }
    }
    ll q(int xl, int xr, int yl, int yr) {
        if (yl >= e || yr < s) return 0;
        if (yl <= s && yr >= e-1) return lt::q(t,xl,xr);
        int m = (s+e)>>1;
        return gcd((l ? l->q(xl,xr,yl,yr) : 0), (r ? r->q(xl,xr,yl,yr) : 0));
    }
    // ll q(int xl, int xr, int yl, int yr) {
    //     ll ans = _q(xl,xr,yl,yr);
    //     cerr << "dbg: y=[" << s << "," << e << "): " << "\n     q=[" << xl << "," << xr << "]*["
    //         << yl << "," << yr << "]\n     ans=" << ans << "\n";
    //     return ans;
    // }
};

sstot root;

void init(int R, int C) {
    root=sstot();
    root.s=0;
    root.e=inf;
}

void update(int P, int Q, long long K) {
   root.op({Q,P},K);
}

long long calculate(int P, int Q, int U, int V) {
    return root.q(min(Q,V),max(Q,V),min(P,U),max(P,U));
}

Compilation message (stderr)

game.cpp: In member function 'll sstot::q(int, int, int, int)':
game.cpp:136:13: warning: unused variable 'm' [-Wunused-variable]
  136 |         int m = (s+e)>>1;
      |             ^

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