oj.uz

Submission #767589

# Submission time Handle Problem Language Result Execution time Memory
767589 2023-06-26T21:22:14 Z Ahmed57 Game (IOI13_game) C++17
63 / 100
 1300 ms 202912 KB 
#include "game.h"
#include<bits/stdc++.h>

using namespace std;
int n,m;
vector<vector<long long>> t;
void init(int R, int C){
    n = R , m = C;t.clear();
    vector<long long> a;
    bool ss = 0;
    if(R<=2000&&R>=100&&C<=2000&&C>=100){
        ss = 1;
    }
    long long hC = 4*C;
    long long hR = 4*R;
    if(ss)hC = min(hC,5000LL);
    if(ss)hR = min(hR,5000LL);
    for(int i = 0;i<hC;i++)a.push_back(0);
    for(int i = 0;i<hR;i++)t.push_back(a);
}
void update_y(int vx, int lx, int rx, int vy, int ly, int ry, int x, int y, long long new_val) {
    if (ly == ry) {
        if (lx == rx)
            t[vx][vy] = new_val;
        else
            t[vx][vy] = __gcd(t[vx*2][vy] , t[vx*2+1][vy]);
    } else {
        int my = (ly + ry) / 2;
        if (y <= my)
            update_y(vx, lx, rx, vy*2, ly, my, x, y, new_val);
        else
            update_y(vx, lx, rx, vy*2+1, my+1, ry, x, y, new_val);
        t[vx][vy] = __gcd(t[vx][vy*2] , t[vx][vy*2+1]);
    }
}

void update_x(int vx, int lx, int rx, int x, int y, long long new_val) {
    if (lx != rx) {
        int mx = (lx + rx) / 2;
        if (x <= mx)
            update_x(vx*2, lx, mx, x, y, new_val);
        else
            update_x(vx*2+1, mx+1, rx, x, y, new_val);
    }
    update_y(vx, lx, rx, 1, 1, m, x, y, new_val);
}
void update(int P, int Q, long long K){
    P++;Q++;
    update_x(1,1,n,P,Q,K);
}
long long sum_y(int vx, int vy, int tly, int try_, int ly, int ry) {
    if (ly > ry)
        return 0;
    if (ly == tly && try_ == ry)
        return t[vx][vy];
    int tmy = (tly + try_) / 2;
    return __gcd(sum_y(vx, vy*2, tly, tmy, ly, min(ry, tmy))
         , sum_y(vx, vy*2+1, tmy+1, try_, max(ly, tmy+1), ry));
}

long long sum_x(int vx, int tlx, int trx, int lx, int rx, int ly, int ry) {
    if (lx > rx)
        return 0;
    if (lx == tlx && trx == rx)
        return sum_y(vx, 1, 1,  m, ly, ry);
    int tmx = (tlx + trx) / 2;
    return __gcd(sum_x(vx*2, tlx, tmx, lx, min(rx, tmx), ly, ry)
         , sum_x(vx*2+1, tmx+1, trx, max(lx, tmx+1), rx, ly, ry));
}
long long calculate(int P, int Q, int U, int V){
    return sum_x(1,1,n,P+1,U+1,Q+1,V+1);
}
/*
int main(){
    init(2,3);
    update(0,0,20);
    update(0,2,15);
    update(1,1,12);
    cout<<calculate(0,0,0,2)<<endl;
    cout<<calculate(0,0,1,1)<<endl;
}*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1508 KB Output is correct
4 Correct 0 ms 276 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 596 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Correct 1 ms 1464 KB Output is correct
11 Correct 1 ms 1492 KB Output is correct
12 Correct 0 ms 212 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 528 ms 129820 KB Output is correct
5 Correct 406 ms 130072 KB Output is correct
6 Correct 487 ms 128816 KB Output is correct
7 Correct 494 ms 128908 KB Output is correct
8 Correct 408 ms 128832 KB Output is correct
9 Correct 490 ms 128832 KB Output is correct
10 Correct 430 ms 128916 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 1 ms 1492 KB Output is correct
12 Correct 833 ms 129956 KB Output is correct
13 Correct 1086 ms 126468 KB Output is correct
14 Correct 598 ms 196868 KB Output is correct
15 Correct 1270 ms 197068 KB Output is correct
16 Correct 203 ms 197016 KB Output is correct
17 Correct 1074 ms 197556 KB Output is correct
18 Correct 1226 ms 197428 KB Output is correct
19 Correct 1182 ms 197436 KB Output is correct
20 Correct 1132 ms 196840 KB Output is correct
21 Correct 1 ms 212 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 1 ms 1492 KB Output is correct
12 Correct 522 ms 129756 KB Output is correct
13 Correct 404 ms 130160 KB Output is correct
14 Correct 479 ms 128860 KB Output is correct
15 Correct 486 ms 128880 KB Output is correct
16 Correct 425 ms 128812 KB Output is correct
17 Correct 464 ms 128816 KB Output is correct
18 Correct 437 ms 128808 KB Output is correct
19 Correct 786 ms 129808 KB Output is correct
20 Correct 1128 ms 126496 KB Output is correct
21 Correct 626 ms 201540 KB Output is correct
22 Correct 1275 ms 201420 KB Output is correct
23 Correct 200 ms 201256 KB Output is correct
24 Correct 1068 ms 202396 KB Output is correct
25 Correct 1227 ms 202700 KB Output is correct
26 Correct 1219 ms 202912 KB Output is correct
27 Correct 1187 ms 202308 KB Output is correct
28 Runtime error 1 ms 340 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 596 KB Output is correct
9 Correct 1 ms 1492 KB Output is correct
10 Correct 1 ms 1492 KB Output is correct
11 Correct 1 ms 1492 KB Output is correct
12 Correct 530 ms 129724 KB Output is correct
13 Correct 412 ms 130092 KB Output is correct
14 Correct 457 ms 128812 KB Output is correct
15 Correct 466 ms 128820 KB Output is correct
16 Correct 404 ms 128816 KB Output is correct
17 Correct 529 ms 128816 KB Output is correct
18 Correct 516 ms 128800 KB Output is correct
19 Correct 785 ms 129832 KB Output is correct
20 Correct 1087 ms 126492 KB Output is correct
21 Correct 588 ms 201476 KB Output is correct
22 Correct 1300 ms 201460 KB Output is correct
23 Correct 195 ms 201252 KB Output is correct
24 Correct 1078 ms 202416 KB Output is correct
25 Correct 1205 ms 202588 KB Output is correct
26 Correct 1197 ms 202888 KB Output is correct
27 Correct 1267 ms 202188 KB Output is correct
28 Runtime error 1 ms 340 KB Execution killed with signal 11
29 Halted 0 ms 0 KB -