oj.uz

Submission #747284

# Submission time Handle Problem Language Result Execution time Memory
747284 2023-05-24T03:45:55 Z nicksms Game (IOI13_game) C++17
100 / 100
 7362 ms 96052 KB 
#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;
}

const int inf = 1e9+20;

struct lt {
    lt *l=NULL, *r=NULL;
    int p;
    pi x;
    ll c,g;
    lt () : p (rand()), x(-1,-1), c(0),g(0) {}
    void upd() {
        g = gcd(c,gcd(l ? l->g : 0, r ? r->g : 0));
    }
    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->g=root->c=val;
        // cerr << "test3" << endl;
        merge(lp,root,root);
        merge(root,rp,root);
    }
    static ll q(lt *&root, int xl, int xr) {
        lt *lp=NULL,*rp=NULL;
        split(root,root,rp,{xr, inf});
        split(root,lp,root,{xl,-inf});
        ll ret=0; if (root) ret=root->g;
        merge(lp,root,root);
        merge(root,rp,root);
        return ret;       
    }
};

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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 220 KB Output is correct
6 Correct 3 ms 428 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 5 ms 424 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 1 ms 212 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1244 ms 27956 KB Output is correct
5 Correct 761 ms 27740 KB Output is correct
6 Correct 1845 ms 25136 KB Output is correct
7 Correct 1900 ms 24924 KB Output is correct
8 Correct 1151 ms 15328 KB Output is correct
9 Correct 2005 ms 25104 KB Output is correct
10 Correct 1629 ms 24568 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 6 ms 432 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 6 ms 468 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 2 ms 212 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 2 ms 296 KB Output is correct
11 Correct 2 ms 308 KB Output is correct
12 Correct 1782 ms 27892 KB Output is correct
13 Correct 3264 ms 19020 KB Output is correct
14 Correct 799 ms 6132 KB Output is correct
15 Correct 3582 ms 20000 KB Output is correct
16 Correct 1327 ms 25008 KB Output is correct
17 Correct 2456 ms 16020 KB Output is correct
18 Correct 4879 ms 26448 KB Output is correct
19 Correct 3930 ms 26560 KB Output is correct
20 Correct 3614 ms 25968 KB Output is correct
21 Correct 1 ms 212 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 4 ms 428 KB Output is correct
3 Correct 4 ms 468 KB Output is correct
4 Correct 1 ms 304 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 4 ms 468 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 1301 ms 27832 KB Output is correct
13 Correct 862 ms 27492 KB Output is correct
14 Correct 1859 ms 25108 KB Output is correct
15 Correct 1852 ms 24920 KB Output is correct
16 Correct 1089 ms 15384 KB Output is correct
17 Correct 1936 ms 25160 KB Output is correct
18 Correct 1641 ms 24540 KB Output is correct
19 Correct 1537 ms 27856 KB Output is correct
20 Correct 3150 ms 18928 KB Output is correct
21 Correct 761 ms 6200 KB Output is correct
22 Correct 3394 ms 19984 KB Output is correct
23 Correct 1100 ms 25036 KB Output is correct
24 Correct 2075 ms 16212 KB Output is correct
25 Correct 3769 ms 26652 KB Output is correct
26 Correct 3183 ms 26568 KB Output is correct
27 Correct 2945 ms 25976 KB Output is correct
28 Correct 1229 ms 50376 KB Output is correct
29 Correct 1979 ms 52832 KB Output is correct
30 Correct 4682 ms 38072 KB Output is correct
31 Correct 4285 ms 30644 KB Output is correct
32 Correct 780 ms 10824 KB Output is correct
33 Correct 1161 ms 11712 KB Output is correct
34 Correct 1763 ms 46632 KB Output is correct
35 Correct 2013 ms 31156 KB Output is correct
36 Correct 3855 ms 50740 KB Output is correct
37 Correct 3026 ms 50920 KB Output is correct
38 Correct 2872 ms 50384 KB Output is correct
39 Correct 2537 ms 41720 KB Output is correct
40 Correct 1 ms 212 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 4 ms 428 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 3 ms 432 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 1129 ms 27916 KB Output is correct
13 Correct 754 ms 27764 KB Output is correct
14 Correct 1668 ms 25176 KB Output is correct
15 Correct 1852 ms 25000 KB Output is correct
16 Correct 1060 ms 15468 KB Output is correct
17 Correct 1825 ms 24964 KB Output is correct
18 Correct 1590 ms 24636 KB Output is correct
19 Correct 1436 ms 27944 KB Output is correct
20 Correct 3118 ms 19016 KB Output is correct
21 Correct 810 ms 6096 KB Output is correct
22 Correct 3507 ms 19992 KB Output is correct
23 Correct 1120 ms 25004 KB Output is correct
24 Correct 2021 ms 16080 KB Output is correct
25 Correct 3723 ms 26436 KB Output is correct
26 Correct 3151 ms 26548 KB Output is correct
27 Correct 3185 ms 26032 KB Output is correct
28 Correct 1191 ms 50124 KB Output is correct
29 Correct 1902 ms 52848 KB Output is correct
30 Correct 4596 ms 37808 KB Output is correct
31 Correct 4198 ms 30656 KB Output is correct
32 Correct 768 ms 10828 KB Output is correct
33 Correct 1156 ms 11444 KB Output is correct
34 Correct 1742 ms 46512 KB Output is correct
35 Correct 2011 ms 31092 KB Output is correct
36 Correct 3804 ms 50744 KB Output is correct
37 Correct 3075 ms 50924 KB Output is correct
38 Correct 2844 ms 50252 KB Output is correct
39 Correct 1572 ms 94140 KB Output is correct
40 Correct 3014 ms 96052 KB Output is correct
41 Correct 7362 ms 72852 KB Output is correct
42 Correct 6262 ms 56816 KB Output is correct
43 Correct 2052 ms 90844 KB Output is correct
44 Correct 1299 ms 12124 KB Output is correct
45 Correct 2556 ms 41640 KB Output is correct
46 Correct 4890 ms 94932 KB Output is correct
47 Correct 4662 ms 94884 KB Output is correct
48 Correct 4395 ms 94560 KB Output is correct
49 Correct 0 ms 212 KB Output is correct