oj.uz

Submission #789545

# Submission time Handle Problem Language Result Execution time Memory
789545 2023-07-21T13:26:00 Z MODDI Game (IOI13_game) C++17
100 / 100
 2867 ms 118428 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
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;
}
struct segtree{
struct Node {
        ll v;
        Node* l, * r;
        int flag;
 
        Node(ll a, Node* b, Node* c) : v(a), l(b), r(c) {flag = -1;}
    };
 
    int size;
    Node* root, *null;
    void init(int n) {
        size = 1;
        while (size < n) size *= 2;
        null = new Node(0, nullptr, nullptr);
        null->l = null->r = null;
        root = null;
    }
 
    Node* update(Node* node, int lx, int rx, int i, ll v) {
        if (node == null)
            node = new Node(0, null, null);
 
        if (lx == rx - 1) {
            node->v = v;
            return node;
        }
 
        int mid = (lx + rx) / 2;
        if (node->flag == -1 || node->flag == i) {
            node->flag = i;
            node->v = v;
 
            return node;
        }
        else if (node->flag != -2) {
            if (node->flag < mid) {
                node->l = update(node->l, lx, mid, node->flag, node->v);
            }
            else {
                node->r =update(node->r, mid, rx,node->flag, node->v);
            }
 
            node->flag = -2;
        }
 
        if (i < mid) {
            node->l = update(node->l, lx, mid, i, v);
        }
        else {
            node->r = update(node->r, mid, rx, i, v);
        }
        node->v = gcd2(node->l->v, node->r->v);
 
        return node;
    }
    void update(int i, ll v) {
        root = update(root, 0, size, i, v);
    }
 
    ll query(Node* node, int lx, int rx, int l, int r) {
        if (l >= rx || lx >= r || node == null) {
            return 0ll;
        }
        if (node->flag >= 0) {
            int p = node->flag;
            if (p >= l && p < r)
                return node->v;
            else
                return 0LL;
        }
        if (l <= lx && rx <= r) {
            ll ret = node->v;
            return ret;
        }
 
        int mid = (lx + rx) / 2;
        ll left = query(node->l, lx, mid, l, r);
        ll right = query(node->r, mid, rx, l, r);
 
        return gcd2(left, right);
    }
    ll query(int l, int r) {
        return query(root, 0, size, l, r);
    }	
};
struct seg2D{
	struct Node{
		segtree col;
		Node*l , *r;
		Node(int sz, Node* a, Node* b) : l(a), r(b){ col.init(sz);}
	};
	Node* root, *null;
	int row_size, col_size;
	void init(int n, int m){
		row_size = 1;
		while(row_size<n)	row_size*=2;
		col_size = m;
		null = new Node(col_size, nullptr, nullptr);
		null->l= null->r = null;
		root = null;
	}
	ll query(Node* node, int l1, int r1, int l2, int r2, int L, int R){
		if(l1 >= R || L >= r1 || node == null)	return 0ll;
		if(l1 <= L && R <= r1){
			return node->col.query(l2, r2);
		}
		int mid = (L + R) / 2;
		ll left = query(node->l, l1, r1, l2, r2, L, mid);
		ll right = query(node->r, l1, r1, l2, r2, mid, R);
		return gcd2(left, right);
	}
	ll query(int l1, int r1, int l2, int r2){
		return query(root, l1, r1, l2, r2, 0, row_size);
	}
	Node* update(Node* node, int l, int r, int L, int R, ll v){
		if (node == null) node = new Node(col_size, null, null);
 
        if (L+1==R) {
            node->col.update(r, v);
            return node;
        }
 
        int mid = (L + R) / 2;
        if (l < mid) {
            node->l = update(node->l, l, r, L, mid, v);
        }
        else {
            node->r = update(node->r, l, r, mid, R, v);
        }
 
        ll new_v = gcd2(node->l->col.query(r, r + 1), node->r->col.query(r, r + 1));
        node->col.update(r, new_v);
 
        return node;
	}
	void update(int l, int r, ll v){
		root = update(root, l, r, 0, row_size, v);
	}
};
seg2D mat;
void init(int R, int C) {
   	mat.init(R, C);
}

void update(int P, int Q, long long K) {
    mat.update(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return mat.query(P, U+1, Q, V+1);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 299 ms 9752 KB Output is correct
5 Correct 266 ms 13852 KB Output is correct
6 Correct 311 ms 11380 KB Output is correct
7 Correct 339 ms 11100 KB Output is correct
8 Correct 231 ms 8740 KB Output is correct
9 Correct 320 ms 11116 KB Output is correct
10 Correct 297 ms 10828 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 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 296 KB Output is correct
10 Correct 1 ms 296 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 533 ms 16772 KB Output is correct
13 Correct 934 ms 9804 KB Output is correct
14 Correct 217 ms 5704 KB Output is correct
15 Correct 1054 ms 12208 KB Output is correct
16 Correct 212 ms 15696 KB Output is correct
17 Correct 495 ms 12044 KB Output is correct
18 Correct 834 ms 17132 KB Output is correct
19 Correct 673 ms 17176 KB Output is correct
20 Correct 644 ms 16684 KB Output is correct
21 Correct 0 ms 212 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 332 ms 14060 KB Output is correct
13 Correct 220 ms 13888 KB Output is correct
14 Correct 335 ms 11336 KB Output is correct
15 Correct 336 ms 11148 KB Output is correct
16 Correct 259 ms 8684 KB Output is correct
17 Correct 331 ms 11324 KB Output is correct
18 Correct 316 ms 10792 KB Output is correct
19 Correct 580 ms 16632 KB Output is correct
20 Correct 935 ms 9856 KB Output is correct
21 Correct 211 ms 5588 KB Output is correct
22 Correct 1062 ms 12112 KB Output is correct
23 Correct 209 ms 15692 KB Output is correct
24 Correct 490 ms 12184 KB Output is correct
25 Correct 821 ms 17208 KB Output is correct
26 Correct 663 ms 17164 KB Output is correct
27 Correct 621 ms 16664 KB Output is correct
28 Correct 409 ms 59516 KB Output is correct
29 Correct 839 ms 54536 KB Output is correct
30 Correct 2096 ms 49700 KB Output is correct
31 Correct 2031 ms 39428 KB Output is correct
32 Correct 408 ms 10596 KB Output is correct
33 Correct 578 ms 14236 KB Output is correct
34 Correct 370 ms 48292 KB Output is correct
35 Correct 656 ms 31552 KB Output is correct
36 Correct 1201 ms 52400 KB Output is correct
37 Correct 919 ms 52728 KB Output is correct
38 Correct 1014 ms 51980 KB Output is correct
39 Correct 864 ms 42764 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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 315 ms 14156 KB Output is correct
13 Correct 240 ms 13888 KB Output is correct
14 Correct 315 ms 11456 KB Output is correct
15 Correct 330 ms 11064 KB Output is correct
16 Correct 233 ms 8740 KB Output is correct
17 Correct 325 ms 11196 KB Output is correct
18 Correct 296 ms 10764 KB Output is correct
19 Correct 592 ms 16588 KB Output is correct
20 Correct 940 ms 9908 KB Output is correct
21 Correct 228 ms 5636 KB Output is correct
22 Correct 1085 ms 12056 KB Output is correct
23 Correct 210 ms 15692 KB Output is correct
24 Correct 497 ms 12116 KB Output is correct
25 Correct 895 ms 17200 KB Output is correct
26 Correct 704 ms 17252 KB Output is correct
27 Correct 685 ms 16644 KB Output is correct
28 Correct 412 ms 59600 KB Output is correct
29 Correct 906 ms 54572 KB Output is correct
30 Correct 2127 ms 49700 KB Output is correct
31 Correct 2076 ms 39544 KB Output is correct
32 Correct 410 ms 10616 KB Output is correct
33 Correct 545 ms 14236 KB Output is correct
34 Correct 400 ms 48292 KB Output is correct
35 Correct 657 ms 31540 KB Output is correct
36 Correct 1330 ms 52428 KB Output is correct
37 Correct 1048 ms 52780 KB Output is correct
38 Correct 961 ms 52052 KB Output is correct
39 Correct 685 ms 118428 KB Output is correct
40 Correct 1497 ms 101976 KB Output is correct
41 Correct 2867 ms 98888 KB Output is correct
42 Correct 2796 ms 76148 KB Output is correct
43 Correct 648 ms 96892 KB Output is correct
44 Correct 571 ms 10960 KB Output is correct
45 Correct 826 ms 42824 KB Output is correct
46 Correct 1772 ms 101016 KB Output is correct
47 Correct 1779 ms 101032 KB Output is correct
48 Correct 1705 ms 100584 KB Output is correct
49 Correct 0 ms 212 KB Output is correct