Submission #108645

#	Time	Username	Problem	Language	Result	Execution time	Memory
108645		tictaccat	Game (IOI13_game)	C++14	63 / 100	7346 ms	257024 KiB

game

#include "game.h"

typedef long long ll;

#include <bits/stdc++.h>

using namespace std;

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 Node {
    Node *left, *right;
    ll g;
    Node(): g(0), left(NULL), right(NULL) {}
};

struct st1 {
    Node* root = new Node(); int sz = 1e9 + 100;
    void upd(Node* cur, int x, int y, int pos, ll val) {
        if (x > pos || y < pos) return;
        if (x == y) {
            cur->g = val;
            return;
        }
        if (cur->left == NULL) cur->left = new Node();
        if (cur->right == NULL) cur->right = new Node();
        int mid = (x+y)/2;
        upd(cur->left,x,mid,pos,val);
        upd(cur->right,mid+1,y,pos,val);
        cur->g = gcd2(cur->left->g, cur->right->g);
    }
    ll query(Node* cur, int x, int y, int l, int r) {
        if (x > r || y < l) return 0;
        if (l <= x && y <= r) return cur->g;
        if (cur->left == NULL) cur->left = new Node();
        if (cur->right == NULL) cur->right = new Node();
        int mid = (x+y)/2;
        return gcd2(query(cur->left,x,mid,l,r), query(cur->right,mid+1,y,l,r));
    }  
    void upd(int pos, ll val) {
        upd(root,0,sz-1,pos,val);
    }
    ll query(int l, int r){
        return query(root,0,sz-1,l,r);
    }
};


struct Node2 {
    Node2 *left,*right;
    st1 st;
    Node2(): left(NULL), right(NULL) {}
};

struct st2 {
    Node2* root = new Node2(); int sz = 1e9 + 100;
    void upd(Node2* cur, int x, int y, int pos2, int pos1, ll val) {
        if (x > pos2 || y < pos2) return;
        if (x == y) {
            cur->st.upd(pos1,val);
            return;
        }
        if (cur->left == NULL) cur->left = new Node2();
        if (cur->right == NULL) cur->right = new Node2();
        int mid = (x+y)/2;
        upd(cur->left,x,mid,pos2,pos1,val);
        upd(cur->right,mid+1,y,pos2,pos1,val);
        cur->st.upd(pos1, gcd2(cur->left->st.query(pos1,pos1),cur->right->st.query(pos1,pos1)));
    }
    ll query(Node2* cur, int x, int y, int l2, int r2, int l1, int r1) {
        if (x > r2 || y < l2) return 0;
        if (l2 <= x && y <= r2) return cur->st.query(l1,r1);
        if (cur->left == NULL) cur->left = new Node2();
        if (cur->right == NULL) cur->right = new Node2();
        int mid = (x+y)/2;
        return gcd2(query(cur->left,x,mid,l2,r2,l1,r1), query(cur->right,mid+1,y,l2,r2,l1,r1));
    }  
    void upd(int pos2, int pos1, ll val) {
        upd(root,0,sz-1,pos2,pos1,val);
    }
    ll query(int l2, int r2, int l1, int r1){
        return query(root,0,sz-1,l2,r2,l1,r1);
    }
} tr;

void init(int R, int C) {
    /* ... */
}

void update(int P, int Q, long long K) {
    /* ... */
    tr.upd(P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
    /* ... */
    if (P > U) swap(P,U);
    if (Q > V) swap(V,Q);
    return tr.query(P,U,Q,V);
}

// int main() {

//     st2 test;

//     test.upd(0,2,20);
//     test.upd(0,1,15);

//     cout << test.query(0,0,0,2);
  
//     return 0;
// }

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~
game.cpp: In constructor 'Node::Node()':
game.cpp:21:8: warning: 'Node::g' will be initialized after [-Wreorder]
     ll g;
        ^
game.cpp:20:11: warning:   'Node* Node::left' [-Wreorder]
     Node *left, *right;
           ^~~~
game.cpp:22:5: warning:   when initialized here [-Wreorder]
     Node(): g(0), left(NULL), right(NULL) {}
     ^~~~

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20