oj.uz

Submission #54519

# Submission time Handle Problem Language Result Execution time Memory
54519 2018-07-04T00:00:41 Z KieranHorgan Game (IOI13_game) C++17
63 / 100
 5297 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(j, j+1);
        } else if(cur->left->l != cur->l || cur->left->r != mid) {
            int mid2 = (cur->l+mid)/2;
            if(cur->left->l < mid2) {
                cur->left->left = new colNode(cur->left->l, cur->left->r);
                cur->left->left->st = cur->left->st;
            } else {
                cur->left->right = new colNode(cur->left->l, cur->left->r);
                cur->left->right->st = cur->left->st;
            }
            cur->left->l = cur->l;
            cur->left->r = mid;
        }
        update(j, val, cur->left, rowL, rowR);
    } else {
        if(cur->right == NULL) {
            cur->right = new colNode(mid, cur->r);
        } else if(cur->right->l != mid || cur->right->r != cur->r) {
            int mid2 = (cur->r+mid)/2;
            if(cur->right->l < mid2) {
                cur->right->left = new colNode(cur->right->l, cur->right->r);
                cur->right->left->st = cur->right->st;
            } else {
                cur->right->right = new colNode(cur->right->l, cur->right->r);
                cur->right->right->st = cur->right->st;
            }
            cur->right->l = mid;
            cur->right->r = 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 376 KB Output is correct
2 Correct 2 ms 488 KB Output is correct
3 Correct 3 ms 488 KB Output is correct
4 Correct 2 ms 556 KB Output is correct
5 Correct 2 ms 556 KB Output is correct
6 Correct 3 ms 728 KB Output is correct
7 Correct 3 ms 728 KB Output is correct
8 Correct 2 ms 728 KB Output is correct
9 Correct 3 ms 728 KB Output is correct
10 Correct 3 ms 728 KB Output is correct
11 Correct 3 ms 728 KB Output is correct
12 Correct 3 ms 728 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 728 KB Output is correct
2 Correct 2 ms 728 KB Output is correct
3 Correct 2 ms 728 KB Output is correct
4 Correct 718 ms 15168 KB Output is correct
5 Correct 499 ms 19460 KB Output is correct
6 Correct 793 ms 20944 KB Output is correct
7 Correct 884 ms 25452 KB Output is correct
8 Correct 488 ms 27380 KB Output is correct
9 Correct 861 ms 34376 KB Output is correct
10 Correct 746 ms 38556 KB Output is correct
11 Correct 2 ms 38556 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 38556 KB Output is correct
2 Correct 3 ms 38556 KB Output is correct
3 Correct 2 ms 38556 KB Output is correct
4 Correct 2 ms 38556 KB Output is correct
5 Correct 2 ms 38556 KB Output is correct
6 Correct 2 ms 38556 KB Output is correct
7 Correct 2 ms 38556 KB Output is correct
8 Correct 2 ms 38556 KB Output is correct
9 Correct 3 ms 38556 KB Output is correct
10 Correct 2 ms 38556 KB Output is correct
11 Correct 2 ms 38556 KB Output is correct
12 Correct 1146 ms 50004 KB Output is correct
13 Correct 2815 ms 50004 KB Output is correct
14 Correct 350 ms 50004 KB Output is correct
15 Correct 3089 ms 58832 KB Output is correct
16 Correct 309 ms 66884 KB Output is correct
17 Correct 1264 ms 66884 KB Output is correct
18 Correct 2286 ms 77360 KB Output is correct
19 Correct 1826 ms 82884 KB Output is correct
20 Correct 1530 ms 87580 KB Output is correct
21 Correct 2 ms 87580 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 87580 KB Output is correct
2 Correct 3 ms 87580 KB Output is correct
3 Correct 3 ms 87580 KB Output is correct
4 Correct 2 ms 87580 KB Output is correct
5 Correct 2 ms 87580 KB Output is correct
6 Correct 2 ms 87580 KB Output is correct
7 Correct 2 ms 87580 KB Output is correct
8 Correct 2 ms 87580 KB Output is correct
9 Correct 3 ms 87580 KB Output is correct
10 Correct 2 ms 87580 KB Output is correct
11 Correct 3 ms 87580 KB Output is correct
12 Correct 679 ms 88728 KB Output is correct
13 Correct 425 ms 92876 KB Output is correct
14 Correct 679 ms 94384 KB Output is correct
15 Correct 1008 ms 98764 KB Output is correct
16 Correct 600 ms 100856 KB Output is correct
17 Correct 885 ms 107692 KB Output is correct
18 Correct 667 ms 112044 KB Output is correct
19 Correct 1094 ms 123544 KB Output is correct
20 Correct 2664 ms 123544 KB Output is correct
21 Correct 403 ms 123544 KB Output is correct
22 Correct 3194 ms 132260 KB Output is correct
23 Correct 281 ms 140264 KB Output is correct
24 Correct 1228 ms 140264 KB Output is correct
25 Correct 2286 ms 150948 KB Output is correct
26 Correct 1973 ms 156224 KB Output is correct
27 Correct 1718 ms 161136 KB Output is correct
28 Correct 761 ms 219908 KB Output is correct
29 Correct 1780 ms 223896 KB Output is correct
30 Runtime error 5297 ms 257024 KB Memory limit exceeded
31 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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