Submission #789545

#	Time	Username	Problem	Language	Result	Execution time	Memory
789545		MODDI	Game (IOI13_game)	C++17	100 / 100	2867 ms	118428 KiB

game

#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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20