oj.uz

Submission #54517

# Submission time Handle Problem Language Result Execution time Memory
54517 2018-07-03T23:31:57 Z KieranHorgan Game (IOI13_game) C++17
0 / 100
 4 ms 1128 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(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
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 4 ms 664 KB Output is correct
4 Correct 2 ms 664 KB Output is correct
5 Runtime error 3 ms 748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 748 KB Output is correct
2 Correct 3 ms 748 KB Output is correct
3 Runtime error 2 ms 748 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 748 KB Output is correct
2 Correct 3 ms 1076 KB Output is correct
3 Correct 3 ms 1076 KB Output is correct
4 Correct 2 ms 1076 KB Output is correct
5 Runtime error 2 ms 1076 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1076 KB Output is correct
2 Correct 3 ms 1128 KB Output is correct
3 Correct 3 ms 1128 KB Output is correct
4 Correct 2 ms 1128 KB Output is correct
5 Runtime error 3 ms 1128 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1128 KB Output is correct
2 Correct 3 ms 1128 KB Output is correct
3 Correct 3 ms 1128 KB Output is correct
4 Correct 2 ms 1128 KB Output is correct
5 Runtime error 2 ms 1128 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -