Submission #747238

#	Time	Username	Problem	Language	Result	Execution time	Memory
747238		nicksms	Game (IOI13_game)	C++17	100 / 100	4032 ms	165876 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())

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;
}

int inf = 1e9+20;

struct treap {
    vi l,r,p;
    V<pi> x;
    vl c,g;
    int root=0;
    treap() : l(1),r(1),x(1),p(1),c(1),g(1) {}
    void upd(int v) {
        g[v] = c[v];
        g[v] = gcd(g[v],g[l[v]]);
        g[v] = gcd(g[v],g[r[v]]);
    }
    void split(int v, int &wl, int &wr, pi X) {
        if (!v) {
            wl=wr=0;
            return;
        }
        if (x[v] <= X) {
            split(r[v],r[v],wr,X);
            wl=v;
        } else {
            split(l[v],wl,l[v],X);
            wr=v;
        }
        upd(v);
    }
    void merge(int il, int ir, int &i) {
        if (!il || !ir) {
            i = (il ? il : ir);
            return;
        }
        if (p[il] < p[ir]) {
            merge(il,l[ir],l[ir]);
            i=ir;
        } else {
            merge(r[il],ir,r[il]);
            i=il;
        }
        upd(i);
    }
    void op(pi X, ll val) {
        int lp=0,rp=0;
        split(root,root,rp,X);
        split(root,lp,root,{X.f,X.s-1});
        if (!root) {
            root = sz(l);
            l.push_back(0);
            r.push_back(0);
            p.push_back(rand());
            x.push_back(X);
            c.push_back(val);
            g.push_back(val);
        }
        c[root]=g[root]=val;
        merge(lp,root,root);
        merge(root,rp,root);
    }
    ll q(int xl, int xr) {
        int lp=0,rp=0;
        split(root,root,rp,{xr,inf});
        split(root,lp,root,{xl,-inf});
        ll ret = g[root];
        merge(lp,root,root);
        merge(root,rp,root);
        return ret;
    }
};

struct sstot {
    sstot *l=NULL, *r=NULL;
    int s,e;
    treap t;
    void op(pi X, ll val) {
        t.op(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 t.q(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({P,Q},K);
}

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

Compilation message (stderr)

game.cpp: In constructor 'treap::treap()':
game.cpp:34:11: warning: 'treap::x' will be initialized after [-Wreorder]
   34 |     V<pi> x;
      |           ^
game.cpp:33:12: warning:   'vi treap::p' [-Wreorder]
   33 |     vi l,r,p;
      |            ^
game.cpp:37:5: warning:   when initialized here [-Wreorder]
   37 |     treap() : l(1),r(1),x(1),p(1),c(1),g(1) {}
      |     ^~~~~
game.cpp: In member function 'll sstot::q(int, int, int, int)':
game.cpp:123:13: warning: unused variable 'm' [-Wunused-variable]
  123 |         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