oj.uz

Submission #108643

# Submission time Handle Problem Language Result Execution time Memory
108643 2019-04-30T13:11:23 Z tictaccat Game (IOI13_game) C++14
36 / 100
 5387 ms 226700 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, 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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 5 ms 768 KB Output is correct
3 Correct 4 ms 896 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 512 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 640 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct

Subtask #2
0 / 27.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 768 KB Output is correct
3 Correct 5 ms 896 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 4 ms 768 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 588 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 4 ms 640 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 1578 ms 37456 KB Output is correct
13 Correct 2250 ms 16588 KB Output is correct
14 Correct 1260 ms 7000 KB Output is correct
15 Correct 2618 ms 24072 KB Output is correct
16 Correct 839 ms 51976 KB Output is correct
17 Correct 4750 ms 216360 KB Output is correct
18 Correct 5387 ms 226700 KB Output is correct
19 Correct 4966 ms 226416 KB Output is correct
20 Correct 5217 ms 226340 KB Output is correct
21 Correct 2 ms 384 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 6 ms 768 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 3 ms 768 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Correct 4 ms 512 KB Output is correct
12 Incorrect 255 ms 3848 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 356 KB Output is correct
2 Correct 4 ms 768 KB Output is correct
3 Correct 6 ms 896 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 4 ms 768 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 512 KB Output is correct
9 Correct 4 ms 740 KB Output is correct
10 Correct 3 ms 640 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Incorrect 273 ms 3756 KB Output isn't correct
13 Halted 0 ms 0 KB -