Submission #264077

#	Time	Username	Problem	Language	Result	Execution time	Memory
264077		anonymous	Game (IOI13_game)	C++14	100 / 100	8000 ms	43364 KiB

game

#include <iostream>
#include <utility>
#include "game.h"
#define LL long long
#define MAXN 22005
using namespace std;
LL gcd(LL X, LL Y) {
    LL tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
 
//begin treap
struct Node {
    LL GCD, val; //gcd of subtree
    int c, pri, l, r; //column, priority, children
};
 
class TreapForest {
public:
    Node trp[MAXN * 125];
    int ptr = 1;
    void pushup(int t) {
        trp[t].GCD = gcd(gcd(trp[trp[t].l].GCD, trp[trp[t].r].GCD), trp[t].val);
    }
 
    int addnode(LL v, int c) { //can also be used to make new treap in forest
        trp[ptr].val = trp[ptr].GCD = v;
        trp[ptr].pri = rand();
        trp[ptr].c = c;
        return(ptr++); //return node index
    }
 
    void Split(int t, int &l, int &r, int val) {
        //split subtree t so c <= val to l, c > val to r
        if (!t) {
            l = r = 0;
            return;
        } else if (trp[t].c > val) {
            Split(trp[t].l, l, trp[t].l, val);
            r = t;
        } else {
            Split(trp[t].r, trp[t].r, r, val);
            l = t;
        }
        pushup(t);
    }
 
    void Merge(int &t, int l, int r) {
        //maxC(l) <= maxC(r)
        //combine subtrees l, r into pointer t
        if (!l || !r) {
            t = max(l, r);
            return;
        } else if (trp[l].pri < trp[r].pri) { //bigger pri on top
            Merge(trp[r].l, l, trp[r].l);
            t = r;
        } else {
            Merge(trp[l].r, trp[l].r, r);
            t = l;
        }
        pushup(t);
    }
 
    int Insert(int rt, LL val, int c) {
        int NewNode = addnode(val, c); //assume rt does not already have key c
        int l, r;
        Split(rt, l, r, c);
        Merge(l, l, NewNode);
        Merge(r, l, r);
        return(r); //new root
    }
 
    int Del(int rt, int c) { //Delete if exists
        int l, r, trash;
        Split(rt, l, r, c);
        Split(l, l, trash, c-1);
        Merge(r, l, r);
        return(r);
    }
 
    pair <LL,int> Ask(int rt, int lo, int hi) { //range query
        int l, mid, r;
        LL res;
        Split(rt, l, mid, lo-1);
        Split(mid, mid, r, hi);
        res = trp[mid].GCD;
        Merge(mid, mid, r);
        Merge(l, l, mid);
        return(pair <LL,int> {res, l});
    }
} Treap;
 
//end treap begin segtree
 
class LazyCreate {
    int ST[MAXN * 125]; //store treap root, order by rows
    int L[MAXN * 125], R[MAXN * 125], ptr = 2;
 
public:
    void addnode(int par) {
        L[par] = ptr++;
        R[par] = ptr++;
    }
 
    void modify(int cur, LL val, int c) {
        if (!ST[cur]) {
            ST[cur] = Treap.addnode(val, c);
        } else {
            ST[cur] = Treap.Del(ST[cur], c);
            ST[cur] = Treap.Insert(ST[cur], val, c);
        }
    }
 
    LL upd(int r, int c, LL val, int Rl, int Rr, int cur) {
        if (r < Rl || r > Rr) {
            pair <LL,int> ret = Treap.Ask(ST[cur],c,c);
            ST[cur] = ret.second;
            return(ret.first);
        } else if (Rl == Rr) {
            modify(cur, val, c);
            return(val);
        } else {
            if (!L[cur]) {addnode(cur);}
            int mid = (Rl + Rr) >> 1;
            LL a = upd(r, c, val, Rl, mid, L[cur]);
            LL b = gcd(a, upd(r, c, val, mid+1, Rr, R[cur]));
            modify(cur, b, c);
            return(b);
        }
    }
 
    LL ask(int Lr, int Hr, int Lc, int Hc, int Rl, int Rr, int cur) {
        if (Hr < Rl || Lr > Rr || !cur) {return(0);}
        else if (Lr <= Rl && Hr >= Rr) {
            pair <LL,int> ret = Treap.Ask(ST[cur],Lc, Hc);
            ST[cur] = ret.second;
            return(ret.first);
        } else {
            int mid = (Rl + Rr) >> 1;
            return(gcd( ask(Lr, Hr, Lc, Hc, Rl, mid, L[cur]),
                        ask(Lr, Hr, Lc, Hc, mid+1, Rr, R[cur])));
        }
    }
} ST;
 
int R,C;
void init(int r, int c) {
    R = r, C = c;
}
 
void update(int P, int Q, long long K) {
    ST.upd(P,Q,K, 0, R-1, 1);
}
 
long long calculate(int P, int Q, int U, int V) {
    return(ST.ask(P,U,Q,V,0, R-1, 1));
}

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   18 |  int res;
      |      ^~~

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