oj.uz

Submission #599977

# Submission time Handle Problem Language Result Execution time Memory
599977 2022-07-20T11:02:18 Z AmirElarbi Game (IOI13_game) C++14
37 / 100
 1218 ms 256000 KB 
#include <bits/stdc++.h>
#define vi vector<int>
#define ve vector
#define ll long long
#define vf vector<float>
#define vll vector<pair<ll,ll>>
#define ii pair<int,int>
#define pll pair<ll,ll>
#define vvi vector<vi>
#define vii vector<ii>
#define gii greater<ii>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define INF 2e9+5
#define eps 1e-7
#define eps1 1e-25
#define optimise ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX_A 1e5+5
using namespace std;
const int MOD = 1e9;
const int nax = 2e3+5;
#include "game.h"
ll n,m;
ve<ve<ll>> t;
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;
}

ll gcd_y(int vx, int vy, int tly, int try_, int ly, int ry) {
    if (ly > ry) 
        return 0ll;
    if (ly == tly && try_ == ry)
        return t[vx][vy];
    int tmy = (tly + try_) / 2;
    return gcd2( gcd_y(vx, vy*2, tly, tmy, ly, min(ry, tmy))
         , gcd_y(vx, vy*2+1, tmy+1, try_, max(ly, tmy+1), ry));
}

ll gcd_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 gcd_y(vx, 1, 0, m-1, ly, ry);
    int tmx = (tlx + trx) / 2;
    return gcd2(gcd_x(vx*2, tlx, tmx, lx, min(rx, tmx), ly, ry)
         , gcd_x(vx*2+1, tmx+1, trx, max(lx, tmx+1), rx, ly, ry));
}

void update_y(int vx, int lx, int rx, int vy, int ly, int ry, int x, int y, ll new_val) {
    if (ly == ry) {
        if (lx == rx)
            t[vx][vy] = new_val;
        else
            t[vx][vy] = gcd2(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] = gcd2(t[vx][vy*2] , t[vx][vy*2+1]);
    }
}

void update_x(int vx, int lx, int rx, int x, int y, ll 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, 0, m-1, x, y, new_val);
}

void init(int R, int C) {
    ve<ll> tm(C*5+5,0);
    for (int i = 0; i <= R*5+5; ++i)
    {
        t.pb(tm);
    }
    n = R, m = C;
}

void update(int P, int Q, long long K) {
    update_x(1,0,n-1,P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
    return gcd_x(1,0,n-1,P,U,Q,V);
}

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 2260 KB Output is correct
3 Correct 2 ms 2260 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 2260 KB Output is correct
6 Correct 1 ms 2260 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 2260 KB Output is correct
10 Correct 1 ms 2260 KB Output is correct
11 Correct 1 ms 2260 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 292 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 588 ms 223624 KB Output is correct
5 Correct 479 ms 223944 KB Output is correct
6 Correct 559 ms 223380 KB Output is correct
7 Correct 580 ms 223372 KB Output is correct
8 Correct 493 ms 223436 KB Output is correct
9 Correct 604 ms 223380 KB Output is correct
10 Correct 537 ms 223436 KB Output is correct
11 Correct 0 ms 212 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 2260 KB Output is correct
3 Correct 2 ms 2260 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 2260 KB Output is correct
6 Correct 1 ms 2260 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 2260 KB Output is correct
10 Correct 1 ms 2272 KB Output is correct
11 Correct 1 ms 2260 KB Output is correct
12 Correct 800 ms 200940 KB Output is correct
13 Correct 1218 ms 197500 KB Output is correct
14 Runtime error 97 ms 256000 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 2260 KB Output is correct
3 Correct 1 ms 2260 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 2260 KB Output is correct
6 Correct 1 ms 2260 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 2260 KB Output is correct
10 Correct 1 ms 2260 KB Output is correct
11 Correct 1 ms 2260 KB Output is correct
12 Correct 624 ms 223512 KB Output is correct
13 Correct 475 ms 223860 KB Output is correct
14 Correct 560 ms 223456 KB Output is correct
15 Correct 570 ms 223432 KB Output is correct
16 Correct 496 ms 223480 KB Output is correct
17 Correct 564 ms 223544 KB Output is correct
18 Correct 524 ms 223432 KB Output is correct
19 Correct 797 ms 200740 KB Output is correct
20 Correct 1201 ms 197440 KB Output is correct
21 Runtime error 94 ms 256000 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 2260 KB Output is correct
3 Correct 1 ms 2260 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 2260 KB Output is correct
6 Correct 1 ms 2260 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 2260 KB Output is correct
10 Correct 1 ms 2260 KB Output is correct
11 Correct 1 ms 2260 KB Output is correct
12 Correct 600 ms 223628 KB Output is correct
13 Correct 480 ms 223816 KB Output is correct
14 Correct 649 ms 223412 KB Output is correct
15 Correct 598 ms 223420 KB Output is correct
16 Correct 502 ms 223480 KB Output is correct
17 Correct 567 ms 223392 KB Output is correct
18 Correct 523 ms 223412 KB Output is correct
19 Correct 805 ms 200872 KB Output is correct
20 Correct 1204 ms 197348 KB Output is correct
21 Runtime error 99 ms 256000 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -