oj.uz

Submission #108637

# Submission time Handle Problem Language Result Execution time Memory
108637 2019-04-30T12:46:21 Z tictaccat Game (IOI13_game) C++14
0 / 100
 4 ms 768 KB 
#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 = 2000 + 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 = 2000 + 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,val);
    }
    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

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Incorrect 4 ms 768 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 3 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 3 ms 640 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Incorrect 3 ms 768 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Incorrect 3 ms 640 KB Output isn't correct
3 Halted 0 ms 0 KB -