oj.uz

Submission #747299

# Submission time Handle Problem Language Result Execution time Memory
747299 2023-05-24T04:47:27 Z nicksms Game (IOI13_game) C++17
100 / 100
 3910 ms 90344 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())

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

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.0 / 10.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 3 ms 468 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 2 ms 340 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 1 ms 308 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 877 ms 27908 KB Output is correct
5 Correct 650 ms 27804 KB Output is correct
6 Correct 1231 ms 25116 KB Output is correct
7 Correct 1164 ms 25028 KB Output is correct
8 Correct 630 ms 15308 KB Output is correct
9 Correct 1182 ms 24956 KB Output is correct
10 Correct 1077 ms 24708 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 212 KB Output is correct
2 Correct 3 ms 436 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 308 KB Output is correct
6 Correct 3 ms 436 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 308 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 1020 ms 27844 KB Output is correct
13 Correct 1742 ms 19052 KB Output is correct
14 Correct 553 ms 6092 KB Output is correct
15 Correct 1846 ms 19944 KB Output is correct
16 Correct 807 ms 24884 KB Output is correct
17 Correct 1012 ms 16000 KB Output is correct
18 Correct 2252 ms 26276 KB Output is correct
19 Correct 2055 ms 26420 KB Output is correct
20 Correct 1917 ms 25832 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 212 KB Output is correct
2 Correct 3 ms 436 KB Output is correct
3 Correct 4 ms 440 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 3 ms 436 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 440 KB Output is correct
10 Correct 1 ms 308 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 1062 ms 27944 KB Output is correct
13 Correct 711 ms 27684 KB Output is correct
14 Correct 1296 ms 25156 KB Output is correct
15 Correct 1280 ms 24976 KB Output is correct
16 Correct 651 ms 15344 KB Output is correct
17 Correct 1335 ms 24960 KB Output is correct
18 Correct 1121 ms 24548 KB Output is correct
19 Correct 1012 ms 27892 KB Output is correct
20 Correct 1836 ms 18896 KB Output is correct
21 Correct 636 ms 6140 KB Output is correct
22 Correct 1873 ms 19944 KB Output is correct
23 Correct 778 ms 24888 KB Output is correct
24 Correct 996 ms 16048 KB Output is correct
25 Correct 2263 ms 26364 KB Output is correct
26 Correct 1897 ms 26412 KB Output is correct
27 Correct 1698 ms 25904 KB Output is correct
28 Correct 595 ms 44244 KB Output is correct
29 Correct 1280 ms 47324 KB Output is correct
30 Correct 2480 ms 36288 KB Output is correct
31 Correct 2251 ms 29512 KB Output is correct
32 Correct 602 ms 8880 KB Output is correct
33 Correct 741 ms 9732 KB Output is correct
34 Correct 787 ms 43812 KB Output is correct
35 Correct 936 ms 27212 KB Output is correct
36 Correct 1994 ms 44940 KB Output is correct
37 Correct 1868 ms 44876 KB Output is correct
38 Correct 1821 ms 44352 KB Output is correct
39 Correct 1266 ms 36648 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 3 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 4 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 2 ms 308 KB Output is correct
11 Correct 2 ms 340 KB Output is correct
12 Correct 885 ms 27916 KB Output is correct
13 Correct 702 ms 27664 KB Output is correct
14 Correct 1371 ms 25184 KB Output is correct
15 Correct 1185 ms 24868 KB Output is correct
16 Correct 666 ms 15360 KB Output is correct
17 Correct 1229 ms 25012 KB Output is correct
18 Correct 1335 ms 24668 KB Output is correct
19 Correct 1053 ms 27816 KB Output is correct
20 Correct 1884 ms 18992 KB Output is correct
21 Correct 590 ms 6188 KB Output is correct
22 Correct 1863 ms 19872 KB Output is correct
23 Correct 776 ms 24952 KB Output is correct
24 Correct 1029 ms 15932 KB Output is correct
25 Correct 2260 ms 26324 KB Output is correct
26 Correct 1932 ms 26492 KB Output is correct
27 Correct 1860 ms 26028 KB Output is correct
28 Correct 677 ms 44252 KB Output is correct
29 Correct 1311 ms 47328 KB Output is correct
30 Correct 2452 ms 36264 KB Output is correct
31 Correct 2228 ms 29524 KB Output is correct
32 Correct 603 ms 10696 KB Output is correct
33 Correct 781 ms 11492 KB Output is correct
34 Correct 777 ms 43920 KB Output is correct
35 Correct 938 ms 29720 KB Output is correct
36 Correct 1903 ms 48084 KB Output is correct
37 Correct 1588 ms 48288 KB Output is correct
38 Correct 1515 ms 47636 KB Output is correct
39 Correct 793 ms 88368 KB Output is correct
40 Correct 2093 ms 90344 KB Output is correct
41 Correct 3910 ms 69656 KB Output is correct
42 Correct 3353 ms 54600 KB Output is correct
43 Correct 1257 ms 85372 KB Output is correct
44 Correct 1002 ms 12256 KB Output is correct
45 Correct 1229 ms 39388 KB Output is correct
46 Correct 2636 ms 89152 KB Output is correct
47 Correct 2650 ms 89232 KB Output is correct
48 Correct 2690 ms 88896 KB Output is correct
49 Correct 0 ms 212 KB Output is correct