oj.uz

Submission #331856

# Submission time Handle Problem Language Result Execution time Memory
331856 2020-11-30T13:00:26 Z aryan12 Game (IOI13_game) C++17
37 / 100
 1572 ms 256004 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const long long N = 2000;
vector<long long> seg[N * 4 + 2];
long long row, col;

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;
}

void init(int R, int C) {
    row = R;
    col = C;
    for(long long i = 0; i <= R * 4; i++) {
        seg[i].resize(C * 4 + 1, 0);
    }
}

void updateY(long long l, long long r, long long xpos, long long pos, long long xl, long long xr, long long q, long long val) {
    if(l == r) {
        if(xl == xr) {
            seg[xpos][pos] = val;
            return;
        }
        else {
            seg[xpos][pos] = gcd2(seg[xpos * 2][pos], seg[xpos * 2 + 1][pos]);
            return;
        }
    }
    long long mid = (l + r) / 2;
    if(q <= mid)
        updateY(l, mid, xpos, pos * 2, xl, xr, q, val);
    else
        updateY(mid + 1, r, xpos, pos * 2 + 1, xl, xr, q, val);
    seg[xpos][pos] = gcd2(seg[xpos][pos * 2], seg[xpos][pos * 2 + 1]);
}

void updateX(long long l, long long r, long long pos, long long ymax, long long p, long long q, long long val) {
    if(l != r) {
        long long mid = (l + r) / 2;
        if(p <= mid)
            updateX(l, mid, pos * 2, ymax, p, q, val);
        else
            updateX(mid + 1, r, pos * 2 + 1, ymax, p, q, val);
    }
    updateY(1, ymax, pos, 1, l, r, q, val);
}

void update(int P, int Q, long long K) {
    P++;
    Q++;
    updateX(1, row, 1, col, P, Q, K);
}

long long calculateY(long long l, long long r, long long pos, long long U, long long V, long long xpos) {
    if(U <= l && r <= V) {
        return seg[xpos][pos];
    }
    if(U > r || V < l)
        return 0;
    long long mid = (l + r) / 2;
    return gcd2(calculateY(l, mid, pos * 2, U, V, xpos), calculateY(mid + 1, r, pos * 2 + 1, U, V, xpos));
}

long long calculateX(long long l, long long r, long long pos, long long ymax, long long P, long long Q, long long U, long long V) {
    if(P <= l && r <= Q) {
        return calculateY(1, ymax, 1, U, V, pos);
    }
    if(P > r || Q < l)
        return 0;
    long long mid = (l + r) / 2;
    return gcd2(calculateX(l, mid, pos * 2, ymax, P, Q, U, V), calculateX(mid + 1, r, pos * 2 + 1, ymax, P, Q, U, V));

}

long long calculate(int P, int Q, int U, int V) {
    P++;
    Q++;
    U++;
    V++;
    swap(Q, U);
    return calculateX(1, row, 1, col, P, Q, U, V);
}
/*
int main() {
    cout << "Input R and C" << endl;
    long long R, C;
    cin >> R >> C;
    init(R, C);
    cout << "Input the number of queries (Q)" << endl;
    long long Q;
    cin >> Q;
    for(long long i = 1; i <= Q; i++) {
        cout << "Enter 1 for Update, 2 for Calculate" << endl;
        long long command;
        cin >> command;
        if(command == 1) {
            cout << "Enter 2 integers(R, C) + 1 integer (val)" << endl;
            long long qr, qc, val;
            cin >> qr >> qc >> val;
            update(qr, qc, val);
            cout << "The segment tree after this operation looks like this" << endl;
            for(long long i = 1; i <= row * 4; i++) {
                for(long long j = 1; j <= col * 4; j++) {
                    cout << seg[i][j] << " ";
                }
                cout << endl;
            }
        }
        else {
            cout << "Enter 4 integers (R1, C1) (R2, C2)" << endl;
            long long qrl, qrr, qcl, qcr;
            cin >> qrl >> qrr >> qcl >> qcr;
            cout << "Answer = " << calculate(qrl, qrr, qcl, qcr) << endl;
        }
    }
}
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 2 ms 1772 KB Output is correct
3 Correct 2 ms 1772 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 1772 KB Output is correct
6 Correct 2 ms 1900 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 876 KB Output is correct
9 Correct 2 ms 1772 KB Output is correct
10 Correct 2 ms 1772 KB Output is correct
11 Correct 2 ms 1772 KB Output is correct
12 Correct 1 ms 492 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 893 ms 133868 KB Output is correct
5 Correct 631 ms 134256 KB Output is correct
6 Correct 785 ms 130924 KB Output is correct
7 Correct 792 ms 130796 KB Output is correct
8 Correct 695 ms 131436 KB Output is correct
9 Correct 784 ms 130796 KB Output is correct
10 Correct 729 ms 130540 KB Output is correct
11 Correct 1 ms 492 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 2 ms 1772 KB Output is correct
3 Correct 2 ms 1772 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 1772 KB Output is correct
6 Correct 3 ms 1772 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 876 KB Output is correct
9 Correct 2 ms 1772 KB Output is correct
10 Correct 2 ms 1772 KB Output is correct
11 Correct 2 ms 1772 KB Output is correct
12 Correct 1096 ms 130812 KB Output is correct
13 Correct 1549 ms 127724 KB Output is correct
14 Runtime error 146 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 2 ms 1772 KB Output is correct
3 Correct 2 ms 1900 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 1772 KB Output is correct
6 Correct 2 ms 1772 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 876 KB Output is correct
9 Correct 2 ms 1772 KB Output is correct
10 Correct 2 ms 1772 KB Output is correct
11 Correct 2 ms 1772 KB Output is correct
12 Correct 886 ms 134076 KB Output is correct
13 Correct 591 ms 134244 KB Output is correct
14 Correct 849 ms 130924 KB Output is correct
15 Correct 753 ms 130668 KB Output is correct
16 Correct 666 ms 131436 KB Output is correct
17 Correct 776 ms 130812 KB Output is correct
18 Correct 747 ms 130284 KB Output is correct
19 Correct 1142 ms 130668 KB Output is correct
20 Correct 1572 ms 127488 KB Output is correct
21 Runtime error 145 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 2 ms 1772 KB Output is correct
3 Correct 2 ms 1772 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 1772 KB Output is correct
6 Correct 2 ms 1772 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 876 KB Output is correct
9 Correct 2 ms 1772 KB Output is correct
10 Correct 2 ms 1772 KB Output is correct
11 Correct 2 ms 1772 KB Output is correct
12 Correct 876 ms 133868 KB Output is correct
13 Correct 657 ms 133868 KB Output is correct
14 Correct 783 ms 130668 KB Output is correct
15 Correct 784 ms 130476 KB Output is correct
16 Correct 670 ms 131180 KB Output is correct
17 Correct 799 ms 130412 KB Output is correct
18 Correct 726 ms 130088 KB Output is correct
19 Correct 1084 ms 130540 KB Output is correct
20 Correct 1569 ms 127212 KB Output is correct
21 Runtime error 144 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -