oj.uz

답안 #1113707

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1113707 2024-11-17T07:54:12 Z Gray 게임 (IOI13_game) C++17
100 / 100
 5952 ms 107592 KB 
#include<bits/stdc++.h>
#include <random>
#include "game.h"
#define ll long long
#define ff first
#define ss second
#define ln "\n"
using namespace std;
mt19937 mt(time(nullptr));
struct Treap{
    struct Node{
        Node *left, *right;
        ll x, y, gcd, fgcd;
        Node(ll _x, ll _gcd){
            left=right=nullptr;
            x=_x; gcd=fgcd=_gcd;
            y=mt();
        }
        Node(ll _x, ll _y, ll _gcd){
            left=right=NULL;
            x=_x; y=_y; gcd=fgcd=_gcd;
        }
    };
    Node * root;
    Treap(){
        root=new Node(-1, 2e18, 0);
    }
    void upd(Node * t){
        if (!t) return;
        t->fgcd=t->gcd;
        if (t->left) t->fgcd=__gcd(t->left->fgcd, t->fgcd);
        if (t->right) t->fgcd=__gcd(t->right->fgcd, t->fgcd);
    }
    void split(Node *par, Node*&wl, Node*&wr, ll x){
        if (!par){
            wl=wr=nullptr;
        }else if (par->x<=x){
            split(par->right, par->right, wr, x); wl=par;
        }else{
            split(par->left, wl, par->left, x); wr=par;
        }
        upd(wl); upd(wr);
    }
    void merge(Node *& npar, Node *l, Node *r){
        if (!l or !r){
            npar=l?l:r;
        }else if (l->y>r->y){
            merge(l->right, l->right, r); npar=l;
        }else{
            merge(r->left, l, r->left); npar=r;
        }
        upd(npar);
    }
    void insert(Node *& cur, Node * item){
        if (!cur){
            cur=item;
        }else if (cur->y>=item->y){
            insert(cur->x<=item->x?cur->right:cur->left, item);
        }else{
            split(cur, item->left, item->right, item->x); cur=item;
        }
        upd(cur);
    }
    ll query_range(Node *& cur, ll l, ll r){
        Node * t1, * t2, * t3;
        split(cur, t1, t2, l-1);
        split(t2, t2, t3, r);
        ll res=t2?t2->fgcd:0;
        merge(cur, t1, t2);
        merge(cur, cur, t3);
        return res;
    }
    void update(Node * cur, ll x, ll newval){
        if (!cur){
            insert(root, new Node(x, newval));
            return;
        }else if (cur->x==x){
            cur->gcd=newval;
        }else if (cur->x<x){
            update(cur->right, x, newval);
        }else{
            update(cur->left, x, newval);
        }
        upd(cur);
    }
    void update(ll x, ll newval){
        update(root, x, newval);
    }
    void insert(ll x, ll val){
        insert(root, new Node(x, val));
    }
    ll query(ll l, ll r){
        return query_range(root, l, r);
    }
};

// struct SegTree1D{
// 	struct Node{
// 		ll left, right, val;
// 		Node(){
// 			left=right=-1;
// 			val=0;
// 		}
// 	};
// 	vector<Node> nodes;
// 	ll add_node(){
// 	    nodes.push_back(Node());
// 		return nodes.size()-1;
// 	}
// 	map<int, ll> leaves;
// 	int rsz;
// 	SegTree1D(int N){
// 		rsz=N;
// 		add_node();
// 	}
// 	void update(ll tl, ll tr, ll v, ll i, ll x){
// 	    if (tl==tr){
// 			nodes[v].val=x;
// 			leaves[tl]=v;
// 		}else{
// 		    ll tm = (tl+tr)/2;
// 			if (i<=tm){
// 			    if (nodes[v].left==-1) nodes[v].left=add_node();
// 				update(tl, tm, nodes[v].left, i, x);
// 			}else{
// 			    if (nodes[v].right==-1) nodes[v].right=add_node();
// 				update(tm+1, tr, nodes[v].right, i, x);
// 			}
// 			nodes[v].val=0;
// 			if (nodes[v].left!=-1) nodes[v].val=__gcd(nodes[nodes[v].left].val, nodes[v].val);
// 			if (nodes[v].right!=-1) nodes[v].val=__gcd(nodes[nodes[v].right].val, nodes[v].val);
// 		}
// 	}
// 	void update(ll i, ll x){
// 	   update(0, rsz-1, 0, i, x);
// 	}
// 	ll query(ll tl, ll tr, ll v, ll l, ll r){
// 	    if (tl==l and tr==r){
// 			return nodes[v].val;
// 		}
// 		else if (l>r) return 0;
// 		else{
// 		    ll tm = (tl+tr)/2;
// 			ll res=0;
// 			if (nodes[v].left!=-1) res=__gcd(res, query(tl, tm, nodes[v].left, l, min(r, tm)));
// 			if (nodes[v].right!=-1) res=__gcd(res, query(tm+1, tr, nodes[v].right, max(l, tm+1), r));
// 			return res;
// 		}
// 	}
// 	ll query(int l, int r){
// 		return query(0, rsz-1, 0, l, r);
// 	}
// 	ll getval(int ind){
// 		if (!leaves.count(ind)) return 0;
// 		return nodes[leaves[ind]].val;
// 	}
// };
struct SegTree2D{
	struct mNode{
		mNode *left, *right;
		Treap *val;
		int csz;
		mNode(int _csz){
			csz=_csz;
			left=right=nullptr;
			val = new Treap();
		}
		void update(int tl, int tr, int i, int j, ll x){
			if (tl==tr){
			    // cout << "Entered" << endl;
				val->update(j, x);
				// cout << "Exited"<< endl;
			}else{
				int tm = (tl+tr)/2;
				if (i<=tm){
					if (!left) left=new mNode(csz);
					left->update(tl, tm, i, j, x);
				}else{
					if (!right) right=new mNode(csz);
					right->update(tm+1, tr, i, j, x);
				}
				val->update(j, __gcd((left?left->val->query(j, j):0), (right?right->val->query(j, j):0)));
			}
		}
		ll query(int li, int ri, int lj, int rj, int tl, int tr){
			if (tl==li and tr==ri){
			    // cout << lj << "-" << rj << endl;
				ll res= val->query(lj, rj);
				// cout << "Success" << endl;
				return res;
			}else if (li>ri) return 0;
			else{
				ll ret=0;
				int tm = (tl+tr)/2;
				if (left and li<=min(ri, tm)) ret=__gcd(ret, left->query(li, min(ri, tm), lj, rj, tl, tm));
				if (right and max(li, tm+1)<=ri) ret=__gcd(ret, right->query(max(li, tm+1), ri, lj, rj, tm+1, tr));
				return ret;
			}
		}
	};
	mNode * root;
	ll csz, rsz;
	void init(int R, int C){
		rsz=R; csz=C;
		root = new mNode(csz);
	}
	void update(int i, int j, ll x){
		root->update(0, rsz-1, i, j, x);
	}
	ll query(int li, int ri, int lj, int rj){
		return root->query(li, ri, lj, rj, 0, rsz-1);
	}
} DS;


void init(int R, int C) {
	DS.init(R, C);
	// cout << "Init" << endl;
}

void update(int P, int Q, long long K) {
    // cout << "Updating " << P << "-" << Q << "-" << K << endl;
	DS.update(P, Q, K);
	// cout << "Updated " << P << "-" << Q << "-" << K << endl;
}

long long calculate(int P, int Q, int U, int V) {
	/* ... */
	ll res= DS.query(P, U, Q, V);
	// cout << "Queried" << endl;
	return res;
	// return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 404 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 1 ms 504 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 2 ms 336 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 508 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 711 ms 11340 KB Output is correct
5 Correct 295 ms 11336 KB Output is correct
6 Correct 1244 ms 8700 KB Output is correct
7 Correct 1415 ms 8520 KB Output is correct
8 Correct 976 ms 7540 KB Output is correct
9 Correct 1468 ms 8508 KB Output is correct
10 Correct 1264 ms 8264 KB Output is correct
11 Correct 2 ms 336 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 440 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Correct 1 ms 444 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 1 ms 504 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 2 ms 336 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 2 ms 336 KB Output is correct
12 Correct 1113 ms 13872 KB Output is correct
13 Correct 2027 ms 8008 KB Output is correct
14 Correct 312 ms 5512 KB Output is correct
15 Correct 2139 ms 9548 KB Output is correct
16 Correct 371 ms 11848 KB Output is correct
17 Correct 2244 ms 10056 KB Output is correct
18 Correct 3828 ms 13212 KB Output is correct
19 Correct 3169 ms 13452 KB Output is correct
20 Correct 3095 ms 12872 KB Output is correct
21 Correct 1 ms 440 KB Output is correct

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 440 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 504 KB Output is correct
9 Correct 2 ms 336 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 688 ms 11480 KB Output is correct
13 Correct 309 ms 11312 KB Output is correct
14 Correct 1300 ms 8700 KB Output is correct
15 Correct 1428 ms 8360 KB Output is correct
16 Correct 900 ms 7600 KB Output is correct
17 Correct 1361 ms 8456 KB Output is correct
18 Correct 1246 ms 8192 KB Output is correct
19 Correct 1074 ms 13640 KB Output is correct
20 Correct 2012 ms 8008 KB Output is correct
21 Correct 291 ms 5520 KB Output is correct
22 Correct 2165 ms 9544 KB Output is correct
23 Correct 348 ms 11816 KB Output is correct
24 Correct 1995 ms 10108 KB Output is correct
25 Correct 3609 ms 13284 KB Output is correct
26 Correct 3099 ms 13388 KB Output is correct
27 Correct 2813 ms 12680 KB Output is correct
28 Correct 943 ms 55704 KB Output is correct
29 Correct 1712 ms 58440 KB Output is correct
30 Correct 2865 ms 39056 KB Output is correct
31 Correct 2491 ms 31708 KB Output is correct
32 Correct 382 ms 10312 KB Output is correct
33 Correct 699 ms 10824 KB Output is correct
34 Correct 632 ms 52044 KB Output is correct
35 Correct 2455 ms 33932 KB Output is correct
36 Correct 4351 ms 56428 KB Output is correct
37 Correct 3574 ms 56456 KB Output is correct
38 Correct 3754 ms 55844 KB Output is correct
39 Correct 2899 ms 45896 KB Output is correct
40 Correct 1 ms 336 KB Output is correct

Subtask #5
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 508 KB Output is correct
2 Correct 2 ms 336 KB Output is correct
3 Correct 2 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 396 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 2 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 2 ms 508 KB Output is correct
12 Correct 673 ms 11396 KB Output is correct
13 Correct 284 ms 11252 KB Output is correct
14 Correct 1234 ms 8672 KB Output is correct
15 Correct 1459 ms 8520 KB Output is correct
16 Correct 978 ms 7496 KB Output is correct
17 Correct 1339 ms 8608 KB Output is correct
18 Correct 1161 ms 8224 KB Output is correct
19 Correct 1027 ms 13896 KB Output is correct
20 Correct 1922 ms 7796 KB Output is correct
21 Correct 288 ms 5756 KB Output is correct
22 Correct 2091 ms 9420 KB Output is correct
23 Correct 365 ms 11848 KB Output is correct
24 Correct 1997 ms 10100 KB Output is correct
25 Correct 3683 ms 13200 KB Output is correct
26 Correct 3151 ms 13384 KB Output is correct
27 Correct 2778 ms 12764 KB Output is correct
28 Correct 947 ms 55716 KB Output is correct
29 Correct 1784 ms 58440 KB Output is correct
30 Correct 2795 ms 39044 KB Output is correct
31 Correct 2404 ms 31580 KB Output is correct
32 Correct 378 ms 10192 KB Output is correct
33 Correct 646 ms 10712 KB Output is correct
34 Correct 611 ms 52280 KB Output is correct
35 Correct 2462 ms 34088 KB Output is correct
36 Correct 4381 ms 56288 KB Output is correct
37 Correct 3606 ms 56496 KB Output is correct
38 Correct 3570 ms 55940 KB Output is correct
39 Correct 1433 ms 105512 KB Output is correct
40 Correct 2919 ms 107592 KB Output is correct
41 Correct 4513 ms 74316 KB Output is correct
42 Correct 3928 ms 57924 KB Output is correct
43 Correct 1130 ms 102452 KB Output is correct
44 Correct 687 ms 10580 KB Output is correct
45 Correct 3121 ms 45904 KB Output is correct
46 Correct 5649 ms 106452 KB Output is correct
47 Correct 5952 ms 106544 KB Output is correct
48 Correct 5563 ms 106044 KB Output is correct
49 Correct 1 ms 336 KB Output is correct