oj.uz

Submission #108645

# Submission time Handle Problem Language Result Execution time Memory
108645 2019-04-30T13:12:29 Z tictaccat Game (IOI13_game) C++14
63 / 100
 7346 ms 257024 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 = 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

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 3 ms 512 KB Output is correct
2 Correct 7 ms 1280 KB Output is correct
3 Correct 7 ms 1280 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 6 ms 1280 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Correct 6 ms 1280 KB Output is correct
10 Correct 6 ms 1024 KB Output is correct
11 Correct 6 ms 640 KB Output is correct
12 Correct 2 ms 512 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 2172 ms 150284 KB Output is correct
5 Correct 1529 ms 149032 KB Output is correct
6 Correct 2713 ms 196880 KB Output is correct
7 Correct 2530 ms 196548 KB Output is correct
8 Correct 1947 ms 148468 KB Output is correct
9 Correct 2528 ms 198776 KB Output is correct
10 Correct 2699 ms 196784 KB Output is correct
11 Correct 3 ms 512 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 7 ms 1408 KB Output is correct
3 Correct 7 ms 1280 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 10 ms 1280 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 4 ms 768 KB Output is correct
9 Correct 21 ms 1280 KB Output is correct
10 Correct 5 ms 1024 KB Output is correct
11 Correct 6 ms 640 KB Output is correct
12 Correct 2209 ms 39196 KB Output is correct
13 Correct 2761 ms 18180 KB Output is correct
14 Correct 1670 ms 3320 KB Output is correct
15 Correct 3025 ms 29944 KB Output is correct
16 Correct 1086 ms 58384 KB Output is correct
17 Correct 6062 ms 223712 KB Output is correct
18 Correct 6641 ms 233864 KB Output is correct
19 Correct 6991 ms 233864 KB Output is correct
20 Correct 6638 ms 232828 KB Output is correct
21 Correct 2 ms 256 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 7 ms 1280 KB Output is correct
3 Correct 8 ms 1280 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 3 ms 768 KB Output is correct
6 Correct 6 ms 1280 KB Output is correct
7 Correct 2 ms 512 KB Output is correct
8 Correct 2 ms 768 KB Output is correct
9 Correct 6 ms 1280 KB Output is correct
10 Correct 5 ms 1024 KB Output is correct
11 Correct 4 ms 768 KB Output is correct
12 Correct 2262 ms 150652 KB Output is correct
13 Correct 1549 ms 148976 KB Output is correct
14 Correct 2925 ms 196880 KB Output is correct
15 Correct 2763 ms 196540 KB Output is correct
16 Correct 1940 ms 148288 KB Output is correct
17 Correct 2787 ms 198588 KB Output is correct
18 Correct 2620 ms 196732 KB Output is correct
19 Correct 2252 ms 42988 KB Output is correct
20 Correct 2591 ms 21864 KB Output is correct
21 Correct 1565 ms 7532 KB Output is correct
22 Correct 3215 ms 34216 KB Output is correct
23 Correct 991 ms 62176 KB Output is correct
24 Correct 6086 ms 228432 KB Output is correct
25 Correct 6955 ms 239088 KB Output is correct
26 Correct 6881 ms 238836 KB Output is correct
27 Correct 6511 ms 238032 KB Output is correct
28 Runtime error 462 ms 257024 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 7 ms 1408 KB Output is correct
3 Correct 8 ms 1408 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 4 ms 640 KB Output is correct
6 Correct 7 ms 1152 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Correct 4 ms 768 KB Output is correct
9 Correct 6 ms 1280 KB Output is correct
10 Correct 4 ms 1024 KB Output is correct
11 Correct 4 ms 768 KB Output is correct
12 Correct 2322 ms 150992 KB Output is correct
13 Correct 1462 ms 148840 KB Output is correct
14 Correct 2979 ms 197192 KB Output is correct
15 Correct 2802 ms 196708 KB Output is correct
16 Correct 2116 ms 148472 KB Output is correct
17 Correct 2571 ms 198836 KB Output is correct
18 Correct 2482 ms 196800 KB Output is correct
19 Correct 2094 ms 42868 KB Output is correct
20 Correct 2761 ms 21888 KB Output is correct
21 Correct 1510 ms 7548 KB Output is correct
22 Correct 3293 ms 34144 KB Output is correct
23 Correct 1053 ms 62264 KB Output is correct
24 Correct 6087 ms 228424 KB Output is correct
25 Correct 7346 ms 239048 KB Output is correct
26 Correct 7075 ms 238748 KB Output is correct
27 Correct 6680 ms 237984 KB Output is correct
28 Runtime error 548 ms 257024 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -