oj.uz

Submission #54518

# Submission time Handle Problem Language Result Execution time Memory
54518 2018-07-03T23:32:44 Z KieranHorgan Game (IOI13_game) C++17
63 / 100
 3364 ms 257024 KB 
#pragma GCC optimize("Ofast")
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
 
long long gcd2(long long X, long long Y) {
    long long tmp;
    if(X==0&&Y==0) return 0;
    if(X==0) return Y;
    if(Y==0) return X;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
 
int R, C;
struct colNode {
    int l, r, st;
    colNode *left, *right;
    colNode(int lv, int rv): left(NULL), right(NULL), st(0) {l=lv; r=rv;};
};
set<pair<int, int>> isNew;
int query(int x, int y, colNode *cur) {
    if(cur == NULL) return 0;
    if(x >= cur->r || y <= cur->l) return 0;
    if(y >= cur->r && x <= cur->l) {
        int temp = cur->st;
        // cerr << "  " << cur->l << " " << cur->r << ": " << temp << endl;
        return temp;
    }
    if(cur->right==NULL) return query(x, y, cur->left);
    if(cur->left==NULL) return query(x, y, cur->right);
    return gcd2(query(x, y, cur->left),
                query(x, y, cur->right));
}
void update(int j, int val, colNode *cur, colNode *rowL, colNode *rowR) {
    if(cur == NULL) return;
    if(j < cur->l || j >= cur->r) {
        // cerr << "  " << cur->l << " " << cur->r << ": " << j << endl;
        return;
    }
    if(cur->l + 1 == cur->r) {
        if(rowL == NULL && rowR == NULL) cur->st = val;
        else if(rowL == NULL) cur->st = query(j, j+1, rowR);
        else if(rowR == NULL) cur->st = query(j, j+1, rowL);
        else cur->st = gcd2(query(j, j+1, rowL), query(j, j+1, rowR));
        // cerr << "  " << cur->l << " " << cur->r << ": " << val << endl;
        // cerr << cur->l << " " << cur->r << ":    \t" << cur->st << endl;
        //Check if merging rows
        return;
    }
    int mid = (cur->l + cur->r)/2;
    if(j < mid) {
        if(cur->left == NULL)
            cur->left = new colNode(cur->l, mid);
        update(j, val, cur->left, rowL, rowR);
    } else {
        if(cur->right == NULL)
            cur->right = new colNode(mid, cur->r);
        update(j, val, cur->right, rowL, rowR);
    }
    if(cur->left==NULL) cur->st = cur->right->st;
    else if(cur->right==NULL) cur->st = cur->left->st;
    else cur->st = gcd2(cur->left->st, cur->right->st);
    // cerr << "  " << cur->l << " " << cur->r << ": " << cur->st << endl;
}
struct rowNode {
    int l, r;
    rowNode *left, *right;
    colNode *col;
    rowNode(int lv, int rv): left(NULL), right(NULL) {l=lv; r=rv; col = new colNode(0, C);};
};
void update(int i, int j, int val, rowNode *cur) {
    if(cur == NULL) return;
    if(i < cur->l || i >= cur->r) return;
    int mid = (cur->l + cur->r)/2;
    
    if(cur->l+1 == cur-> r) {

    } else if(i < mid) {
        if(cur->left == NULL)
            cur->left = new rowNode(cur->l, mid);
        update(i, j, val, cur->left);
    } else {
        if(cur->right == NULL)
            cur->right = new rowNode(mid, cur->r);
        update(i, j, val, cur->right);
    }
    // cerr << cur->l << " " << cur->r << ": " << endl;
    if(cur->left == NULL && cur->right == NULL) update(j, val, cur->col, NULL, NULL);
    else if(cur->left == NULL) update(j, val, cur->col, NULL, cur->right->col);
    else if(cur->right == NULL) update(j, val, cur->col, cur->left->col, NULL);
    else update(j, val, cur->col, cur->left->col, cur->right->col);
        // cerr << cur->l << " " << cur->r << ":    \t" << cur->st << endl;
}
int query(int x, int y, int nx, int ny, rowNode *cur) {
    if(cur == NULL) return 0;
    if(x >= cur->r || y <= cur->l) return 0;
    if(y >= cur->r && x <= cur->l) {
        int temp = query(nx, ny, cur->col);
        // cerr << cur->l << " " << cur->r << ": " << temp << endl;
        return temp;
    }
    if(cur->right==NULL) return query(x, y, nx, ny, cur->left);
    if(cur->left==NULL) return query(x, y, nx, ny, cur->right);
    return gcd2(query(x, y, nx, ny, cur->left),
                query(x, y, nx, ny, cur->right));
}

rowNode root(0,1);

void init(signed r, signed c) {
    R = r;
    C = c;
    root = *(new rowNode(0, R));
}

void update(signed P, signed Q, long long K) {
    // cerr << "Update:" << endl;
    update(P, Q, K, &root);
    // cerr << endl;
    // update(Q, K, &root);
    // cerr << endl;
}
 
long long calculate(signed P, signed Q, signed U, signed V) {
    // cerr << "Query:" << endl;
    int x = query(P, U+1, Q, V+1, &root);
    // cerr << endl;
    // cerr << endl;
    return x;
}

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 'colNode::colNode(long long int, long long int)':
game.cpp:23:21: warning: 'colNode::right' will be initialized after [-Wreorder]
     colNode *left, *right;
                     ^~~~~
game.cpp:22:15: warning:   'long long int colNode::st' [-Wreorder]
     int l, r, st;
               ^~
game.cpp:24:5: warning:   when initialized here [-Wreorder]
     colNode(int lv, int rv): left(NULL), right(NULL), st(0) {l=lv; r=rv;};
     ^~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 612 KB Output is correct
3 Correct 3 ms 612 KB Output is correct
4 Correct 2 ms 612 KB Output is correct
5 Correct 2 ms 612 KB Output is correct
6 Correct 3 ms 676 KB Output is correct
7 Correct 2 ms 676 KB Output is correct
8 Correct 2 ms 676 KB Output is correct
9 Correct 3 ms 836 KB Output is correct
10 Correct 2 ms 836 KB Output is correct
11 Correct 2 ms 836 KB Output is correct
12 Correct 2 ms 836 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 836 KB Output is correct
2 Correct 2 ms 836 KB Output is correct
3 Correct 2 ms 836 KB Output is correct
4 Correct 766 ms 21592 KB Output is correct
5 Correct 478 ms 25756 KB Output is correct
6 Correct 839 ms 27692 KB Output is correct
7 Correct 1109 ms 31932 KB Output is correct
8 Correct 570 ms 31932 KB Output is correct
9 Correct 966 ms 40984 KB Output is correct
10 Correct 961 ms 45240 KB Output is correct
11 Correct 3 ms 45240 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 45240 KB Output is correct
2 Correct 3 ms 45240 KB Output is correct
3 Correct 3 ms 45240 KB Output is correct
4 Correct 2 ms 45240 KB Output is correct
5 Correct 2 ms 45240 KB Output is correct
6 Correct 4 ms 45240 KB Output is correct
7 Correct 2 ms 45240 KB Output is correct
8 Correct 2 ms 45240 KB Output is correct
9 Correct 3 ms 45240 KB Output is correct
10 Correct 2 ms 45240 KB Output is correct
11 Correct 3 ms 45240 KB Output is correct
12 Correct 1203 ms 57420 KB Output is correct
13 Correct 2592 ms 57420 KB Output is correct
14 Correct 348 ms 57420 KB Output is correct
15 Correct 3364 ms 61488 KB Output is correct
16 Correct 396 ms 79896 KB Output is correct
17 Correct 1441 ms 79896 KB Output is correct
18 Correct 2539 ms 90532 KB Output is correct
19 Correct 2470 ms 96036 KB Output is correct
20 Correct 2279 ms 100648 KB Output is correct
21 Correct 3 ms 100648 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 100648 KB Output is correct
2 Correct 3 ms 100648 KB Output is correct
3 Correct 4 ms 100648 KB Output is correct
4 Correct 2 ms 100648 KB Output is correct
5 Correct 2 ms 100648 KB Output is correct
6 Correct 3 ms 100648 KB Output is correct
7 Correct 2 ms 100648 KB Output is correct
8 Correct 2 ms 100648 KB Output is correct
9 Correct 3 ms 100648 KB Output is correct
10 Correct 2 ms 100648 KB Output is correct
11 Correct 3 ms 100648 KB Output is correct
12 Correct 753 ms 100648 KB Output is correct
13 Correct 524 ms 100648 KB Output is correct
14 Correct 852 ms 100968 KB Output is correct
15 Correct 892 ms 105356 KB Output is correct
16 Correct 553 ms 105356 KB Output is correct
17 Correct 855 ms 114544 KB Output is correct
18 Correct 754 ms 118656 KB Output is correct
19 Correct 1150 ms 130736 KB Output is correct
20 Correct 2845 ms 130736 KB Output is correct
21 Correct 351 ms 130736 KB Output is correct
22 Correct 3073 ms 134884 KB Output is correct
23 Correct 344 ms 153428 KB Output is correct
24 Correct 1534 ms 153428 KB Output is correct
25 Correct 2680 ms 163868 KB Output is correct
26 Correct 2154 ms 169512 KB Output is correct
27 Correct 1877 ms 174108 KB Output is correct
28 Runtime error 2115 ms 257024 KB Memory limit exceeded
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 257024 KB Memory limit exceeded
2 Halted 0 ms 0 KB -