oj.uz

Submission #331855

# Submission time Handle Problem Language Result Execution time Memory
331855 2020-11-30T12:57:34 Z aryan12 Game (IOI13_game) C++17
37 / 100
 1595 ms 256004 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const long long N = 2010;
vector<long long> seg[N * 4 + 10];
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 + 10; i++) {
        seg[i].resize(C * 4 + 10, 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 1772 KB Output is correct
7 Correct 1 ms 620 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 620 KB Output is correct
4 Correct 958 ms 168880 KB Output is correct
5 Correct 663 ms 168800 KB Output is correct
6 Correct 839 ms 166156 KB Output is correct
7 Correct 846 ms 165996 KB Output is correct
8 Correct 696 ms 166252 KB Output is correct
9 Correct 785 ms 165868 KB Output is correct
10 Correct 753 ms 165612 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 3 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 620 KB Output is correct
8 Correct 2 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 1094 ms 134892 KB Output is correct
13 Correct 1577 ms 131316 KB Output is correct
14 Runtime error 147 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 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 620 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 934 ms 168940 KB Output is correct
13 Correct 600 ms 168624 KB Output is correct
14 Correct 786 ms 166124 KB Output is correct
15 Correct 790 ms 165868 KB Output is correct
16 Correct 677 ms 166380 KB Output is correct
17 Correct 772 ms 165868 KB Output is correct
18 Correct 752 ms 165612 KB Output is correct
19 Correct 1099 ms 134764 KB Output is correct
20 Correct 1595 ms 131112 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 -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 2 ms 1772 KB Output is correct
3 Correct 2 ms 1784 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 620 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 890 ms 169068 KB Output is correct
13 Correct 612 ms 168684 KB Output is correct
14 Correct 771 ms 166124 KB Output is correct
15 Correct 776 ms 165996 KB Output is correct
16 Correct 692 ms 166252 KB Output is correct
17 Correct 790 ms 165996 KB Output is correct
18 Correct 740 ms 165616 KB Output is correct
19 Correct 1101 ms 134736 KB Output is correct
20 Correct 1547 ms 131376 KB Output is correct
21 Runtime error 143 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -