oj.uz

Submission #54735

# Submission time Handle Problem Language Result Execution time Memory
54735 2018-07-04T22:02:35 Z KieranHorgan Game (IOI13_game) C++17
63 / 100
 5274 ms 256752 KB 
#pragma GCC optimize("Ofast")
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
#define ll 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;
    ll st;
    colNode *left, *right;
    colNode(int lv, int rv): left(NULL), right(NULL), st(0) {l=lv; r=rv;};
};
set<pair<int, int>> isNew;
ll query(int x, int y, colNode *cur) {
    if(cur == NULL) {
        // cerr << "  inv " << endl;
        return 0;
    }
    // cerr << "  " << cur->l << " " << cur->r << ": " << cur->st << endl;
    if(x >= cur->r || y <= cur->l) {
        // cerr << " i" << cur->l << " " << cur->r << ": " << cur->st << endl;
        return 0;
    }
    if(y >= cur->r && x <= cur->l) {
        // cerr << "  " << cur->l << " " << cur->r << ": " << cur->st << endl;
        return cur->st;
    }
    if(cur->left==NULL && cur->right==NULL) 
    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, ll val, colNode *cur, colNode *rowL, colNode *rowR) {
    if(cur == NULL) return;
    if(j < cur->l || j >= cur->r) 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));
        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(j, j+1);
        } 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);
}
void copy(colNode *orig, colNode *next) {
    if(orig == NULL) return;
    next->l = orig->l; next->r = orig->r;
    next->st = orig->st;
    if(orig->left != NULL) { next->left = new colNode(0, 0); copy(orig->left, next->left); }
    if(orig->right != NULL) { next->right = new colNode(0, 0); copy(orig->right, next->right); }
}
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, ll 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(i, i+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 rowNode(cur->left->l, cur->left->r);
                copy(cur->left->col, cur->left->left->col);
            } else {
                cur->left->right = new rowNode(cur->left->l, cur->left->r);
                copy(cur->left->col, cur->left->right->col);
            }
            cur->left->l = cur->l;
            cur->left->r = mid;
        }
        update(i, j, val, cur->left);
    } else {
        if(cur->right == NULL) {
            cur->right = new rowNode(i, i+1);
        } 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 rowNode(cur->right->l, cur->right->r);
                copy(cur->right->col, cur->right->left->col);
            } else {
                cur->right->right = new rowNode(cur->right->l, cur->right->r);
                copy(cur->right->col, cur->right->right->col);
            }
            cur->right->l = mid;
            cur->right->r = cur->r;
        }
        update(i, j, val, cur->right);
    }
    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);
}
ll 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) return query(nx, ny, cur->col);
    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) {
    update(P, Q, K, &root);
}
 
long long calculate(signed P, signed Q, signed U, signed V) {
    return query(P, U+1, Q, V+1, &root);;
}

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(int, int)':
game.cpp:24:21: warning: 'colNode::right' will be initialized after [-Wreorder]
     colNode *left, *right;
                     ^~~~~
game.cpp:23:8: warning:   'long long int colNode::st' [-Wreorder]
     ll st;
        ^~
game.cpp:25: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 3 ms 340 KB Output is correct
2 Correct 3 ms 360 KB Output is correct
3 Correct 3 ms 416 KB Output is correct
4 Correct 2 ms 452 KB Output is correct
5 Correct 2 ms 500 KB Output is correct
6 Correct 3 ms 740 KB Output is correct
7 Correct 2 ms 740 KB Output is correct
8 Correct 2 ms 740 KB Output is correct
9 Correct 3 ms 740 KB Output is correct
10 Correct 2 ms 740 KB Output is correct
11 Correct 3 ms 740 KB Output is correct
12 Correct 2 ms 740 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 740 KB Output is correct
2 Correct 2 ms 752 KB Output is correct
3 Correct 2 ms 776 KB Output is correct
4 Correct 812 ms 14116 KB Output is correct
5 Correct 487 ms 18324 KB Output is correct
6 Correct 751 ms 19824 KB Output is correct
7 Correct 788 ms 24236 KB Output is correct
8 Correct 522 ms 26732 KB Output is correct
9 Correct 733 ms 33172 KB Output is correct
10 Correct 673 ms 37552 KB Output is correct
11 Correct 2 ms 37552 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 37552 KB Output is correct
2 Correct 3 ms 37552 KB Output is correct
3 Correct 3 ms 37552 KB Output is correct
4 Correct 2 ms 37552 KB Output is correct
5 Correct 2 ms 37552 KB Output is correct
6 Correct 2 ms 37552 KB Output is correct
7 Correct 2 ms 37552 KB Output is correct
8 Correct 2 ms 37552 KB Output is correct
9 Correct 2 ms 37552 KB Output is correct
10 Correct 2 ms 37552 KB Output is correct
11 Correct 2 ms 37552 KB Output is correct
12 Correct 1252 ms 48636 KB Output is correct
13 Correct 3050 ms 48636 KB Output is correct
14 Correct 360 ms 48636 KB Output is correct
15 Correct 3512 ms 57992 KB Output is correct
16 Correct 312 ms 64736 KB Output is correct
17 Correct 1370 ms 65196 KB Output is correct
18 Correct 2424 ms 75452 KB Output is correct
19 Correct 2192 ms 80776 KB Output is correct
20 Correct 1748 ms 85684 KB Output is correct
21 Correct 2 ms 85684 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 85684 KB Output is correct
2 Correct 3 ms 85684 KB Output is correct
3 Correct 3 ms 85684 KB Output is correct
4 Correct 2 ms 85684 KB Output is correct
5 Correct 2 ms 85684 KB Output is correct
6 Correct 3 ms 85684 KB Output is correct
7 Correct 2 ms 85684 KB Output is correct
8 Correct 2 ms 85684 KB Output is correct
9 Correct 3 ms 85684 KB Output is correct
10 Correct 2 ms 85684 KB Output is correct
11 Correct 3 ms 85684 KB Output is correct
12 Correct 772 ms 87548 KB Output is correct
13 Correct 454 ms 91760 KB Output is correct
14 Correct 721 ms 93492 KB Output is correct
15 Correct 889 ms 97828 KB Output is correct
16 Correct 507 ms 100084 KB Output is correct
17 Correct 830 ms 106776 KB Output is correct
18 Correct 690 ms 110940 KB Output is correct
19 Correct 1247 ms 122244 KB Output is correct
20 Correct 2975 ms 122244 KB Output is correct
21 Correct 355 ms 122244 KB Output is correct
22 Correct 3349 ms 131436 KB Output is correct
23 Correct 259 ms 138156 KB Output is correct
24 Correct 1188 ms 138672 KB Output is correct
25 Correct 1913 ms 148764 KB Output is correct
26 Correct 1655 ms 154316 KB Output is correct
27 Correct 1529 ms 159128 KB Output is correct
28 Correct 683 ms 184552 KB Output is correct
29 Correct 1621 ms 190252 KB Output is correct
30 Correct 5274 ms 205808 KB Output is correct
31 Runtime error 5028 ms 256752 KB Memory limit exceeded
32 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

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